DS八大排序之冒泡排序和快速排序

前言

前两期我们已经对"插入排序"（直接插入排序和希尔排序）和 "选择排序"（直接选择排序和堆排序）进行了详细的介绍~！这一期我们再来详细介绍一组排序："交换排序"即耳熟能详的冒泡排序和赫赫有名的快速排序~！

本期内容介绍

冒泡排序

快速排序（Hoare、挖坑、前后指针、非递归）

交换排序的基本思想

对待排序的序列，进行元素的两两比较，如果满足交换条件，交换。即将元素逐步换到合适的位置~！

冒泡排序

从前往后，逐一比较相邻元素，前面的大于或小于后面的则进行交换，每一轮将当前轮最大或最小的元素冒泡到当前论的最后。重复上述过程最后就是有序的~！

OK，还是画个图理解一下：

OK，这就是冒泡排序的过程，我们还是先来写单趟，再来改造整体：

单趟

	//注意，前一个和后一个比，j最大只能走到n-2(倒数第二个)，j+1只能走到n-1(倒数第一个)for (int j = 0; j < n - 1; j++){if (a[j] > a[j + 1]){Swap(&a[j], &a[j + 1]);}}

整体

整体的话，控制一下每一趟的交换个数即可~！

//冒泡排序
void BubbleSort(int* a, int n)
{for (int i = 0; i < n - 1; i++)//n-1是最后一个只能放在第一个即可以不对他排{//注意，前一个和后一个比，j最大只能走到n-2(倒数第二个)，j+1只能走到n-1(倒数第一个)for (int j = 0; j < n - 1 - i; j++)//每一趟确定当前趟的最大之到当前趟的最后{								//每一趟确定出一个即每一趟少排i个if (a[j] > a[j + 1]){Swap(&a[j], &a[j + 1]);}}}
}

OK，测试一下！看结果：

没问题！但有一种情况就是上述画图的那种例子，已经有序了但不知道还是在两两比较。这其实是很没有必要的~！请我们可以优化一下！

优化思路：在每一趟开始之前进行一个有序的标记，当一趟结束后判断该标记，如果有序直接不用再往后排了，否则继续进行排序~！

//冒泡排序
void BubbleSort(int* a, int n)
{for (int i = 0; i < n - 1; i++)//n-1是最后一个只能放在第一个即可以不对他排{int flag = 1;//假设该趟有序//注意，前一个和后一个比，j最大只能走到n-2(倒数第二个)，j+1只能走到n-1(倒数第一个)for (int j = 0; j < n - 1 - i; j++)//每一趟确定当前趟的最大之到当前趟的最后{								//每一趟确定出一个即每一趟少排i个if (a[j] > a[j + 1]){Swap(&a[j], &a[j + 1]);flag = 0;//交换了说明是该趟是无序的}}if (flag == 1)//说明已经有序了没有必要再冒泡了{break;}}
}

冒泡这是一种写法，其实还有很多。这里再来一个：这里前面与后面比较！

单趟

		//后一个和前一个比较，j最大走到倒数第一个for (int j = 1; j < n - i; j++){if (a[j - 1] > a[j])//后面与前一个比较{Swap(&a[j - 1], &a[j]);flag = 0;}}

整体

//冒泡排序
void BubbleSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int flag = 1;//后一个和前一个比较，j最大走到倒数第一个for (int j = 1; j < n - i; j++){if (a[j - 1] > a[j])//后面与前一个比较{Swap(&a[j - 1], &a[j]);flag = 0;}}if (flag == 1)//已经有序不要再去冒泡了{break;}}
}

测试一下：

一点问题没有~！

总结：冒泡虽然简单，但一定要注意边界点的控制~！

复杂度分析

时间复杂度：O(N^2)

每一趟遍历选出一个最值即每一趟都比前一趟少比较一次，所以他应该是第一趟比较n-1次，第二趟比较n-2次...1很明显这是等差数列求和，最后的时间复杂度为O(N^2)

空间复杂度：O(1)

快速排序

在一个序列中先随意选出一个元素，该元素称为基准。比基准值大的移动到基准的右边，比基准值小的移动到基准的左边，这样基准值就到了他该到的位置。然后对基准值的左右区间分别进行上述相同的操作

