【排序算法】

排序算法

• 前言
• 一、排序算法的分类
• 二、选择排序
• 三、冒泡排序
• 四、直接插入排序
• 五、堆排序
• 六、快速排序
• • 1.hoare版本
  • 2.前后指针
• 七、归并排序
• 八、希尔排序
• 总结

前言

排序算法有很多种，其中最重要的当属快速排序。

一、排序算法的分类

排序算法种类繁多，主要以下几大类：

1. 交换排序

   冒泡排序、快速排序

2. 插入排序

3. 直接插入排序、希尔排序

4. 选择排序

5. 选择排序、堆排序

6. 归并排序

   归并排序

除此之外，还有记数排序、桶排序等。

我将由简到难依次说明。
查看各个排序算法(除堆排序)动态演示效果

二、选择排序

选择排序就是每次从左到右遍历在数据中选出最值，放到数据的头部或尾部。

具体实现：

#include//选择排序void Swap(int* p1, int* p2){int tmp = *p1;*p1 = *p2;*p2 = tmp;}void Selection_Sort1(int* a, int n){int bigin = 0;int min = 0;while (bigin < n-1){for (int i = bigin+1; i < n; i++){if (a[min] > a[i])min = i;}Swap(a + min, a + bigin);bigin++;}}

当然，我们还可以改成一次遍历找出两个最值，再分别放入对应位置。
具体实现：

void Swap(int* p1, int* p2){int tmp = *p1;*p1 = *p2;*p2 = tmp;}void Selection_Sort2(int* a, int n){int bigin = 0;int end = n - 1;int min = 0;int max = 0;while (bigin<end){for (int i = 1; i <=end; i++){if (a[min] > a[i])min = i;if (a[max] < a[i])max = i;}Swap(a + min, a + bigin);if (max == bigin)max = min;Swap(a + end, a + max);bigin++;end--;}}

三、冒泡排序

冒泡排序是C语言学习初期常常使用或出现的排序算法，因为它较容易理解，就是将数据从左往右两两比较，大的数据发放到小数据后面，每次遍历都能找到最大值。

具体实现：

// 冒泡排序void BubbleSort(int* a, int n){for (int j = 1; j < n; j++){int count = 0;for (int i = 1; i < n; i++){if (a[i - 1] > a[i]){count++;Swap(&a[i - 1], &a[i]);}}if (count == 0)break;}}

四、直接插入排序

直接插入排序就是将总数据的第一个数据当作一个有序数组，从该数据的后面开始，将数据插入到这个有序数组的合理位置，直到全部数据插入完毕。
具体实现：

//插入排序void InsertSort(int* arr, int sz){for (int i = 0; i < sz-1; i++){int end = i;int tmp = arr[end+1];while (end >= 0){if (arr[end] > tmp){arr[end+1] = arr[end];end--;}elsebreak;}arr[end+1] = tmp;}}

五、堆排序

堆排序参考——二叉树和堆中堆排序内容。
具体实现：

//向下调整算法void Heap_Dowm(int* a,int sz,int parent){if (a == NULL)return;int child = 2 * parent + 1;while (child<sz){if (a[child] > a[child + 1]&&child+1<sz)child++;if (a[parent] > a[child]){Swap(&a[child], &a[parent]);parent = child;child = 2 * parent + 1;}elsebreak;}}//堆排序void Heap_Sort(int* a, int sz){if (a == NULL)return;int parent = (sz - 1 - 1) / 2;for(int i=parent;i>=0;i--)//for (int i = 0; i <sz; i++){Heap_Dowm(a, sz, i);}while (sz>0){Swap(a, &a[sz - 1]);sz--;Heap_Dowm(a, sz, 0);}}

六、快速排序

快速排序的思想有很多种版本：hoare版本、前后指针、挖坑法

1.hoare版本

如图所示，R先出发从右往左寻找比key所指向的数小的数；L在R找到符合要求的数后再出发从右往左寻找比key所指向的数大的数，在L也找到符合要求的数后，将R和L所指向的值进行交换，重复这一过程直到R和L相遇，此时将相遇时所指向的值与key所指向的值进行交换，就能做到key左边的数都比key所指向的数小，而右边的数都比key所指向的数大，同时key走到了有序的位置上，这样就完成了一次的处理。之后以key为界，将数据当做两个数组进行跟前面一样的处理，最终就能做到升序排序。

