快速排序及归并排序的实现与排序的稳定性

快速排序

一. 快速排序递归的实现方法

1. 左右指针法

步骤思路

为什么要让end先走？

2. 挖坑法

步骤思路

3. 前后指针法

步骤思路

二. 快速排序的时间和空间复杂度

1. 时间复杂度

2. 空间复杂度

三. 快速排序的优化方法

1. 三数取中优化

2. 小区间优化

四. 使用栈来实现非递归快排

步骤思路

归并排序

编辑

一. 归并排序的递归实现

步骤思路

二. 时间复杂度与空间复杂度

1. 时间复杂度

2. 空间复杂度

三. 非递归实现归并排序

步骤思路

排序算法的稳定性

快速排序

一. 快速排序递归的实现方法

1. 左右指针法

步骤思路

(假设排升序)将数组a最左边的下标用begin记录下来，最右边用end记录下来，定义一个key为begin或end

(假设key定义为begin)end先向左查找找到<a[key]的数停下，begin再向右查找找到>a[key]的值停下，此时将begin指向的值与end指向的值交换，以此类推直到end的值<=begin，将此时的a[key]与begin与end相遇坐标的值交换，我们发现此时的a[key]，左边的值都比其小，右边的值都比其大，那就说明key所指向的值在数组中已经排好位置了

如以下代码，即完成了单趟

		int key = left;int begin = left, end = right;while (begin < end){while (a[end] >= a[key] && begin < end){end--;}while (a[begin] <= a[key] && begin < end){begin++;}Swap(&a[begin], &a[end]);}Swap(&a[key], &a[begin]);

我们在end和begin寻找比a[key]大或小的值的时候不要忘记也要判断循环成立的条件

既然key已经在数组排好位置，我们接下来递归就不需要加上key了，只需要递归key的左右区间即可，直到递归的区间左边与右边相等即只有一个数

完整代码如下

void QuickSort1(int* a, int left,int right)
{if (left >= right)return;int mid = GetMid(a, left, right);Swap(&a[mid], &a[left]);int key = left;int begin = left, end = right;while (begin < end){while (a[end] >= a[key] && begin < end){end--;}while (a[begin] <= a[key] && begin < end){begin++;}Swap(&a[begin], &a[end]);}Swap(&a[key], &a[begin]);QuickSort1(a, left, begin - 1);QuickSort1(a, begin + 1, right);
}

为什么要让end先走？

左边做key右边先走，可以保证相遇位置比key小
相遇场景分析

