常见排序算法详解

一、插入排序插入排序的核心思想是把一个数据插入已经排好序的一组数据中的正确位置。当运用插入排序来排序一组数据时先把第一个数看作有序把第二个数插入正确位置再把前两个数看作有序把第三个数插入正确位置以此类推直到所有数据按照正确顺序排列。以升序为例假设[0-end]有序。每一趟排序需要将end1位置的数据与前面的数据依次比较。如果小于当前位置的数据需要将当前位置的数据向前移动一位否则就将这个数据插入到当前数据的后面。将移动一位的操作放在while循环外面来写有这样的考虑如果end1位置的数据是最小的那么最后end会减小至-1导致跳出循环。所以把移动数据的逻辑写在循环外面就不用写两次了。void InsertSort(int* a, int n) { for (int i 0; i n - 1; i) { int end i;//认为0-end有序end1位置的值插入[0,end]保持有序 int tmp a[end 1]; while (end 0) { if (a[end] tmp) { a[end 1] a[end]; --end; } else { break; } } a[end 1] tmp; } }二、希尔排序希尔排序是对插入排序的优化。它的核心思想是通过预排序使数组接近有序然后再进行插入排序。我们将整组数据分为gap组每一组中每gap个数据取一个数据然后将每一组插入排序再整体插入排序。我们首先实现每一组插入排序的代码void ShellSort(int* a, int n) { int gap 3; for (int j 0; j gap; j) { for (size_t i j; i n - gap; i gap) { int end i; int tmp a[end gap]; while (end 0) { if (tmp a[end]) { a[end gap] a[end]; end - gap; } else { break; } } a[end gap] tmp; } } }这是一组一组排用了三层循环来实现。我们也可以多组一起排用两个循环就可以实现看上去简洁一点但是效率并没有改变。void ShellSort(int* a, int n) { int gap 3; for (size_t 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; } else { break; } } a[end gap] tmp; } }预排序过程gap越大大的数据越快调到后面小的数据越快跳到前面但预排序后的结果越不接近有序。gap越小跳得越慢但预排序后的结果越接近有序。一般会走多组预排序每次预排序gap的值发生变化。下一次预排序的gap值与这一次预排序的gap值满足gap gap/3 1比较合适可以保证最后一次gap1也就是最后一次进行的是整体的插入排序。void ShellSort(int* a, int n) { int gap n; while (gap 1) { gap gap/3 1; for (size_t 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; } else { break; } } a[end gap] tmp; } } }希尔排序的时间复杂度约为O(n^1.3)其证明涉及一些复杂的数学知识。三、选择排序选择排序的核心思想是遍历一次所有数据选出最大和最小的数据放在两端再遍历一次剩下的数据选出其中最大和最小的数据放在第二和倒数第二的位置......直到数组有序。void SelectSort(int* a, int n) { int begin 0, end n-1; while (begin end) { int mini begin, maxi end; for (size_t i begin; 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--; } }这里有一个需要注意的地方如果maxi恰好与begin重合那么交换begin与mini位置的数据后最大的数据就移动到mini的位置了。所以要写一个判断语句来专门处理这种情况。四、快速排序4.1 hoare版快速排序快速排序的核心思想是将数组中的一个数据作为“关键值”两个指针分别从数组的左端和右端开始遍历数组遍历的过程中将所有比“关键值”小的数据放到左边把所有比“关键值”大的数据都放到右边当两个指针相遇时将相遇位置的数据与“关键值”互换这样关键值就把数组分成了两半左边数据都小于关键值右边数据都大于关键值。然后在分出的两个数组中再进行一次这样的遍历......整个过程类似二叉树的递归遍历终止条件是分出的数组中只剩1个值或没有值递归遍历结束时整个数组就有序了。void QuickSort(int* a, int left, int right) { if (left right) return; int keyi left; int begin left, end right; while (begin end) { //右边找小的 while (begin end a[end] a[keyi]) { --end; } //左边找大的 while (begin end a[begin] a[keyi]) { begin; } Swap(a[begin], a[end]); } Swap(a[keyi], a[begin]); keyi begin; QuickSort(a, left, keyi - 1); QuickSort(a, keyi 1, right); }此处有一个可能的疑点为什么begin和end相遇的位置数据一定比关键值小分两种情况分析如果是begin遇到了endend先走停下的条件是遇到比关键值小的数据所以end停下的位置的数据一定比关键值小。begin没有找到比关键值更大的数据所以遇到end停下了。如果是end遇到了beginend先走找比关键值更小的数据没有找到直接和begin相遇了。此时begin停留的位置是上一轮交换过后的位置上一轮交换把比关键值小的数据移动到begin的位置了。不管是那种情况相遇位置的数据一定比关键值小。4.2 快速排序算法的优化我们已经写出了一个简单版的快速排序算法。然而这个算法现在有很大的缺陷。首先这个算法面对已经有序的数组时每趟排序只能解决一个数据此时它就退化成一个O(N^2)的算法递归深度太深会有栈溢出的风险。为了避免有序情况下的效率退化我们可以对算法进行一些优化。我们可以不要总是选择数组的第一个数据作为关键值可以采取“三数取中”的方法在最前面、最后面和最中间这三个数据中选择一个中间的数据作为关键值。此时我们需要实现一个三数取中的函数。int GetMidi(int* a, int left, int right) { int midi (left right) / 2; if (a[left] a[midi]) { if (a[midi] a[right]) { return midi; } else if (a[left] a[right]) { return right; } else { return left; } } else { if (a[midi] a[right]) { return midi; } else if (a[right] a[left]) { return right; } else { return left; } } }然后修改一下我们写好的快速排序算法void QuickSort(int* a, int left, int right) { if (left right) return; int midi GetMidi(a, left, right); Swap(a[left], a[midi]); int keyi left; int begin left, end right; while (begin end) { //右边找小的 while (begin end a[end] a[keyi]) { --end; } //左边找大的 while (begin end a[begin] a[keyi]) { begin; } Swap(a[begin], a[end]); } Swap(a[keyi], a[begin]); keyi begin; QuickSort(a, left, keyi - 1); QuickSort(a, keyi 1, right); }此时仍然有优化的空间。现在的快速排序算法用的是递归遍历递归到接近结束的时候假设一个小区间只有五个数那么仍然任然需要用6次递归使之有序非常浪费。刚才提快速排序的过程类似二叉树的递归遍历而二叉树仅最后一层的递归次数就占整体的50%最后三层的递归次数占整体的80%多。所以我们可以通过“小区间优化”在分出的区间足够小时改用插入排序就可以大幅减少递归的次数。void QuickSort(int* a, int left, int right) { if ((right - left 1) 10) { InsertSort(a left, right - left 1); //注意此处调用插入排序第一个参数应为a left } else { if (left right) return; int midi GetMidi(a, left, right); Swap(a[left], a[midi]); int keyi left; int begin left, end right; while (begin end) { //右边找小的 while (begin end a[end] a[keyi]) { --end; } //左边找大的 while (begin end a[begin] a[keyi]) { begin; } Swap(a[begin], a[end]); } Swap(a[keyi], a[begin]); keyi begin; QuickSort(a, left, keyi - 1); QuickSort(a, keyi 1, right); } }4.3 双指针版快速排序hoare版本的单趟排序不太好理解而双指针法好理解写起来也更简单效率并没有区别。用双指针法来实现快速排序的单趟排序就是定义两个指针prev和cur让prev从左端开始走cur从左端数的第二个位置开始走cur向前移动寻找比关键值小的数据没有找到就继续向前移动找到了就让prev然后交换prev和cur位置的数据一直到cur走到最右端为止。然后交换prev和最左端位置的数据就完成了单趟排序。把单趟排序的过程拎出来就是这样的int PartSort2(int* a, int left, int right) { //三数取中 int midi GetMidi(a, left, right); Swap(a[left], a[midi]); int keyi left; int prev left; int cur prev 1; while (cur right) { if (a[cur] a[keyi] prev ! cur) { Swap(a[prev], a[cur]); } cur; } Swap(a[prev], a[left]); return prev; }4.4 非递归版快速排序快速排序中每个递归调用的栈帧实际上主要用来记录区间。递归有栈溢出风险我们可以改用栈这种数据结构来存储区间的值实现非递归版本的快速排序。每次从栈顶取出一个区间单趟排序后将分出来的右、左区间压栈一直重复到栈为空为止就完成了排序。void QuickSortNonR(int* a,int left, int right) { ST st; STInit(st); STPush(st, right); STPush(st, left); while (!STEmpty(st)) { int begin STTop(st); STPop(st); int end STTop(st); STPop(st); int keyi PartSort2(a, begin, end); if (end keyi 1) { STPush(st, end); STPush(st, keyi 1); } if (keyi - 1 begin) { STPush(st, keyi - 1); STPush(st, begin); } } STDestroy(st); }4.5 三路划分版快速排序当数据中有大量重复数据时快速排序的性能会急剧下降。为了解决这个问题可以用三路划分的思路将数组分为严格小于关键值、等于关键值和大于关键值三部分。接下来只需要递归遍历严格小于和严格大于关键值的部分即可。具体的实现思路是用三个指针left从左开始移动right从右开始移动cur从左开始遍历数组。cur所在位置的值比关键值小时交换left和cur位置的值然后让left向右移动一位让cur向后移动一位如果cur所在位置的值等于关键值不进行交换操作直接让cur向后移动如果cur所在位置的值大于关键值交换cur和right位置的值让right向左移动一位。此时cur不必移动因为不确定新换到cur位置的值与关键值的大小关系需要重新进入判断语句进行判断。void QuickSort2(int* a, int begin, int end) { if (begin end) { return; } int key a[begin]; int left begin; int right end; int cur begin; while (cur right) { if (a[cur] key) { cur; } else if (a[cur] key) { Swap(a[cur], a[left]); left; cur; } else { Swap(a[cur], a[right]); right--; } } QuickSort2(a, begin, left - 1); QuickSort2(a, right 1, end); }五、归并排序5.1 递归版归并排序我们已经做过归并两个有序链表的问题当时我们用了两个指针分别从两个有序链表的第一个节点开始移动将两个指针指向的两个数据中小的那个插入新链表直到其中一个链表中的所有数据全部插入新链表中再把另一个链表中剩下的所有节点插入到新链表中。假设一个数组由两个已经有序的数组拼接而成我们就可以用类似的思路进行排序。然而数组是无序的。此时我们就可以用递归的方法将无序的数组继续拆成两个数组直到拆出的数组中只有一个数据就可以视为有序的了。每次拆分我们以 mid 左端下标右端下标/2 作为分界点将数组拆成[begin,mid] 和[mid 1, end]两部分。递归的终止条件是数组只有一个元素也就是左端点等于右端点。void _MergeSort(int* a, int* tmp, int begin, int end) { if (begin end) { return; } int mid (begin end) / 2; //[begin, mid][mid 1,end] _MergeSort(a, tmp, begin, mid); _MergeSort(a, tmp, mid 1, end); //归并 int begin1 begin, end1 mid; int begin2 mid 1, end2 end; int i begin; while (begin1end1 begin2end2) { if (a[begin1] a[begin2]) { tmp[i] a[begin1]; } else { tmp[i] a[begin2]; } } while (begin2 end2) { tmp[i] a[begin2]; } while (begin1 end1) { tmp[i] a[begin1]; } memcpy(abegin, tmpbegin, (end - begin 1) * sizeof(int)); } void MergeSort(int* a, int n) { int* tmp (int*)malloc(sizeof(int) * n); if (tmp NULL) { perror(malloc failed); return; } _MergeSort(a, tmp, 0, n - 1); free(tmp); tmp NULL; }归并的时间复杂度是O(N*logN)空间复杂度是O(N)。5.2 非递归版归并排序可以像快速排序一样用栈来模拟递归也可以直接用循环先让数据两个两个归并再四个四个归并再八个八个归并直到所有数据有序为止。我们将每次归并的数据个数设为gap。gap从1开始每次乘2。归并的逻辑和刚才一样只需要注意每个数组的起末位置不要写错即可。void MergeSortNonR(int* a, int n) { int* tmp (int*)malloc(sizeof(int) * n); if (tmp NULL) { perror(malloc failed); return; } int gap 1; while (gap n) { for (int i 0; i n; i gap * 2) { int cur i; int begin1 i, end1 i gap - 1; int begin2 i gap, end2 i 2 * gap - 1; while (begin1 end1 begin2 end2) { if (a[begin1] a[begin2]) { tmp[cur] a[begin1]; } else { tmp[cur] a[begin2]; } } while (begin2 end2) { tmp[cur] a[begin2]; } while (begin1 end1) { tmp[cur] a[begin1]; } memcpy(a i, tmp i, gap * 2 * sizeof(int)); } gap gap * 2; } free(tmp); tmp NULL; }此时我们还要解决一个越界的问题如果数组中数据个数不是2的幂次就会越界访问。越界分成三种情况1、只有end2越界2、begin2和end2越界3、end1、begin2、end2都越界。由于begin1和end2之间的数据一定是有序的begin2和end2之间的数据也一定是有序的所以上述的第2、3种情况都不需要处理而第一种情况只需要调整end2的值为n-1即可。void MergeSortNonR(int* a, int n) { int* tmp (int*)malloc(sizeof(int) * n); if (tmp NULL) { perror(malloc failed); return; } int gap 1; while (gap n) { for (int i 0; i n; i gap * 2) { int cur i; int begin1 i, end1 i gap - 1; int begin2 i gap, end2 i 2 * gap - 1; if (begin2 n) { break; } else if (end1 n) { end2 n - 1; } while (begin1 end1 begin2 end2) { if (a[begin1] a[begin2]) { tmp[cur] a[begin1]; } else { tmp[cur] a[begin2]; } } while (begin2 end2) { tmp[cur] a[begin2]; } while (begin1 end1) { tmp[cur] a[begin1]; } memcpy(a i, tmp i, gap * 2 * sizeof(int)); } gap gap * 2; } free(tmp); tmp NULL; }5.3 归并排序实现外排序当要排序的数据非常多而内存有限时就可以采用外排序。比如我们现在创建一个有一千万个随机数的数据文件void CreateData() { int n 10000000; srand(time(0)); const char* file data.txt; FILE* fin fopen(file, w); if (fin NULL) { perror(fopen failed); return; } for (int i 0; i n; i) { int x rand() 1; fprintf(fin, %d\n, x); } fclose(fin); }我们可以用归并排序的思路来实现外排序。我们可以先从从文件中读取100000个数用C语言库中的qsort排序后放入file1文件中。再读取100000个数排序后放入file2文件中。用归并排序将这200000个数据归并到mfile中。然后删除file1和file2将mfile重命名为file1然后再从数据文件中读取100000个数据放入新的file2中再次进行归并......直到所有数据都被排序此时的排序结果就存在file1中。void FileSort() { CreateData(); const char* file data.txt; const char* file1 file1.txt; const char* file2 file2.txt; const char* mfile mfile.txt; FILE* fout fopen(file, r); if (fout NULL) { perror(fopen failed); return; } int m 1000000; ReadNDataSortToFile(fout, m, file1); ReadNDataSortToFile(fout, m, file2); while (true) { MergeFile(file1, file2, mfile); remove(file1); remove(file2); rename(mfile, file1); int n 0; n ReadNDataSortToFile(fout, m, file2); if (n 0) break; if (n 100) { int x 0; } } }整体的框架有了。接下来我们需要实现ReadNDataSortToFile和MergeFile的具体逻辑。先看ReadNDataSortToFile传数据文件的句柄作为参数将数据文件中的100000个数据读取后放到malloc开辟的数组中用qsort进行排序需要自己写比较函数然后放入指定文件中。因为要处理数据个数不是100000的整数倍的情况所以用变量j记录成功读取的数据个数排序时排j个数据。如果刚开始就读到了EOF说明数据文件已经读完了直接返回0。外部得到返回值为0时也终止循环。int compare(const void* a, const void* b) { return (*(int*)a - *(int*)b); } int ReadNDataSortToFile(FILE* fout, int n, const char* file1) { int x 0; int* a malloc(sizeof(int) * n); if (a NULL) { perror(malloc failed); return; } int j 0; for (int i 0; i n; i) { if (fscanf(fout, %d, x) EOF) break; a[j] x; } if (j 0) { free(a); return 0; } qsort(a, j, sizeof(int), compare); FILE* fin fopen(file1, w); if (fin NULL) { perror(fopen failed); return; } for (int i 0; i j; i) { fprintf(fin, %d\n, a[i]); } fclose(fin); free(a); return j; }MergeFile的逻辑就是归并排序。void MergeFile(const char* file1, const char* file2, const char* mfile) { FILE* fout1 fopen(file1, r); if (fout1 NULL) { perror(fopen failed); return; } FILE* fout2 fopen(file2, r); if (fout2 NULL) { perror(fopen failed); return; } FILE* mfin fopen(mfile, w); if (mfin NULL) { perror(fopen failed); return; } int x1 0; int x2 0; int ret1 fscanf(fout1, %d, x1); int ret2 fscanf(fout2, %d, x2); while (ret1 ! EOF ret2 ! EOF) { if (x1 x2) { fprintf(mfin, %d\n, x1); ret1 fscanf(fout1, %d, x1); } else { fprintf(mfin, %d\n, x2); ret2 fscanf(fout2, %d, x2); } } while (ret1 ! EOF) { fprintf(mfin, %d\n, x1); ret1 fscanf(fout1, %d, x1); } while (ret2 ! EOF) { fprintf(mfin, %d\n, x2); ret2 fscanf(fout2, %d, x2); } fclose(fout1); fclose(fout2); fclose(mfin); }六、计数排序计数排序是一种非比较排序它利用了数组下标天然有序的特点进行排序。它的核心思想是进行一次遍历找出数组中最大和最小的数进而算出所有数据的范围然后开辟一个大小恰好等于这个范围的count数组这样所有的数据都和count数组的下标有了映射关系。再次遍历数组每读取一个数据就让count数组中对应下标位置的数据1。最后遍历count数组每个下标位置的数据是几就往原来数组中放入几个对应数据。void CountSort(int* a, int n) { int min a[0]; int max a[0]; for (int i 0; i n; i) { if (a[i] min) { min a[i]; } if (a[i] max) { max a[i]; } } int range max - min 1; int* count (int*)calloc(range, sizeof(int)); if (count NULL) { perror(calloc failed); return; } //统计次数 for (int i 0; i n; i) { count[a[i] - min]; } //排序 int j 0; for (int i 0; i range; i) { while (count[i]--) { a[j] i min; } } }计数排序只适用于整数的排序适合处理范围比较集中的数据的排序。时间复杂度是O(Nrange)。七、排序算法的性能比较7.1 稳定性稳定性指的是排序后相同的值相对顺序不变的性能。在结构体排序中这个性能就很重要。直接插入排序稳定不改变相同值的相对位置希尔排序不稳定相同的数据在预排序时可能被分到不同的组里选择排序不稳定排序过程中有交换数据位置的操作堆排序不稳定排序过程中有交换数据位置的操作冒泡排序稳定不改变相同值的相对位置快速排序不稳定会交换数据位置归并排序稳定不改变相同值的相对位置7.2 时间复杂度和空间复杂度算法时间复杂度空间复杂度直接插入排序O(N^2)O(1)希尔排序O(N^1.3)O(1)选择排序O(N^2)O(1)堆排序O(N*logN)O(1)冒泡排序O(N^2)O(1)快速排序O(N*logN)O(logN)归并排序O(N*logN)O(N)END