具体实现：(其中三数取中和小区间优化属于快排算法的优化内容，可以不要)

// 三数取中int QuickSort_Mid(int* a,int begin, int end){int mid = (begin + end) / 2;if (a[begin] < a[mid]){if (a[begin] > a[end])returnbegin;if (a[mid] > a[end])return end;elsereturnmid;}else{if (a[mid] > a[end])return mid;if (a[begin] > a[end])return end;elsereturn begin;}}// 快速排序hoare版本int PartSort1(int* a, int left, int right){int begin = left;int end = right;//三项取中int mid= QuickSort_Mid(a, begin, end);Swap(&a[left], &a[mid]);int key = left;while (begin < end){while (a[end] >= a[key]&& begin < end)end--;while (a[begin] <= a[key] && begin < end)begin++;if(begin<end)Swap(&a[begin], &a[end]);}Swap(&a[begin], &a[key]);return begin;}void QuickSort(int* a, int left, int right){if (left >= right)return;//小区间优化if (right - left < 5){InsertSort(a + left, right - left + 1);//使用插入排序return;}int key = PartSort1(a, left, right);//int key = PartSort3(a, left, right);//[left,key-1] key [key+1,right]QuickSort(a, left, key - 1);QuickSort(a, key + 1, right);}

2.前后指针

前后指针相对更容易理解。
初始状态如图：

如图，cur每次将自身对应的值和key所指向的值进行比较再向右行动一格，若比较结果为cur小，则prev也跟着向右动一格：反之则不动，直到cur走出数组时，将prev所对应的值与key所对应的值进行交换，就能做到key左边的数都比key所指向的数小，而右边的数都比key所指向的数大，同时key走到了有序的位置上，这样就完成了一次的处理。之后以key为界，将数据当做两个数组进行跟前面一样的处理，最终就能做到升序排序。

具体实现：(其中三数取中和小区间优化属于快排算法的优化内容，可以不要)

// 三数取中int QuickSort_Mid(int* a,int begin, int end){int mid = (begin + end) / 2;if (a[begin] < a[mid]){if (a[begin] > a[end])returnbegin;if (a[mid] > a[end])return end;elsereturnmid;}else{if (a[mid] > a[end])return mid;if (a[begin] > a[end])return end;elsereturn begin;}}// 快速排序前后指针法int PartSort3(int* a, int left, int right){int prev = left;int cur = left + 1;//三项取中int mid= QuickSort_Mid(a, left, right);Swap(&a[left], &a[mid]);int key = left;while (cur <= right){if (a[cur] < a[key]&&++prev!=cur){Swap(&a[prev], &a[cur]);}cur++;}Swap(&a[key], &a[prev]);return prev;}void QuickSort(int* a, int left, int right){if (left >= right)return;//小区间优化if (right - left < 5){InsertSort(a + left, right - left + 1);//使用插入排序return;}//int key = PartSort1(a, left, right);int key = PartSort3(a, left, right);//[left,key-1] key [key+1,right]QuickSort(a, left, key - 1);QuickSort(a, key + 1, right);}

七、归并排序

归并排序这里就只说明思想：

如图所示，归并排序就是将一个数组进行反复拆分直到有序，再重新建立一个数组将这些被拆成有序的数组进行合并。(注意：只是逻辑上的拆分)

八、希尔排序

希尔排序是将数组在逻辑上进行(每隔gap个位置归为一组)分组，再将它们分别做直接插入排序处理，再将gap/3+1，重复上述过程，直到gap为1时，数据就为有序排列了。
因为希尔排序是直接插入排序上的优化，所以可以将其和直接插入排序放一起进行理解。

具体实现：

//希尔排序void ShellSort(int* a, int sz){int gap = sz;while (gap > 1){gap = gap / 3 + 1;for (int j = 0; j < gap; j++){for (int i = j; i < sz - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}elsebreak;}a[end + gap] = tmp;}}}}

总结

排序算法种类繁多，建议本篇所说的几种都最好能实现一下，尤其是快速排序。

中文学习资料