begin遇end：end先走，停下来，end停下条件是遇到比key小的值,end停下来的位置一定比key小,begin没有找到大的遇到end停下了
end遇begin:end先走，找小，没有找到比key更小的，直接跟begin相遇了。begin停留的位置是上一轮交换的位置(即，上一轮交换，把比key小的值，换到begin的位置了）
同样道理让右边做key，左边先走，可以保证相遇位置比key要大

2. 挖坑法

步骤思路

(假设排升序，给数组a)将最左边的值定义key存储起来，最左边的下标用bigen记录，最右边的下标用end记录，定义pivot记录为最左边的下标，即将最左边视为坑位

然后end向左寻找比key小的值放到pivot所指向的位置即坑位中，并将这个地方(end所找到的)视作新的坑(更新pivot的值)。

begin向右寻找比key大的值，放到坑位中，并将这个地方视作新的坑(更新pivot的值)

重复以上步骤直到end<=begin

然后将key填进pivot中，再通过递归，即可完成排序

由于与左右指针法类似就不写单趟，直接上完整代码

void QuickSort2(int* a, int left, int right)
{if (left >= right)return;int key = a[left];int begin = left, end = right;int pivot = left;while (begin < end){while (a[end] >= key && begin < end){end--;}a[pivot]=a[end];pivot = end;while (a[begin] <= key && begin < end){begin++;}a[pivot] = a[begin];pivot = begin;}a[pivot] = key;QuickSort2(a, left, pivot - 1);QuickSort2(a, pivot + 1, right);
}

3. 前后指针法

步骤思路

(假设排升序)定义key为数组最左边的下标，并定义，prev=key与after=key+1

after在找到比key指向的值小的值时，prev++，并将after指向的值与现在的prev(即prev++后的值)交换

以此往复，直到after>数组的值

然后将prev所指向的值与key所指向的值交换

代码如下

我们要注意，当prev++后的值==after就会发生与自身交换

完成一次后，效果依然是a[key]左区间的值比其小，右区间的值比其大

	int key = left;int prev = left, after = left + 1;while (after<=right){while (a[after] < a[key]&&++prev!=after){Swap(&a[prev], &a[after]);}after++;}Swap(&a[prev], &a[key]);

递归是和上面两种方法同样的道理

完整代码如下

void QuickSort3(int* a,int left,int right)
{if (left >= right)return;int key = left;int prev = left, after = left + 1;while (after<=right){while (a[after] < a[key]&&++prev!=after){Swap(&a[prev], &a[after]);}after++;}Swap(&a[prev], &a[key]);QuickSort3(a, left, prev - 1);QuickSort3(a, prev + 1, right);
}

二. 快速排序的时间和空间复杂度

1. 时间复杂度

①最好情况

每次的划分都使得划分后的子序列长度大致相等，一般在数据已经部分有序或者随机分布的情况下发生。此时时间复杂度为O(Nlog₂N)

②最坏情况

在待排序序列有序的情况下，每一次划分的两个区间都有一个为0，此时快速排序的时间复杂度退化为O(N²)

③平均情况

实际应用中快速排序的平均情况大概会接近于最好情况，因为待排序序列通常不是有序的，我们还可以通过三数取中来优化，减少最坏情况的可能性，所以快速排序的时间复杂度为O(Nlog₂N)

2. 空间复杂度

由于需要递归调用，相当于求递归树的深度，

①最坏情况

当数组接近有序时，递归深度很深，空间复杂度为O(N)

②最好情况

当数组无序时，递归树基本相当与完全二叉树，空间复杂度为O(log₂N)

③平均情况

实际应用中，平均情况大概会接近最好情况，同样可以用三数取中优化

所以快速排序空间复杂的为O(log₂N)

三. 快速排序的优化方法

1. 三数取中优化

为了让每次左右区间长度接近，我们可以使用三数取中，即最左边最右边与中间的值取不大也不小的一个值并返回

int GetMid(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[mid] < a[right])return mid;else if (a[left] < a[right])//上面if条件不成立可得a[right]<a[mid]return right;else//又可得 a[left] > a[right]return left;}else//a[left]>=a[mid]{if (a[mid] > a[right])return mid;else if (a[left]<  a[right])//上面if条件不成立可得a[right]>a[mid]return left;else//又可得 a[left] < a[right]return right;}}

将返回值接收并将其指向位置与最左边的值交换，代码如下

		if (left >= right)return;int mid = GetMid(a, left, right);Swap(&a[mid], &a[left]);int key = left;

2. 小区间优化

当快速排序要排的数据很长时，越递归到后面区间越小递归的层数越多，我们可以考虑，当要递归区间小于10的时候用别的排序来代替，这样就可以省去80%到90%的递归

代码如下

void QuickSort1(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 mid = GetMid(a, left, right);Swap(&a[mid], &a[left]);int key = left;int begin = left, end = right;while (begin < end){while (a[end] >= a[key] && begin < end){end--;}while (a[begin] <= a[key] && begin < end){begin++;}Swap(&a[begin], &a[end]);}Swap(&a[key], &a[begin]);QuickSort1(a, left, begin - 1);QuickSort1(a, begin + 1, right);}
}

四. 使用栈来实现非递归快排

栈的实现可以看一下我以前的博客

栈的实现详解-CSDN博客

步骤思路

初始化栈后，将数组的最右边与最左边分别放入栈(即将一个区间放入栈中)

进入循环(当栈为空时循环结束)，用begin和begin1接收栈顶端的值，再删除栈的值，再用end和end1接收栈顶端的值，再删除栈的值，使用左右指针法(挖坑法，前后指针法皆可)(用begin与end来寻找值，begin1与end1不变)进行一趟排序，

如果right1>=begin+1 就往栈里存 right1(当前排序区间的最右边) 和 begin+1 反之不存

如果left1<=begin-1 就往栈里存 begin-1 和 left1(当前排序区间的最左边) 反之不存

最后不要忘记销毁栈

代码如下

