排序算法排序算法

前言算法是一门十分重要的必修课，近来有些空余时间，故温习一下几种排序算法，希望也对你有益。
环境： MinGW w64 6.0 / C99 / CLion 2018.1
排序算法共用部分

#include typedef struct { int len; int *ary; } array; void vSwap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

冒泡排序从左到右，两两比较，

array tBubbleSort(array tAry) { for (int i = 0; i < tAry.len; i++) { for (int j = 1; j < tAry.len - i; j++) { if (tAry.ary[j - 1] > tAry.ary[j]) { vSwap(tAry.ary + (j - 1), tAry.ary + j); } } } return tAry; }

插入排序

直接插入

array tInsertionSort(array tAry) { for (int i = 1; i < tAry.len; i++) { for (int j = i; j >= 1; j--) { if (tAry.ary[j - 1] > tAry.ary[j]) { vSwap(tAry.ary + (j - 1), tAry.ary + j); } else { break; } } } return tAry; }

二分插入

array tBinaryInsertionSort(array tAry) { for (int i = 0; i < tAry.len; i++) { int st = 0, ed = i; while (st != ed) { int j = (st + ed) / 2; if (tAry.ary[i] > tAry.ary[j]) { st = j += (st == j); } else { ed = j; } } for (int now = i; now > st; now--) { vSwap(tAry.ary + now, tAry.ary + (now - 1)); } } return tAry; }

选择排序

简单选择

array tSelectSort(array tAry) { for (int i = 0; i < tAry.len; i++) { for (int j = i; j < tAry.len; j++) { if (tAry.ary[j] < tAry.ary[i]) { vSwap(tAry.ary + i, tAry.ary + j); } } } return tAry; }

优化选择

array tSelectSortPlus(array tAry) { for (int i = 0; i < tAry.len / 2; i++) { for (int st = i, ed = tAry.len - i - 1; st <= ed; st++) { if (tAry.ary[st] < tAry.ary[i]) { vSwap(tAry.ary + st, tAry.ary + i); } if (tAry.ary[st] > tAry.ary[ed]) { vSwap(tAry.ary + st, tAry.ary + ed); } } } return tAry; }

希尔排序

array tShellSort(array tAry) { int step = tAry.len; while (step > 1) { step = step / 3 + 1; for (int i = step; i < tAry.len; i++) { int j = i - step, k = tAry.ary[i]; while (j >= 0) { if (k < tAry.ary[j]) vSwap(tAry.ary + j, tAry.ary + j + step); j = j - step; } } } return tAry; }

快速排序分享一个关于快速排序的演示视频，可以帮助理解。

void vQuickSortSubFun(int *ary, int low, int high) { if (high <= low) return; int lowRaw = low, highRaw = high; int temp = ary[low]; while (low < high) { while (low < high) { if (temp > ary[high]) { ary[low] = ary[high]; break; } high--; } while (low < high) { if (ary[low] > temp) { ary[high] = ary[low]; break; } low++; } } ary[low] = temp; vQuickSortSubFun(ary, lowRaw, low - 1); vQuickSortSubFun(ary, low + 1, highRaw); }array tQuickSort(array tAry) { vQuickSortSubFun(tAry.ary, 0, tAry.len - 1); return tAry; }

堆排序 【排序算法】不是真的去构造二叉树，算法在于意而不在于形。
节点的两个子节点是和
我网上找到一张动图，可以帮助理解。

堆排序 gif

array tHeapSort(array tAry) { for (int last = tAry.len; last > 1; last--) { int *ary = tAry.ary; if (last % 2 == 0) { if (ary[last - 1] > ary[last / 2 - 1]) vSwap(ary + (last - 1), ary + (last / 2 - 1)); } for (int cur = last % 2 == 0 ? (last - 1) / 2 : last / 2; cur > 0; cur--) { if (ary[cur - 1] < ary[cur * 2 - 1]) {//比较左节点 vSwap(ary + (cur - 1), ary + (cur * 2 - 1)); } if (ary[cur - 1] < ary[cur * 2]) {//比较右节点 vSwap(ary + (cur - 1), ary + (cur * 2)); } } vSwap(ary + 0, ary + (last - 1)); } return tAry; }

归并排序合并时是先复制两个子数组，在往目标数组里顺序放置元素。

void vMerge(int *ary, int left, int centre, int right) { int lLen = centre - left + 1; int rLen = right - centre; int *lAry = (int *) malloc(sizeof(int) * lLen); int *rAry = (int *) malloc(sizeof(int) * rLen); for (int tm = 0; tm < lLen; tm++) { lAry[tm] = ary[left + tm]; } for (int i = 0; i < rLen; i++) { rAry[i] = ary[centre + 1 + i]; } int lFlag = 0, rFlag = 0, curFlag = left; while (1) { if (lFlag < lLen && rFlag < rLen) { if (lAry[lFlag] <= rAry[rFlag]) { ary[curFlag] = lAry[lFlag]; lFlag++; curFlag++; } else { ary[curFlag] = rAry[rFlag]; rFlag++; curFlag++; } } else if (lFlag >= lLen) { ary[curFlag] = rAry[rFlag]; rFlag++; curFlag++; } else { ary[curFlag] = lAry[lFlag]; lFlag++; curFlag++; } if (curFlag > right) break; } }void vMergeSortSubFun(int *arr, int left, int right) { if (right <= left) return; int centre = (left + right) / 2; vMergeSortSubFun(arr, left, centre); vMergeSortSubFun(arr, centre + 1, right); vMerge(arr, left, centre, right); }array tMergeSort(array tAry) { vMergeSortSubFun(tAry.ary, 0, tAry.len - 1); return tAry; }

测试正确性

#include #include #include #include //创建数值和长度随机的数组 array tCreateRandomAry() { int aryLenMax = 20, numMax = 100; int aryLen = rand() % aryLenMax; int *ary = (int *) malloc(sizeof(int) * aryLen); for (int i = 0; i < aryLen; i++) { ary[i] = rand() % (numMax + 1); } array tAry; tAry.len = aryLen; tAry.ary = ary; return tAry; }//测试排序函数正确性（升序） bool bVerifySortFunc(array (*sort)(array), array tAry) { array tResult = sort(tAry); for (int i = 1; i < tResult.len; i++) { if (tResult.ary[i - 1] > tResult.ary[i]) return false; } return true; }//批量测试 void test(array (*sort)(array), char *description) { int m = 0; //错误标记 int t = 1000; //测试次数 for (int i = 0; i < t; i++) { if (!bVerifySortFunc(sort, tCreateRandomAry())) { m = 1; break; } } if (m) printf("%s: Error\n", description); else printf("%s: OK\n", description); }int main() { srand((unsigned int) time(NULL)); test(tBubbleSort,"冒泡排序"); test(tInsertionSort,"插入排序"); test(tBinaryInsertionSort,"二分排序"); test(tSelectSort,"选择排序"); test(tSelectSortPlus,"优化选择排序"); test(tShellSort,"希尔排序"); test(tQuickSort,"快速排序"); test(tHeapSort,"堆排序"); test(tMergeSort,"归并排序"); return 0; }

结束以上，纰漏之处请指正。
图片如有侵权请告知，将尽快删除。