一 建设茶叶网站前的市场分析,局域网网站建设软件,wordpress标题重复,云南火电建设公司网站前言 ①排序#xff1a;所谓排序#xff0c;就是使一串记录#xff0c;按照其中的某个或某些关键字的大小#xff0c;递增或递减的排列起来的操作。 ②稳定性#xff1a;假定在待排序的记录序列中#xff0c;存在多个具有相同的关键字的记录#xff0c;若经过排序#…前言 ①排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 ②稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。 ③内部排序数据元素全部放在内存中的排序。 ④外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。 文章目录 前言1.冒泡排序2.插入排序3.希尔排序4.直接选择排序5.堆排序6.快速排序(qsort)6.1 hoare法6.2 前后指针法6.3 挖洞法 7.归并排序8.排序性能比较 1.冒泡排序
冒泡排序是我们刚接触C语言时就经常使用的排序大家应该都清楚什么时冒泡排序这里就不做介绍。
void BubbleSort(int* a, int n)
{for (int i 0; i n; i){bool exchange false;for (int j 1; j n - i; j){if (a[j - 1] a[j]){int temp;temp a[j - 1];a[j - 1] a[j];a[j] temp;exchange true;}}if (exchange false)break;}
}2.插入排序 直接插入排序是一种简单的插入排序法其基本思想是 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列。 直接插入排序的特性总结 元素集合越接近有序直接插入排序算法的时间效率越高时间复杂度O(N^2)空间复杂度O(1)它是一种稳定的排序算法稳定性稳定 void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){int end i;int tmp a[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];--end;}elsebreak;}a[end 1] tmp;}
}3.希尔排序 希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成个组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达1时所有记录在统一组内排好序。 总结一下步骤就是两步 1.预排序 2.插入排序 希尔排序的特性总结
希尔排序是对直接插入排序的优化。当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些树中给出的希尔排序的时间复杂度都不固定。研究表明希尔排序的时间复杂度约为O(N1.3)
void ShellSort(int* a, int n)
{int gap n;// gap 1时是预排序目的让他接近有序// gap 1是直接插入排序目的是让他有序while (gap 1){//gap gap / 2;gap gap / 3 1;//现希尔排序的常用的两种gap取值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;}elsebreak;}a[end gap] tmp;}}
}4.直接选择排序 其思想是 每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。 直接选择排序的特性总结
直接选择排序思考非常好理解但是效率不是很好。实际中很少使用时间复杂度O(N^2)空间复杂度O(1)稳定性不稳定
void SelectSort(int* a, int n)
{int begin 0, end n - 1;while (begin end){int mini begin, maxi begin;for (int i begin 1; i end; i){if (a[i] a[mini]){mini i;}if (a[i] a[maxi]){maxi i;}}Swap(a[begin], a[mini]);if (maxi begin){maxi mini;}Swap(a[end], a[maxi]);begin;--end;}
}5.堆排序
具体见 链接: C语言数据结构-----二叉树(2)堆的深入理解及应用、链式二叉树的讲解及代码实现
void AdjustDown(int* a, int size, int parent)
{int child parent * 2 1;while (child size){// 假设左孩子小如果解设错了更新一下if (child 1 size a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}// 升序
void HeapSort(int* a, int n)
{// O(N)// 建大堆for (int i (n - 1 - 1) / 2; i 0; --i){AdjustDown(a, n, i);}// O(N*logN)int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
}6.快速排序(qsort) 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。 其也就是我们在C语言中常使用的qsort函数。 其有三种三种版本hoare版本挖坑法版本前后指针版本。让我们一种一种来看。
6.1 hoare法
用一个形象生动的动画来说明一下此方法 再配上一个简单的说明 ①先以6为基准然后慢慢走Lift和Right。最后比基准小的在左边比基准大的在右边。 ②Right先走走到比基准小的值就停下然后Left走走到比基准大的值就停下然后交换Left和Right的值。 ③然后Right继续走走到比基准小的值就停下然后Left走走到比基准大的值就停下然后继续交换。 ④Right和Left相遇了就把基准值与相遇位置的值交换。便完成了比基准小的在左边比基准大的在右边的操作。 int GetMidi(int* a, int begin, int end)
{int midi (begin end) / 2;// begin midi end 三个数选中位数if (a[begin] a[midi]){if (a[midi] a[end])return midi;else if (a[begin] a[end])return begin;elsereturn end;}else // a[begin] a[midi]{if (a[midi] a[end])return midi;else if (a[begin] a[end])return begin;elsereturn end;}
}void hoare_QuickSort(int* a, int begin, int end)
{if (begin end)return;if (end - begin 1 10){InsertSort(a begin, end - begin 1);}else{int midi GetMidi(a, begin, end);Swap(a[midi], a[begin]);int left begin, right end;int keyi begin;while (left right){// 右边找小while (left right a[right] a[keyi]){--right;}// 左边找大while (left right a[left] a[keyi]){left;}Swap(a[left], a[right]);}Swap(a[left], a[keyi]);keyi left;// [begin, keyi-1] keyi [keyi1, end]hoare_QuickSort(a, begin, keyi - 1);hoare_QuickSort(a, keyi 1, end);}
}6.2 前后指针法
用一个形象生动的动画来说明一下此方法 配上一个简短的说明 ①以6为基准值前驱指针prev先走cur再走。当cur的值大于基准值时prev不动cur继续走当cur的值小于基准值时cur不动。此时prev向前走交换cur与prev的值。这样小的数就到前面大的数就到后面了。 ②cur继续走以此类推。cur遇到比基准大的数就继续走知道遇到比基准小的数prev才动然后交换。 ③继续上述步骤直到cur越界然后交换基准值和prev的值。 int GetMidi(int* a, int begin, int end)
{int midi (begin end) / 2;// begin midi end 三个数选中位数if (a[begin] a[midi]){if (a[midi] a[end])return midi;else if (a[begin] a[end])return begin;elsereturn end;}else // a[begin] a[midi]{if (a[midi] a[end])return midi;else if (a[begin] a[end])return begin;elsereturn end;}
}void point_QuickSort(int* a, int begin, int end)
{if (begin end)return;if (end - begin 1 10){InsertSort(a begin, end - begin 1);}else{int midi GetMidi(a, begin, end);Swap(a[midi], a[begin]);int keyi begin;int prev begin;int cur prev 1;while (cur end){if (a[cur] a[keyi] prev ! cur)Swap(a[prev], a[cur]);cur;}Swap(a[prev], a[keyi]);keyi prev;// [begin, keyi-1] keyi [keyi1, end]point_QuickSort(a, begin, keyi - 1);point_QuickSort(a, keyi 1, end);}
}6.3 挖洞法
用一个形象生动的动画来说明一下此方法 再配一个简短的说明 ①先选出基准值然后基准值的位置为坑位。Right先走遇到比基准值小的数就停下。然后把这个小于基准值的数放到坑位这个位置变成新的坑位。 ②然后left走遇到比基准值大的数停下把这个大于基准值的数放到坑位这个位置再变成新的坑位。 ③以此类推直到left和right相遇然后将基准值放入最后的坑位即可。
int GetMidi(int* a, int begin, int end)
{int midi (begin end) / 2;// begin midi end 三个数选中位数if (a[begin] a[midi]){if (a[midi] a[end])return midi;else if (a[begin] a[end])return begin;elsereturn end;}else // a[begin] a[midi]{if (a[midi] a[end])return midi;else if (a[begin] a[end])return begin;elsereturn end;}
}int dig(int* a, int begin, int end)
{int midi GetMidi(a, begin, end);Swap(a[midi], a[begin]);int key a[begin];int hole begin;while (begin end){// 右边找小填到左边的坑while (begin end a[end] key){--end;}a[hole] a[end];hole end;// 左边找大填到右边的坑while (begin end a[begin] key){begin;}a[hole] a[begin];hole begin;}a[hole] key;return hole;
}void dig_QuickSort(int* a, int begin, int end)
{if (begin end)return;int keyi dig(a, begin, end);dig_QuickSort(a, begin, keyi - 1);dig_QuickSort(a, keyi 1, end);
}7.归并排序 归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 简而言之就是先一个一个排然后两个两个排然后四个四个排然后再全排序。
void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin end)return;int mid (begin end) / 2;// [begin, mid][mid1, end]_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid 1, end, tmp);// [begin, mid][mid1, end]归并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(malloc fail);return;}_MergeSort(a, 0, n - 1, tmp);free(tmp);
}8.排序性能比较
void TestOP()
{srand(time(0));const int N 100000;int* a1 (int*)malloc(sizeof(int) * N);int* a2 (int*)malloc(sizeof(int) * N);int* a3 (int*)malloc(sizeof(int) * N);int* a4 (int*)malloc(sizeof(int) * N);int* a5 (int*)malloc(sizeof(int) * N);int* a6 (int*)malloc(sizeof(int) * N);int* a7 (int*)malloc(sizeof(int) * N);for (int i 0; i N; i){a1[i] rand();a2[i] a1[i];a3[i] a1[i];a4[i] a1[i];a5[i] a1[i];a6[i] a1[i];a7[i] a1[i];}int begin1 clock();InsertSort(a1, N);int end1 clock();int begin2 clock();ShellSort(a2, N);int end2 clock();int begin3 clock();SelectSort(a3, N);int end3 clock();int begin4 clock();HeapSort(a4, N);int end4 clock();int begin5 clock();hoare_QuickSort(a5, 0, N - 1);int end5 clock();int begin6 clock();MergeSort(a6, N);int end6 clock();int begin7 clock();BubbleSort(a7, N);int end7 clock();printf(InsertSort:%d\n, end1 - begin1);printf(ShellSort:%d\n, end2 - begin2);printf(SelectSort:%d\n, end3 - begin3);printf(HeapSort:%d\n, end4 - begin4);printf(hoare_QuickSort:%d\n, end5 - begin5);printf(MergeSort:%d\n, end6 - begin6);printf(BubbleSort:%d\n, end7 - begin7);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);
}各种排序跑10W个数所需要的时间如上。 快速排序的三种算法时间都差不多。只不过思想不一样罢了。