相信看到这里应该想到快排用的是递归，是的！但我们也会实现非递归版本~！

快排最核心的就是他选基准的那个单趟！这里的版本我会的有三个：Hoare、挖坑法、前后指针。下面一个一个的来！

Hoare

选择最左端或最右端作为基准点，使用两个指针从序列两端向中间扫描，右指针找到比基准小的值，左指针找到比基准大的值，然后进行交换。重复这个过程直到左右指针相遇，相遇的位置就是基准的最终位置。（为什么相遇的位置就是最终的位置呢？后面会解释！）

OK，还是画个图理解一下：

OK，上代码：

//Hoare
int PartSort1(int* a, int left, int right)
{int keyi = left;//选最左端的为基准while (left < right){//右指针找小while (left < right && a[right] >= a[keyi])right--;//左指针找大while (left < right && a[left] <= a[keyi])left++;//找到了，交换Swap(&a[right], &a[left]);}//当相遇时left或right与基准交换Swap(&a[left], &a[keyi]);return left;//返回基准下标
}

解释：

1、这里找大或找小时可能在极端情况下找不到，从而导致越界。所以得判断让其不要越界~！

2、为什么在左右指针相遇时就是基准的最终位置？（左右指针相交有两种情况，左找右和右找左）

左找右：因为是右先找小，所以当他们相交时，一定是小于基准的。

右找左：因为前一轮已经交换过，所以当前左一定是小于基准的的。

这就保证了，当左右相交时的位置与基准的位置交换后基准的位置是最终位置！

OK，单趟写好了就可以用相同的方式去处理左右区间了~！而每个区间的处理和上述的处理方式一样，所以使用递归就很方便~！

我们以前在函数那一期介绍递归的时候说过，递归必须有结束条件~！这个的结束条件是啥吧呢？

其实很简单，只需要注意每次递归的那个区间合法即可！即左区间 < 右区间(相等只有一个元素也不需要排了)

整体

//快速排序
void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int key = PartSort1(a, begin, end);//[begin, key-1] key [key+1, end]QuickSort(a, begin, key - 1);QuickSort(a, key + 1, end);
}

测试一把：

其实介绍到这里，你有没有感觉到。快排很像二叉树的前序遍历~！

OK，我们再来看看，Hoare的优化版(国人优化的)挖坑法！

挖坑法

和Hoare的很相似。用左右两指针向中间扫描，右找小，左找大。选最左端或最右端为基准，基准位置空出来了，形成了坑。右指针(左指针)先走，找到小(大)的了，填到左(右)边坑里面。自身形成了坑，左(右)边找大(小)，填到右(左)边的坑。如此循环，直到相交！然后把基准与左右指针的任意交换即可~！

OK，还是画个图：

OK，上代码：

//挖坑法
int PartSort2(int* a, int left, int right)
{int keyi = a[left];//选左端为基准，左端就是坑位while (left < right){//右指针找小while (left < right && a[right] >= keyi)right--;a[left] = a[right];//找到了，填到左坑，自身成了新坑位//左指针找大while (left < right && a[left] <= keyi)left++;a[right] = a[left];//找到了，填到右坑，自身成了新坑位}//左右指针相遇，交换基准与左右指针的任意Swap(&a[left], &keyi);return left;//返回基准的下标
}

整体

//快速排序
void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int key = PartSort2(a, begin, end);//[begin, key-1] key [key+1, end]QuickSort(a, begin, key - 1);QuickSort(a, key + 1, end);
}

测试一下：

OK，没有问题！下面我们在来看一个版本~前后指针。

前后指针

选左端为基准，前指针在第一个位置，后指针的第二个位置。当前指针遇到小于基准值时，当前位置的值与后指针的下一个位置的值进行交换。直到前指针到区间结束，此时后指针与基准交换，后指针的位置就是最终基准的位置！

OK，还是来画个图：

OK，上代码：

//前后指针
int PartSort3(int* a, int left, int right)
{int prev = left;//后(慢)指针int keyi = left;//基准int cur = left + 1;//快指针while (cur <= right)//闭区间所以是<={if (a[cur] < a[keyi])//快指针如果找到小了{Swap(&a[++prev], &a[cur]);//与prev的下一个位置交换}++cur;}Swap(&a[prev], &a[keyi]);//最后交换基准位置与prev位置的值return prev;//返回基准的位置
}

