【数据结构】 常见的八大排序算法

 代码实现：

void Bubblesort(int* a, int n){for (int i = 0; i < n; i++)//遍历次数{for (int j = 0; j < n - i - 1; j++)//向后冒泡 ,控制边界 {if (a[j] > a[j + 1])//如果前一个值大于后一个值,交换. {swap(&a[j], &a[j + 1]);}}}}//优化void BubbleSort(int* a, int n){for (int j = 0; j < n; ++j){int exchange = 0;for (int i = 1; i < n-j; ++i){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}// 一趟冒泡过程中，没有发生交换，说明已经有序了，不需要再处理if (exchange == 0){break;}}}

相关分析：

我们可以做一个简单的优化，如果我们排序的某一趟每个元素都不用交换，则说明要排序的元素已经有序，那么后面的排序就可以直接跳出循环了。

2、快速排序

2.1 hoare版本

基本思想：

我们将左边值设为key,然后右边right先走,找小的,比key小停下来,然后左边left走找比key大,然后交换左边右边，继续上述过程，直至left和right相遇，此时的值一定是比key小的值，我们再把key和这个相遇位置的值进行交换，此时key所在的位置，左边的数据一定比key值小，右边的数据一定比key值大，即key放到了合适的位置上。重复此过程进行递归，直至所有的元素都处在合适位置。

动图展示：

 代码实现：

int HoareSort(int* arr, int left, int right){int key = left; //我们默认key为左边值while (left < right){while (left < right && arr[right] >= arr[key]) //找小{right--;}while (left < right && arr[left] <= arr[key]) //找大{left++;}Swap(&arr[left], &arr[right]);}Swap(&arr[key], &arr[left]);key = left;return key; }void QuickSort(int* arr, int begin, int end)  //快排hoare版{if (begin >= end)//递归结束条件{return;}int key = HoareSort(arr, begin, end);QuickSort(arr, begin, key - 1); //递归key左边数组排序QuickSort(arr, key + 1, end); //递归key右边数组排序}

相关分析：

Hoare版本的快排需要注意的地方挺多的：

如果key后面的每个数都比key小或大的话，那left向后面找或right向前面找，会产生越界访问的问题，所以我们选择在if语句的判断部分逻辑与&&保证left小于right，以免产生越界访问的问题。 在if语句的判断部分，找的数据一定得比key小或大的。因为若相等会产生死循环。

对次的优化： 

我们可以对key值的选取进行优化，采用三数取中法让我们选取的key数据在序列中的位置尽量靠中间，以提高递归的效率。同时，递归建立的栈帧数量会随着递归深度的增加而增加，为了避免递归深度太深，造成栈溢出的问题。我们采用小区间优化，当递归区间的数据量较小的时候，采用直接插入法进行排序。

相关代码：

//三数取中int GetMidIndex(int *arr, int begin, int end){int mid = (begin + end) / 2;if (arr[begin] > arr[end]){if (arr[end] > arr[mid]){return end;}else if (arr[begin] < arr[mid]){return begin;}else{return mid;}}else// arr[begin] < arr[end]{if (arr[mid] < arr[begin]){return begin;}else if (arr[end] > arr[mid]){return mid;}else{return end;}}}

//对小区间优化void QuickSort(int* arr, int begin, int end){if ((end - begin) < 1)//递归结束条件{return;}if ((end - begin + 1) < 15){InsertSort(arr + begin, end - begin + 1);}else{int key = PartSort1(arr, begin, end);QuickSort(arr, begin, key - 1);QuickSort(arr, key + 1, end);}}

2.2 挖坑法

基本思想：

挖坑法对hoare的思想进行了优化。我们设定key数组左边第一个值为坑,右边right找小,找到比key小的值填到坑位，right就成为新的坑位，然后左边left找大,找到后填到坑位上,left此时更新为新的坑位,循环此过程，right接着找小，left找大，交换形成新的坑位，直至left和right相遇。最后把key放到坑里，即类似于hoare版本key应处于的位置。

动图展示：

代码实现： 

int QuickSort2(int* arr, int left, int right) //快速排序挖坑法{int mid = GetMidIndex(arr, left, right); //三数取中Swap(&arr[left], &arr[mid]);使中间值永远在最左，便于决定谁先走int hole = left; //对key值保存int key = arr[left];//保存坑位下标while (left < right){while (left < right && arr[right] >= key) //右边找小{--right;}arr[hole] = arr[right]; //填坑hole = right;while (left < right && arr[left] <= key) //左边找大{++left;}arr[hole] = arr[left];//填坑hole = left;}arr[hole] = key; //相遇时return hole;}

相关分析：

需要进行坑位的位置更新

2.3 前后指针法

基本思想：

我们定义两个指针cur和prev，选取key值,cur去遍历小于key的值,对prev++,交换cur与prev值,直至cur遍历完整个数组，prev位置的值一定是比key值小的，即key应处的正确位置

动图展示：

 代码实现：

int QuickSort3(int* arr, int left, int right) //前后指针版{int mid = GetMidIndex(arr, left, right);Swap(&arr[left], &arr[mid]);int key = left; int prev = left, cur = left + 1; //初始化前后指针while (cur <= right){if (arr[cur] < arr[key] && ++prev != cur)//逻辑与防止交换同一个位置的元素{Swap(&arr[cur], &arr[++prev]);}cur++;}Swap(&arr[key], &arr[prev]);//遍历结束将key值放在定位点return prev;}

相关分析：

++prev!=cur 是对防止同一位置元素进行交换的简单优化，实际中，前后指针法推荐掌握，简单理解易于操控。

对前后指针法的优化：

在数据量极大的情况下，会出现很多相同的数据，此时进行快排，会建立很多栈帧，造成递归深度太深，运行时间过长，对于那些相同的数据我们采用三指针法进行优化

我们定义left，right，cur三个下标，利用cur对序列的遍历，找出大于key，等于key，小于key的三种值，将他们交换到left和right下标位置，将等于key值的数据集中到数组区间中部，然后继续递归剩余的左右区间，直至排序完成。

相关代码： 

void _QuickSort3(int* arr, int begin, int end) //前后指针法优化：三指针法{if (begin >= end){return;}if ((end - begin + 1) < 15){InsertSort(arr + begin, end - begin + 1);}else{int mid = GetMidIndex(arr, begin, end);Swap(&arr[begin], &arr[mid]);int key = arr[begin];int left = begin, right = end, cur = begin + 1;while (cur <= right){if (arr[cur] < key){Swap(&arr[left], &arr[cur]);left++;cur++;}else if (arr[cur] > key){Swap(&arr[cur], &arr[right]);right--;}else//arr[cur]==key时{cur++;}}QuickSortPlus(arr, begin, left - 1);QuickSortPlus(arr, right + 1, end);}}

2.4 快排非递归版

基本思想：

对于非递归版的实现，因为递归函数在内存实际上是在栈中进行开辟函数栈帧，延用递归中的思想，这里我们采用数据结构中的栈来模拟内存中的栈，从而实现快排的非递归。

代码实现：

void QuickSortNonR(int* arr, int begin, int end) // 快速排序 非递归实现{ST st; //首先构建一个栈StackInit(&st);StackPush(&st, begin); //将左右区间入栈StackPush(&st, end);while (!StackEmpty(&st)){int right = StackTop(&st);StackPop(&st);int left = StackTop(&st);StackPop(&st);int key = QuickSort3(arr, left, right); //排序：利用上面的前后指针法进行排序// [begin,key-1]  [key+1,end]if (key + 1 < right)//key+1==right说明区间只剩一个值时，则可以认为有序{StackPush(&st, key + 1);StackPush(&st, right);}if (left < key - 1){StackPush(&st, left);StackPush(&st, key - 1);}}StackDestroy(&st); //栈销毁}

四、归并排序

1、归并排序递归版

基本思想：

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。通过递归实现对小数组有序,再返回回来。

动图展示:

 代码实现：

void _MergeSort(int* arr, int begin, int end, int* tmp) //归并排序{if (begin >= end) //只有一个元素或没有元素为有序{return;}int mid = (begin + end) / 2;_MergeSort(arr, begin, mid, tmp);_MergeSort(arr, mid + 1, end, tmp);//左区间和右区间有序后开始归并int i = begin;int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] <= arr[begin2])//升序{tmp[i++] = arr[begin1++];}else{tmp[i++] = arr[begin2++];}}while (begin1 <= end1){tmp[i++] = arr[begin1++];}while (begin2 <= end2){tmp[i++] = arr[begin2++];}memcpy(arr + begin, tmp + begin, sizeof(int) * (end - begin + 1));//拷贝回数组arr}void MergeSort(int* arr, int begin, int end){int* tmp = (int*)malloc(sizeof(int) * (end - begin));//创建暂存数据数组，以保存归并好的数据_MergeSort(arr, begin, end - 1, tmp);free(tmp);//释放tmp = NULL;}

相关分析：

归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。

2、递归排序非递归版

基本思想：

因为递归实现过程就是分治,只不过非递归不用递归返回,我们可以不借助其他数据结构，直接对序列进行归并排序，这里主要采用循环：

void MergeSortNonR(int* a, int n) //归并排序非递归版{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");exit(-1);}int gap = 1;//定义数组归并距离//（初始gap为1即每个数组只有一个元素，此时每个数组都为有序数组）while (gap < n)//归并趟次{for (int i = 0; i < n; i += gap * 2)//分组归并{//划分区间int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;//判断越界的情况//这种情况不用考虑归并（已经有序）if (end1 >= n || begin2 >= n){break;}//这种情况需要归并if (end2 >= n){end2 = n - 1;}//归并int p = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[p++] = a[begin1++];}else{tmp[p++] = a[begin2++];}}while (begin1 <= end1){tmp[p++] = a[begin1++];}while (begin2 <= end2){tmp[p++] = a[begin2++];}//拷贝排序后数据到原数组for (int j = i; j <= end2; j++){a[j] = tmp[j];}}gap *= 2;}free(tmp);//释放tmp = NULL;}

相关分析：

对于越界情况我们可以直接break掉，拷贝的时候我们只能在for循环里面进行拷贝，也就是部分拷贝，防止在for循环外面进行拷贝的话，arr中会出现随机值的情况。

五、计数排序 - 非比较排序

计数排序基本思想：

动图展示： 

%20%20%20%20%20

 代码实现：

void%20CountSort(int*%20a,%20int%20n)%20//计数排序{//遍历找出数组最大最小值（算出范围）int%20max%20=%20a[0],%20min%20=%20a[0];for%20(int%20i%20=%201;%20i%20<%20n;%20i++){if%20(a[i]%20>%20max)max%20=%20a[i];if%20(a[i]%20<%20min)min%20=%20a[i];}int%20range%20=%20max%20-%20min%20+%201;//开辟对应长度个计数数组int*%20count%20=%20(int*)malloc(sizeof(int)%20*%20range);if%20(count%20==%20NULL){perror("malloc%20fail");exit(-1);}//初始化数组计数为0memset(count,%200,%20sizeof(int)%20*%20range);//遍历计数据出现次数for%20(int%20i%20=%200;%20i%20<%20n;%20i++){count[a[i]%20-%20min]++;//a[i]%20-%20min：数据与下标构成的相对映射关系}//排入原数组int%20p%20=%200;for%20(int%20i%20=%200;%20i%20<%20range;%20i++){while%20(count[i]--){a[p++]%20=%20i%20+%20min;}}free(count);//释放内存count%20=%20NULL;}

相关分析：

在数据较为集中的情况下，计数排序的性能是很好的，因为N大于range的话，其时间复杂度就是O(N)。缺点是：1、适用于数据集中的情况，数据分散会浪费空间%202、只适用于整型数据的排序

%20六、对排序的分析总结%20什么是排序的稳定性： %20

如果在某个排序算法在排序过程中，没有打乱原有序列中相同数据的相对位置关系，我们就称这个算法是稳定的。

像是希尔排序，相同的数据可能被预排序到不同的组，不能保证排序的稳定性；像是冒泡排序是从左到右进行比较排序，相同数据的相对位置关系不会发生改变，因此排序是稳定的。