void StackQuickSort(int* a, int left, int right)
{ST s;StackInit(&s);StackPush(&s, right);StackPush(&s, left);while (!StackEmpty(&s)){int begin = StackTop(&s);int left1 = begin;StackPop(&s);int end = StackTop(&s);int right1= end;StackPop(&s);int key = begin;//int mid = GetMid(a, begin, end);//Swap(&a[mid], &a[begin]);while (begin < end){while (a[end] >= a[key] && begin < end){end--;}while (a[begin] <= a[key] && begin < end){begin++;}Swap(&a[begin], &a[end]);}Swap(&a[key], &a[begin]);if(right1>=begin+1){StackPush(&s,right1);StackPush(&s, begin + 1);}if(left1<=begin-1){StackPush(&s, begin - 1);StackPush(&s, left1);}}StackDestroy(&s);
}

归并排序

一. 归并排序的递归实现

步骤思路

malloc一个临时数组进入子函数(创建子函数递归会更方便)，进行递归，子函数利用分治思想一直递归直到left>=right 开始执行下面操作

k赋初值为当前区间最左边，begin1 ， end1来记录左数组最左边和最右边，定义begin2 ，end2 来记录右数组的最左边和最右边，将两个数组从头比较，较小的赋值给临时数组，直到有一方赋完值，再将没赋完值的数组给临时数组赋值。最后给要排序数组left到right赋值为临时数组left到right

代码如下

//递归
void _MergeSort(int* a,int* tmp, int left, int right)
{if(left>=right){return;}int mid = (left + right) / 2;//如果[left,mid][mid+1,right]有序就可以归并了_MergeSort(a,tmp, left, mid);_MergeSort(a,tmp, mid + 1, right);int begin1 = left;int end1 = mid;int begin2 = mid + 1;int end2 = right;int k=left;while (begin1 <= end1&&begin2<=end2){if(a[begin1]<a[begin2]){tmp[k++] = a[begin1++];}else{tmp[k++] = a[begin2++];}}while (begin1 <= end1){tmp[k++] = a[begin1++];}while (begin2 <= end2){ tmp[k++] = a[begin2++];}for (int i = left; i <= right; i++){a[i] = tmp[i];}}void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}//_MergeSort(a, tmp, 0, n - 1);_MergeSort2(a,tmp,  n);free(tmp); tmp = NULL;
}

二. 时间复杂度与空间复杂度

1. 时间复杂度

归并排序的时间复杂度是稳定的，不受输入数组的初始顺序影响

将数组分成两个子数组的时间复杂度为O(1)，递归对子数组进行排序，假设每个子数组长度为n

则两个子数组排序的总时间复杂度为O(NlogN)，将两个有序数组合并为一个有序数组时间复杂度为O(N)，所以归并排序时间复杂度为O(NlogN)

2. 空间复杂度

调用栈所需要的额外空间为O(logN)，因为我们需要一个额外数组来存储数据所以又额外消耗O(N)的空间，我们将较小的O(logN)忽略可以得到归并排序的空间复杂度为O(N)

三. 非递归实现归并排序

步骤思路

开辟动态空间后定义一个数gap=1来控制区间(gap相当于每组数据个数)，(每一次gap*2，使每次区间扩大)gap<数组长度

设计一个for循环i+=gap*=2

每次分两组[i][i+gap-1]和[i+gap][i+2*gap-1] (i每次+=正好跳过这些数据)

将两个区间的值比较放入新开辟的数组，再拷贝到原数组

代码如下

//非递归
void _MergeSort2(int* a,int* tmp,int n)
{int gap = 1;while(gap<n){for (int i = 0; i < n; i += 2 * gap){int begin1 = i;int end1 = i + gap - 1;;int begin2 = i + gap;int end2 = i + 2 * gap - 1;int k = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[k++] = a[begin1++];}else{tmp[k++] = a[begin2++];}}while (begin1 <= end1){tmp[k++] = a[begin1++];}while (begin2 <= end2){tmp[k++] = a[begin2++];}//memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));for (int j = i; j < k; j++){a[j] = tmp[j];}}gap *= 2;}
}

但是我们发现，这样如果会发生越界的现象

一共三种可能

1. [begin1,end1][begin2,end2] end2越界
2. [begin1,end1][begin2,end2] begin2，end2越界
3. [begin1,end1][begin2,end2] end1，begin2，end2越界

第2,3种我们可以直接不递归了，因为后面区间的不存在前面区间的在上一次已经递归好了，

第一种呢我们需要把区间(即end)给修正一下

修正代码如下

//非递归
void _MergeSort2(int* a,int* tmp,int n)
{int gap = 1;while(gap<n){for (int i = 0; i < n; i += 2 * gap){int begin1 = i;int end1 = i + gap - 1;;int begin2 = i + gap;int end2 = i + 2 * gap - 1;int k = i;if (begin2 >= n)//第二种情况,第二组不存在，不需要归并break;if (end2 >= n)//第一种情况，需要修正一下end2 = n - 1;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[k++] = a[begin1++];}else{tmp[k++] = a[begin2++];}}while (begin1 <= end1){tmp[k++] = a[begin1++];}while (begin2 <= end2){tmp[k++] = a[begin2++];}//memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));for (int j = i; j < k; j++){a[j] = tmp[j];}}gap *= 2;}
}

排序算法的稳定性

假定在待排序的记录序列中，存在多个具有相同关键字的记录，若经过排序，这些记录的相对次序保持不变

即原序列中 r[i]=r[j],且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]前，则称这种排序算法是稳定的，否则是不稳定的

冒泡选择	稳定
选择排序	不稳定***	只会考虑自身，假如找到最小值1下标为3，将其与下标为0(假设此处为6)处交换若下标为1处也是6，就改变了
直接插入排序	稳定
希尔排序	不稳定(分组)	预排序时相同的值可能分到不同的组
堆排序	不稳定	建堆时可能就乱了
归并排序	稳定	当两个数相等，让第一个下来就是稳定的（可以控制）
快速排序	不稳定	end先找到 j 和begin交换了，在找到 i 和bigin交换，显然改变了