【数据结构入门】排序算法之交换排序与归并排序

前言

在前一篇博客，我们学习了算法>排序算法中的插入排序和选择排序，接下来我们将继续探索交换排序与归并排序，这两个排序都是重头戏，让我们接着往下看。

一、交换排序

1.1 冒泡排序

冒泡排序是一种简单的算法>排序算法。

1.1.1 基本思想

它的基本思想是通过相邻元素的比较和交换，让较大的元素逐渐向右移动，从而将最大的元素移动到最右边。

动画演示：

1.1.2 具体步骤

从列表的第一个元素开始，重复进行以下步骤，直到最后一个元素：
- 遍历列表中的每一个相邻的元素。
- 如果相邻元素的顺序错误（较大的元素在前），则交换它们的位置。
重复上述步骤，直到列表中的所有元素都按照从小到大的顺序排列。

1.1.3 算法特性

冒泡排序是一种非常容易理解的排序
时间复杂度：O(N^2) ，其中n是列表的长度。因为算法需要对列表中的每个元素进行多次比较和交换操作。
空间复杂度：O(1)
稳定性：稳定

1.1.4 算法实现

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

1.2 快速排序

快速排序是一种常用的算法>排序算法。

1.2.1 基本思想

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

注意：

由于选取基准值是任意的，所以会有多种实现方式，每种方式最后的结果也不尽相同。

一般实现的大思路主要有三种：

1.hoare版本（左右指针法）

注意事项：

左边做key，右边先走；右边做key，左边先走。这样能够保证两个指针相遇时，以左边为key，相遇位置比key小正好可以交换；以右边为key时，相遇的位置比key大，正好可以交换。

原理如下：

以左边为例：

1.R找小，L找大没有找到，L遇到R

2.R找小，没有找到，直接遇到L，要么就是一个比key小的位置或者直接到keyi

类似的，右边做key，左边先走，相遇的位置就比key要大。

2.挖坑版本

3.前后指针版本

实现思路：

1.cur找到比key小的值，++prev， cur与prev位置的值交换，++cur；

2.cur找到比key大的值，++cur；

方法：

1.a[cur] < key , 交换left 和 cur 数据， left++, cur++;

2.a[cur] == key, cur++;

3.a[cur] > key, 交换cur 和 right数据， right++；

4.cur > right 结束

核心思想：

1.与key相等的值，往后推

2.比key小的值，往前甩

3.比key大的值，往后甩

4.与key相等的就在中间

1.2.2 具体步骤

选择列表中的一个元素作为基准值（pivot），一般选择列表的第一个元素。
遍历列表，将比基准值小的元素放到基准值的左边，将比基准值大的元素放到基准值的右边。
将基准值放到它最终的位置上，即左边的元素都比它小，右边的元素都比它大。
对基准值左边和右边的子列表，分别进行递归快速排序。

1.2.3 算法特性

快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
时间复杂度：O(N*logN)（经过优化后），在最坏情况下，快速排序的时间复杂度为O(n^2)，但是通过一些优化技巧，可以将其降低到O(nlogn)。快速排序是一种原地算法>排序算法，即不需要额外的空间来存储排序结果。
空间复杂度：O(logN)
稳定性：不稳定

1.2.4 算法实现

在算法整体实现之前我们需要考虑一下快速算法>排序算法的特殊性：

这个算法利用了分治的思想，理想的状态下，从中间分开，时间复杂度大大降低，如果每次选key都正好选到中间值，那么完全可以达到 $\log (n)$ ；

但是要是key选的不好，假如说选到最小值或最大值，那么这个排序的效率就会大打折扣，不如直接使用插入排序。

所以，不能简单的直接取左边的数或者右边的数，这样很容易造成key的选择不好，降低效率。

好用的方法有两个：

1. 随机选key

这种方式使用随机在数中选key的方式，来选择key，降低了选到最大或者最小值的概率。

srand((unsigned int)time(NULL));void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}int randi = left + (rand() % (right - left));
swap(&a[left], &a[randi]);

2.三数取中法

这种方法使用的较为普遍，通过选择三个数中中间的一个数来定key，在数据没有大量重复的情况下，对提高算法效率有很大帮助。

这里其实留下了一个坑，当数据大量重复时，快速排序的效率会降到Nlog(N)，如何解决这个问题，可以等等下一篇博客，会介绍三路划分优化快速算法>排序算法。

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//三数取中，有序情况下最快
int GetMidNumi(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[mid] > a[left]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else //a[mid] <= a[left]{if (a[right] < a[mid]){return mid;}else if (a[right] > a[left]){return left;}else{return right;}}
}int midi = GetMidNumi(a, left, right);
Swap(&a[left], &a[midi]);

1）hoare版本（左右指针法）

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//三数取中，有序情况下最快
int GetMidNumi(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[mid] > a[left]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else //a[mid] <= a[left]{if (a[right] < a[mid]){return mid;}else if (a[right] > a[left]){return left;}else{return right;}}
}
//hoare版本
int PartSort1(int* a, int left, int right)
{//优化：三数取中int midi = GetMidNumi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;//这地方left 不能先+1，否则最后一步交换会出问题while (left < right){//右边先找小//注意内部没有判断left< rightwhile (left < right && a[right] >= a[keyi]){right--;}//左边找大while (left < right && a[left] <= a[keyi]){left++;}Swap(&a[left], &a[right]);}//相遇位置一定比key小Swap(&a[keyi], &a[left]);keyi = left;return keyi;
}