这里其实可以小小的优化一下：和上面画图情况的一样，假设prev和cur是同一个位置时，是不是根本就不用交换啊~！OK，我们可以控制一下

//前后指针
int PartSort3(int* a, int left, int right)
{int prev = left;//后(慢)指针int keyi = left;//基准int cur = left + 1;//快指针while (cur <= right)//闭区间所以是<={if (a[cur] < a[keyi] && ++prev != cur)//快指针如果找到小了并且prev的位置和cur不同{Swap(&a[prev], &a[cur]);//与prev的下一个位置交换}++cur;}Swap(&a[prev], &a[keyi]);//最后交换基准位置与prev位置的值return prev;//返回基准的位置
}

整体

//快速排序
void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int key = PartSort3(a, begin, end);//[begin, key-1] key [key+1, end]QuickSort(a, begin, key - 1);QuickSort(a, key + 1, end);
}

测试一下：

OK，没有问题~！

以上就是三个版本快排了，他们都是递归版本的。以前介绍的递归时说过递归有个致命的缺陷是：如果递归的太深会栈溢出（每一次调用都要建立函数栈帧，一般的情况下栈区的大小时7M左右）~！为了解决栈溢出的问题我们采用非递归即迭代的方式来解决这个问题~！下面我们来实现一下~！

非递归版本

非递归版本，其实时利用栈来模拟递归的这个过程的~！但C语言没有栈这种数据结构...得手搓，我们就把以前的在栈和队列那一期的那个拿过来。

实现思路：模拟递归的方式！先让数组的 0 和 size-1 即左右端点的下标入栈，当栈不为空时分别取栈顶元素，赋值给左右指针。然后调用任意一个版本的单趟获得基准，然后把基准左右的两个区间入栈继续上述操作！直到栈为空就排序结束了~！

OK，画个图：

OK，上代码：

//快速排序 非递归版
void QuickSort(int* a, int begin, int end)
{ST* s = NULL;//先把左右区间入栈Push(&s, end);Push(&s, begin);//栈不为空时，出left和rightwhile (!STEmpty(s)){//获取左端点int left = STTop(s);Pop(&s);		//获取右端点int right = STTop(s);Pop(&s);//获取该区间的基准int keyi = PartSort3(a, left, right);//右子区间入栈if (keyi + 1 < right){Push(&s, right);Push(&s, keyi + 1);;}//左子区间入栈if (left < keyi - 1){Push(&s, keyi-1);Push(&s, left);}}STDestory(&s);
}

OK，测试一下：

分析以及优化

我们前面说过快速排序和二叉树的前序遍历很象，然而上述的版本的单趟和一些情况下其实可以做一下一些小优化~！第一当我们的待排序的序列是已经有序的时！我们快速排序的时间复杂度时很高的，接近O(n^2)如下图1分析，避免这种情况我们采用三数取中的方式来解决。第二递归的最后几层是整个递归的80%左右，而递归要建立函数栈帧空间消耗比较大，我们可以在区间小的时候，换成直接插排提高效率~！

图1：快排最差情况（已经有序）

解决已经有序的序列排序效率低的问题 --->三数取中

三数取中：当前待排的序列的最左端、最右端、最中间。三个值中取中间大的那一个~！这样就不怕有序的情况效率低了，而且是越有序越效率高~！

代码实现：

