国内知名网站,湖口网站建设,网站的产品图片怎样做清晰,网站qq号获取目录
一、插入排序
1、直接插入排序
1.1、排序方法
1.2、图解分析
1.3、代码实现
2、希尔排序
2.1、排序方法
2.2、图解分析
2.3、代码实现
二、选择排序
1、直接选择排序
1.1、排序方法
1.2、图解分析
1.3、代码实现
2、堆排序
2.1、排序方法
2.2、图解分析 …目录
一、插入排序
1、直接插入排序
1.1、排序方法
1.2、图解分析
1.3、代码实现
2、希尔排序
2.1、排序方法
2.2、图解分析
2.3、代码实现
二、选择排序
1、直接选择排序
1.1、排序方法
1.2、图解分析
1.3、代码实现
2、堆排序
2.1、排序方法
2.2、图解分析
2.3、代码实现
三、交换排序
1、冒泡排序
1.1、排序方法
1.2、图解分析
1.3、代码实现
2、快速排序
2.1、hoare排序
2.1.1、图解分析
2.1.2、代码实现
2.2、挖坑法
2.2.1、图解分析
2.2.2、代码实现
2.3、前后指针法
2.3.1、图解分析
2.3.2、代码实现
四、归并排序
1、排序方法
2、图解分析
3、代码实现 一、插入排序 基本思想把待排序的数据按其关键码值的大小追个插入到一个有序序列中得到一个新的有序序列。
1、直接插入排序
1.1、排序方法 当插入第i个元素时数组的前i-1个元素已经有序将第i个元素与前i-1个元素的关键码值进行比较找到合适的位置插入并将该位置之后的所有元素顺序后移即可。
1.2、图解分析 1.3、代码实现
// 直接插入排序
void InsertSort(int* a, int n)
{for (int i 0; i n; i){int tmp a[i];int end i-1;while (end 0){if (tmp a[end]){a[end 1] a[end];end--;}else{break;}}a[end 1] tmp;;}
}
2、希尔排序
2.1、排序方法 希尔排序是对直接插入排序的优化。希尔排序的基本思想是先选定一个合理的增量gap把待排序文件中的数据分成gap个组每一组中的相邻元素位置相差gap的距离对每组元素各自进行直接插入排序。然后适当缩小gap重复上述操作。直到gap等于1时所有元素在同一组内最后一次直接插入排序。
2.2、图解分析 2.3、代码实现
// 希尔排序
void ShellSort(int* a, int n)
{int gap n;while (gap 1){bool change false;gap gap / 3 1;for (int i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end-gap;change true; }else{break;}}a[end gap] tmp;;}if (change false){break;}}
}
二、选择排序 基本思想每次从待排序元素中选出最大或最小的一个元素将其存放在已有序序列的后一个位置重复操作直到所有元素存放结束得到一个有序的新序列。
1、直接选择排序
1.1、排序方法 在元素集合arr[i]~arr[n-1]中选出关键码值最大小的元素若该元素不是第一个或最后一个则将其与这组元素中的第一个或最后一个元素进行交换对剩余未排序元素重复上述操作直到结束。
1.2、图解分析 1.3、代码实现
// 选择排序
void SelectSort(int* a, int n)
{int begin_i 0;int end_i n-1;while (begin_i end_i){int max_i end_i;int min_i begin_i;for (int i begin_i; i end_i; i){if (a[i] a[min_i]){Swap(a[i], a[min_i]);}if (a[i] a[max_i]){Swap(a[i], a[max_i]);}}begin_i;end_i--;}
}
2、堆排序
2.1、排序方法 堆排序的操作对象是堆排序会调整部分节点在堆中的相对位置为了不破坏堆的性质我们将堆顶节点与堆的最后一个节点交换再将除最后一个节点之外的其他节点通过向下调整算法调整成为一个新的堆。重复操作直到只剩下一个节点为止。
2.2、图解分析 2.3、代码实现
//堆排序typedef struct Heap
{int* a;int size;int capacity;
}Heap;//向下调整算法
void AdjustDwon(int* a, int n, Heap* hp)
{for (int parent (n - 2) / 2; parent 0; parent--){int child parent * 2 1;while (child n){bool change false;if (child 1 n){child hp-a[child] hp-a[child 1] ? child : child 1;}if (hp-a[child] hp-a[parent]){int tmp hp-a[parent];hp-a[parent] hp-a[child];hp-a[child] tmp;change true;parent child;child parent * 2 1;}if (change false){break;}}}
}//初始化堆
void InitialHeap(Heap* hp,int n)
{if (!hp){return;}int* tmp (int*)malloc(sizeof(int) * n);if (!tmp){perror(InitialHeap::malloc:);return;}hp-a tmp;hp-size 0;hp-capacity n;
}//创建堆
void HeapBuild(Heap* hp, int* a, int n)
{assert(hp);for (int i 0; i n; i){hp-a[i] a[i];}AdjustDwon(a, n, hp);
}//排序
void Sort(Heap* hp, int* a, int n)
{int end n - 1;while (end 0){int tmp hp-a[0];hp-a[0] hp-a[end];hp-a[end] tmp;a[end] hp-a[end];end--;AdjustDwon(a, end, hp);}a[0] hp-a[0];
}
三、交换排序 基本思想根据序列中两个元素的关键码值的大小来判断是否需要交换他们在序列中的位置默认将关键码值较大的元素向序列的尾部移动关键码值较小的元素向序列的首部移动。
1、冒泡排序
1.1、排序方法 冒泡排序是将待排序元素的关键码值最大小的元素通过从前往后依次两两比较交换到最后面的位置。每操作一次可以确定一个元素在有序序列中的的位置。
1.2、图解分析 1.3、代码实现
// 冒泡排序
void BubbleSort(int* a, int n)
{for (int j 1; j n; j){for (int i 0; i n - j; i){if (a[i] a[i 1]){int tmp a[i];a[i] a[i 1];a[i 1] tmp;}}}
}
2、快速排序 基本思想快速排序是任取待排序元素序列中的某元素的关键码值作为基准值按照该基准值将待排序集合分割成左右两个子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值再对左右子序列重复该过程直到结束。
2.1、hoare排序
2.1.1、图解分析 key选左边从右边出发。保证了相遇位置的值比key位置的值小 key选右边从左边出发。保证了相遇位置的值比key位置的值大 注意key指的是下标 2.1.2、代码实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{int key left;while (left right){while (left right a[right] a[key]){right--;}while (leftright a[left]a[key]){left;}int tmp a[right];a[right] a[left];a[left] tmp;}int tmp a[key];a[key] a[left];a[left] tmp;return left;
}
2.2、挖坑法
2.2.1、图解分析 注意 这里的key是一个变量不是下标 2.2.2、代码实现
// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{int key a[left];int hole left;while (left right){while (hole right){if (a[right] key){a[hole] a[right];hole right;break;}right--;}while (hole left){if (a[left] key){a[hole] a[left];hole left;break;}left;}}a[hole] key;return hole;
}
2.3、前后指针法
2.3.1、图解分析 这里的key同样是一个变量不是下标 2.3.2、代码实现
// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{int prev left;int cur prev 1;int key a[left];while (cur right){if (a[cur] key){prev;int tmp a[prev];a[prev] a[cur];a[cur] tmp;}cur;}a[left] a[prev];a[prev] key;return prev;
}
四、归并排序
1、排序方法 归并排序是建立在归并操作上的一种排序算法。归并排序是将已有序的子序列合并得到完全有序的序列即先使每个字序列有序再使子序列段间有序。归并排序的核心思想是先分解后合并。
2、图解分析 3、代码实现
// 归并排序递归实现void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin end){return;}int mid (begin end) / 2;_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid 1, end, tmp);int begin1 begin, end1 mid;int begin2 mid 1, end2 end;int i begin;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[i] a[begin1];}else{tmp[i] a[begin2];}}while (begin1 end1){tmp[i] a[begin1];}while (begin2 end2){tmp[i] a[begin2];}memcpy(a begin, tmp begin, sizeof(int) * (end - begin 1));
}void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(MergeSort--malloc:);return;}_MergeSort(a, 0, n - 1, tmp);free(tmp);tmp NULL;
}