2）挖坑版本

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//三数取中，有序情况下最快
int GetMidNumi(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[mid] > a[left]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else //a[mid] <= a[left]{if (a[right] < a[mid]){return mid;}else if (a[right] > a[left]){return left;}else{return right;}}
}
//挖坑版
int PartSort2(int* a, int left, int right)
{//优化：三数取中int midi = GetMidNumi(a, left, right);Swap(&a[left], &a[midi]);int key = a[left];int pit = left;//这地方left 不能先+1，否则最后一步交换会出问题while (left < right){//右边先找小//注意内部没有判断left< rightwhile (left < right && a[right] >= key){right--;}a[pit] = a[right];pit = right;//左边找大while (left < right && a[left] <= key){left++;}a[pit] = a[left];pit = left;}//相遇位置一定比key小a[pit] = key;return pit;
}

3）前后指针版本

//前后指针法
int PartSort3(int* a, int left, int right)
{int midi = GetMidNumi(a, left, right);if (midi != left){Swap(&a[left], &a[midi]);}int keyi = left;int prev = left;int cur = left + 1;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[prev], &a[cur]);}++cur;}//这里prev直接换就好了，不用交换Swap(&a[prev], &a[keyi]);keyi = prev;return keyi;
}

4）快速排序调用程序

void QuickSort(int* a, int left, int right)
{//递归结束条件if (left >= right){return;}//小区间优化 -- 小区间使用插入排序//这个数字不能太大，否则没有意义if ((right - left + 1) > 10){int keyi = PartSort3(a, left, right);//只需改变1，2，3就可以改用三个快速排序版本//[begin, keyi-1] keyi [keyi+1, end]QuickSort(a, left, keyi - 1);QuickSort(a, keyi+1, right);}else{InsertSort(a + left, right - left +1);}
}

优化：

在区间长度小于10时，改用插入排序，然后再递归，增加了算法效率。但是一定要注意区间长度一定要设置的恰到好处，否则区间过长就起不到相应的作用了。

1.2.5 非递归实现(重点)

非递归的实现一般有两种方式：

1.直接改，适用于简单的递归，比如斐波那契数；
2.使用栈辅助改为非递归，适用于复杂的结构，利用栈先进先出的特点，对数据进行排序。

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 = PartSort3(a, begin, end);if (end > keyi + 1){STPush(&st, end);STPush(&st, keyi + 1);}if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}}STDestroy(&st);
}

二、归并排序

归并排序是一种分治算法，它将列表递归地拆分成两个子列表，然后将这两个子列表合并成一个有序的列表。

2.1 基本思想

它的基本思想是将待排序列表分解成若干个子列表，然后将这些子列表逐个合并，最终得到一个有序的列表。

动画演示：

2.2 具体步骤

将列表不断地二分，直到每个子列表只包含一个元素。
将两个有序的子列表合并成一个有序的列表。合并时，比较两个子列表的第一个元素，将较小的元素放到结果列表中，并将指针向后移动一位，依此类推，直到其中一个子列表为空。然后将另一个非空子列表的剩余部分直接放到结果列表中。
重复步骤2，直到所有的子列表都合并为一个有序的列表。

2.3 算法特性

1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)，其中n是列表的长度。
3. 空间复杂度：归并排序是一种稳定的算法>排序算法，它需要额外的空间来存储临时的结果，所以空间复杂度为O(n)。
4. 稳定性：稳定

2.4 算法实现

//归并排序，O(NlogN)
void _MergeSort(int* a, int begin, int end, int* tmp)
{//递归结束条件if (begin >= end){return;}int mid = (begin + end) / 2;//mid控制递归_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid + 1, end, tmp);//[begin, mid] [mid+1, end]归并int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;//i为每个栈帧中的独立变量，控制每一次的归并int i = begin;while (begin1 <= end1 && begin2 <= end2){//begin1<=begin2，可以做到稳定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);tmp = NULL;
}

归并在实现时使用了递归所以一定要注意栈帧的开辟，防止爆栈。

事实上，归并的递归写法并不难，但是在大量数据归并时对栈帧的开销很大，很容易造成栈溢出，所以作为一名合格的程序员，一定要学会将递归改为非递归。

修正思路：

归并排序改非递归：数据多不好调试，可以打印出来看边界

复杂问题分解为简单问题：分类处理

1.end1越界？不归并了

2.end1没有越界，begin2越界了？跟1一样处理

3.end1、begin没有越界，end2越界了？继续归并，修正

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1;//gap是归并过程中，每组数据的个数while (gap < n){for (int i = 0; i < n; i += 2*gap){			//归并一次，拷贝一次（推荐）if (end1 >= n || begin2 >= n){break;}if (end2 >= n){end2 = n - 1;}//归并int j = i;while (begin1 <= end1 && begin2 <= end2){//begin1<=begin2时可以做到稳定if (a[begin1] <= a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}//没排到的直接接到后面while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}//数据覆盖到原数组memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}gap *= 2;//gap控制遍历}free(tmp);tmp = NULL;
}