//三数取中
int GetMid(int* a, int left, int right)
{int mid = left + (right - left) / 2;if (a[left] > a[right]){if (a[mid] < a[right]){return right;}else if (a[mid] > a[left]){return left;}elsereturn mid;}else{//left < rightif (a[mid] > a[right]){return right;}else if (a[mid] < a[left]){return left;}elsereturn mid;}
}

当区间小的时候，我们可以采用指直接插排来优化。

原因：在序列很大时当区间小的时候就说明此小区间已经接近有序了，而接近有序的区间直接插入排序的效率很高的。

代码实现：

void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;if (end - begin + 1 > 10){int key = PartSort1(a, begin, end);//[begin, key-1] key [key+1, end]QuickSort(a, begin, key - 1);QuickSort(a, key + 1, end);}else{InsertSort(a, end - begin + 1);//区间小于10个待排序的元素后进行直接插排}
}

复杂度分析

时间复杂度：O(N*logN)

快排可以看做一棵二叉树，一共有N个节点。每一层确定2^(i-1)（i从1开始）个待排元素的最终位置，总共的确定待排的层数是：2^x = N ---> x = logN,而每一次确定一个元素的位置又是遍历一遍待排的序列即O(N)所以总共合计O(N*logN)

注意：加了三数取中，几乎不可能再出现O(N^2)了

空间复杂度：O(logN)

因为递归是要开销栈帧的，我们前面在复杂度的那一期介绍过，空间可以重复利用而时间不可重复利用。所以这里至多递归到他的深度即h = logN,所以他的空间复杂度是O(logN)

注意：非递归的空间复杂度任然是log(N)原因是他的空间消耗虽然不在栈了，但他利用栈的数据结构转移到了堆上，还是会消耗空间的~！！

优化后的快排源码：

//三数取中
int GetMid(int* a, int left, int right)
{int mid = left + (right - left) / 2;if (a[left] > a[right]){if (a[mid] < a[right]){return right;}else if (a[mid] > a[left]){return left;}elsereturn mid;}else{//left < rightif (a[mid] > a[right]){return right;}else if (a[mid] < a[left]){return left;}elsereturn mid;}
}Hoare 
O(N)
int PartSort1(int* a, int left, int right)
{int mid = GetMid(a, left, right);Swap(&a[mid], &a[left]);int keyi = left;while (left < right){while (left < right && a[right] >= a[keyi])right--;while (left < right && a[left] <= a[keyi])left++;Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);return left;
}挖坑法
O(N)
int PartSort2(int* a, int left, int right)
{int mid = GetMid(a, left, right);Swap(&a[mid], &a[left]);int keyi = a[left];while (left < right){while (left < right && a[right] >= keyi)right--;a[left] = a[right];while (left < right && a[left] <= keyi)left++;a[right] = a[left];}a[left] = keyi;return left;
}前后指针
O(N)
int PartSort3(int* a, int left, int right)
{int mid = GetMid(a, left, right);Swap(&a[mid], &a[left]);int prev = left;//后(慢)指针int keyi = left;//基准int cur = left + 1;//快指针while (cur <= right)//闭区间所以是<={//if (a[cur] < a[keyi])//快指针如果找到小了//{//	Swap(&a[++prev], &a[cur]);//与prev的下一个位置交换//}if (a[cur] < a[keyi] && ++prev != cur)//快指针如果找到小了并且prev的位置和cur不同{Swap(&a[prev], &a[cur]);//与prev的下一个位置交换}++cur;}Swap(&a[prev], &a[keyi]);//最后交换基准位置与prev位置的值return prev;//返回基准的位置
}//快速排序
//O(N*logN)
void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;if (end - begin + 1 > 10){int key = PartSort1(a, begin, end);//[begin, key-1] key [key+1, end]QuickSort(a, begin, key - 1);QuickSort(a, key + 1, end);}else{InsertSort(a, end - begin + 1);//区间小于10个待排序的元素后进行直接插排}
}//快速排序 非递归版
//void QuickSort(int* a, int begin, int end)
//{
//	ST* s = NULL;
//	//先把左右区间入栈
//	Push(&s, end);
//	Push(&s, begin);
//
//	//栈不为空时，出left和right
//	while (!STEmpty(s))
//	{
//		//获取左端点
//		int left = STTop(s);
//		Pop(&s);		
//		//获取右端点
//		int right = STTop(s);
//		Pop(&s);
//		//获取该区间的基准
//		int keyi = PartSort3(a, left, right);
//		//右子区间入栈
//		if (keyi + 1 < right)
//		{
//			Push(&s, right);
//			Push(&s, keyi + 1);;
//		}
//		//左子区间入栈
//		if (left < keyi - 1)
//		{
//			Push(&s, keyi-1);
//			Push(&s, left);
//		}
//	}
//
//	STDestory(&s);
//}

OK，好兄弟我们本期分享就到这里，我们下一期的归并排序再见~！