发布日期: 2022-09-18

八大排序算法

[toc]

Intro

数据结构和算法是不分家的，接下来的排序算法中，有的算法可能会用到某种数据结构

排序算法是什么呢？百度百科一下

排序就是把集合中的元素按照一定的次序排序在一起。一般来说有升序排列和降序排列2种排序，在算法中有8种基本排序

往往评价一个排序算法的好坏往往可以从几个方面入手：

（1）时间复杂度：即从序列的初始状态到经过排序算法的变换移位等操作变到最终排序好的结果状态的过程所花费的时间度量。

（2）空间复杂度：就是从序列的初始状态经过排序移位变换的过程一直到最终的状态所花费的空间开销。

（3）使用场景：排序算法有很多，不同种类的排序算法适合不同种类的情景，可能有时候需要节省空间对时间要求没那么多，反之，有时候则是希望多考虑一些时间，对空间要求没那么高，总之一般都会必须从某一方面做出抉择。

（4）稳定性：稳定性是不管考虑时间和空间必须要考虑的问题，往往也是非常重要的影响选择的因素。

就像Crash Course Computer Science 13. Intro to Algorithm所说，记载最多的算法之一是“排序”，我们在生活中也常常会排序，比如名字，比如数字Computer sort all the time,比如说找出最便宜的机票，按最新时间排邮件，按姓氏排联系……

本图片来源于Crash Course Computer Science,举了飞机飞到印第安纳波利斯的机票价钱排序

那么接下来开始介绍八大排序，之后的排序算法实例都是以排升序为示例

插入排序

插入排序其实可以联想到当我们在打扑克牌的时候，把同样大的摆在一起，把大的排在小的后面，每次摸一张牌的时候，就插入手中有序的拍的序列之中，找到合适的位置插入进去

直接插入排序

假设插入前的排序已经排好顺序，用要插入的数据进行一一比较，找到相应位置将其插入

实现插入排序

实现排序要想到先拆解问题，然后再画图思考

先对问题的拆解

单趟怎么走？
单趟实现了，那多趟怎么走？

先写单趟排序

先确定要插入的数组的最后一个是下标是end，然后要插入的值是tmp
然后比较数组中下标为end的值和tmp的大小
- 如果tmp小，那么当前指向的值向后移动一位，然后end往前走一个
- 如果tmp大，就放入当前end位置的后面一个
- 如果一样大就放在你这个数的后面
- 如果end==-1走出数组，那么还是放在end位置的后面一个，也就是数组下标为0的位置

int tmp;
int end;
	while (end >= 0)
	{
		if (tmp<end)
		{
			a[end + 1] = a[end];//挪动数据
         --end;
		}
		else
		{
			break;
		}
	}
	//循环结束或者end==-1
	a[end + 1] = tmp;

再写多趟，控制end的位置和插入的值

end的值等于i
tmp相当于end的后一个位置，所以是end+1

template<class T>
void InsertSort(vector<T>& a)   
{
    for (int i = 0; i < n - 1; ++i)
   	{
   		//把tmp插入到数组的[0，end]的有序区间
   		int end=i;
   		int tmp = a[end + 1];
   		while (end >= 0)
   		{
   			if (tmp < a[end])
   			{
   				a[end + 1] = a[end];
   				--end;
   			}
   			else
   			{
   				break;
   			}
   		}
   		//循环结束或者end==-1
   		a[end + 1] = tmp;
   	}

所以代码是这样

直接插排复杂度

最好与最坏	复杂度	发生情况
最坏的情况	O（N^2^）	逆序的一个数组
最好的情况	O（N）	顺序有序的数组

分析这样一个表格说明：直接插入排序比较适合接近于顺序有序的数组

希尔排序

希尔排序也叫缩小增量排序，希尔他分析了一下直接插入排序时间复杂度，他发现了问题，也解决了问题，实现了对直接插入排序的优化

希尔排序分为了两个目的：

预排序，使得数组接近有序
直接插入排序

效果：只要最后结果的方法复杂度小于O（N^2^），就是有效的进步

实现希尔排序

想法：

间隔为gap分为一组数据，对一组插入排序，假如说如上图的gap=5

这样之后相比原来的会更加接近有序，并且大的数会被更快的挪到后面，小的更快挪到后面

gap越大，大的和小的数可以更快地挪到对应的方向，但是越不接近有序
gap越小，大的和小的就会越慢地挪到对应的方向，但是gap越小就会越接近有序

希尔排序的思想就是一开始gap要相对于整个数据地总量来说是一个大的值，要求快速接近相应位置，然后gap要减小，为了接近有序，最后gap==1的时候本质就是一个直接插入排序

还是先对复杂的问题进行拆解

先写一次希尔排序
再把多趟排序完成

一次希尔排序

   int gap;
int end;
int tmp = a[end + gap];
while (end>=0)
{
	if (tmp < a[end])
	{
		a[end + gap] = a[end];
		end -= gap;
	}
	else
	{
		break;
	}
} 
a[end + gap] = tmp;

可以看到其实gap==1的时候就是直接插入排序

完成多次排序，改变gap让其越来越接近顺序

我们按照gap==3来举一个栗子

我们的想法是这样的，先对i所在位置的蓝色区间9排列，排完一次之后立马往后移一个i然后对红区间的1，然后是绿区间的2，然后再是蓝5，然后再是……，最后到size-gap即蓝8排完的时候结束算排序完

这样就可以把gap和end相应的赋值

int gap=3;
for (int i = 0; i < sz - gap; ++i)
{
	int end = i;
	int tmp = a[end + gap];
	while (end >= 0)
	{
		if (tmp < a[end])
		{
			a[end + gap] = a[end];
			end -= gap;
		}
		else
		{
			break;
		}
	}
	a[end + gap] = tmp;
}

但是gap肯定不能只是3不变，这里我们使用推荐的做法，每次gap都gap=gap/3+1，为的是使得最后一次能够保证最后一次一定是gap==1

void ShellSort(vector<T>& a)
{
    //多组并排
//gap>1的时候，预排序
//gap==1的时候，直接插入排序
int gap=sz;
while (gap > 1)
{
    gap = (gap / 3+1);//保证最后一次是1
    for (int i = 0; i < sz - gap; ++i)
    {
        int end = i;
        int tmp = a[end + gap];
        while (end >= 0)
        {
            if (tmp < a[end])
            {
                a[end + gap] = a[end];
                end -= gap;
            }
            else
            {
                break;
            }
        }
        a[end + gap] = tmp;
    }
}

当然gap每次/5，/7都是可以的

用一个逆序的栗子可以看希尔排序更直接

int a[] = { 10,9,8,7,6,5,4,3,2,1,-1,-2,-3,-4,-5,-6,-7,-8,-9,-10,-11 };

希尔排序时间复杂度

对于时间复杂度的问题上面来看，这里我们通过100000个数的伪随机数来试试看排序的速度（单位是毫秒）

srand(time(0));
const int N = 100000;
int* a1 = (int*)malloc(sizeof(int) * N);
int* a2 = (int*)malloc(sizeof(int) * N);
for (int i = 0; i < N; ++i)
{
		a1[i] = rand();
		a2[i] = a1[i];
}
int begin1 = clock();
InsertSort(a1, N);
int end1 = clock();

int begin2 = clock();
ShellSort(a2, N);
int end2 = clock();

printf("InsertSort:%d\n", end1 - begin1);
printf("ShellSort:%d\n", end2 - begin2);
free(a1);
free(a2);

可见差别还是很明显的

希尔排序的复杂度非常难算,平均来说是O(N^1.3^)

当取gap/3的时候是
$$
O(log_3^N*N)
$$

2. 选择排序

直接选择排序

选择排序

直接选择排序的想法

直接选择排序也就是暴力排序一波，排升序的时候找到剩下数组中最小的那一个放在剩下区间的头

当然现在我们可以稍稍优化一下，就是每遍历一遍数组，把最大和最小放在合适的位置，然后再去选择次小的和次大的，依次这样走，直到该区间只剩一个值或没有

优化了一点，但还是，因为要考虑最差的时间复杂度
$$
O(N^2)
$$

实现选择排序(不完全对)

int left = 0, right = sz - 1;
	while (left<right)
	{
		//找出=最大的和最小的
		int minIndex = left, maxIndex = left;
		for (int i = left; i <= right; ++i)
		{
			if (a[i] < a[minIndex])
			{
				minIndex = i;
			}
			if (a[i] > a[maxIndex])
			{
				maxIndex = i;
			}
		}
		Swap(&a[left], a[minIndex]);
		Swap(&a[right], a[maxIndex]);
		++left;
		--right;
	}

但是我们用逆序数组的栗子发现这样仍然不对，需要找一下问题

int a[] = { 10,9,8,7,6,5,4,3,2,1,-1,-2,-3,-4,-5,-6,-7,-8,-9,-10,-11 };

改正选择排序

其实我们的选择排序缺的是很重要的一步，通过调试我们可以发现，如果当a[left]正好就是数组中max的时候，因为有这样的一步

Swap(&a[left], a[minIndex]);

所以相当于a[left]的值被交换到了minIndex，那个数组中的最大值已经不是原先记录在maxIndex的下标，所以导致执行下一步的时候

Swap(&a[right], a[maxIndex]);

把a[right]换成了a[minIndex]，如果遇到left == maxIndex的情况时，会产生大问题，遇到逆序数组更是白排序了一遍

于是我们需要下面一步排除问题

if (left == maxIndex)
{
	maxIndex = minIndex;
}

正确的选择排序

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void SelectSort(int* a, int sz)
{
	int left = 0, right = sz - 1;
	while (left<right)
	{
		//找出=最大的和最小的
		int minIndex = left, maxIndex = left;
		for (int i = left; i <= right; ++i)
		{
			if (a[i] < a[minIndex])
			{
				minIndex = i;
			}
			if (a[i] > a[maxIndex])
			{
				maxIndex = i;
			}
		}
		Swap(&a[left], &a[minIndex]);
		if (left == maxIndex)
		{
			maxIndex = minIndex;
		}
		Swap(&a[right], &a[maxIndex]);
		++left;
		--right;
	}
}

堆排序

还有一种选择排序就是通过堆的特性来选择排序

堆排序就还是通过建堆，然后向上调整和向下调整来实现，具体的实现思路与方法会在数据结构堆中仔细展开，到时候可以参见那篇专门谈堆的博客

注：本图片来源于https://www.codesdope.com/staticroot/images/algorithm，图片仅供参考学习，不涉及商业用途，如有侵权，请联系删除

实现堆排序

一定要记住，==排升序要建大堆，排降序要建小堆==

分解问题
1. 先建大堆
2. 向下调整排序

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void AdjustDown(int* a, int sz,int root)
{
	int parent = root;
	int child = 2 * parent + 1;
	while (child < sz)
	{
		if (child + 1 < sz && a[child + 1] > a[child])//先检查再访问
		{
			++child;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;//已经小了就直接跳出循环  
		}
	}
}
void HeapSort(int *a,int sz)
{
	for (int i = (sz - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, sz, i);//向下调整建一个大堆
	}
	int end = sz - 1;//头放到最后，次大的放到倒数第二个……
	while(end>0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

堆排序的时间复杂度

$$
O(N*log_2 ^N)
$$
这时候我们再通过100000个数的伪随机数来试试看排序的速度（单位是毫秒）

效果很明显

空间复杂度是
$$
O(1)
$$

3. 交换排序

冒泡排序

基本想法

起源于水里的气泡随着上升，越来越大

在这里插入图片描述

实现冒泡排序

问题拆解
1. 单趟
2. 多趟

单趟

for (int i = 1; i < sz; ++i)
{
	if (a[i-1] > a[i])
	{
		Swap(&a[i], &a[i - 1]);
	}
}

多趟

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

优化

创建一个优化的标志，某一次如果没有交换，直接跳出循环，因为已经有序

void BubbleSort(int* a, int sz)
{
	for (int j = 0; j < sz; ++j)
	{
		bool exchange = false;
		for (int i = 1; i < j; ++i)
		{
			if (a[i - 1] > a[i])

            {
				algorithm::swap(a[i], a[i - 1]);
				exchange = true;
			}
		}
		if (exchange == false)
		{
			break;
		}
	}
}

时间复杂度分析

最好与最坏	复杂度	发生情况
最坏的情况	O（N^2^）	逆序的一个数组
最好的情况	O（N）	顺序有序的数组

看上去好像和插入排序是一样的，那么到底谁更好呢？

顺序有序的话，一样好

接近有序的话，插入好

快速排序

注：本图片来源于https://commons.wikimedia.org，图片仅供参考学习，不涉及商业用途，如有侵权，请联系删除

快排，如其名说明很快，且了解后发现其变形多

基本想法（Hoare）

Hoare的实现

单趟排序

选出一个key，一般是最左边的或者是最右边的，key放到正确的位置去，左边比key要小，右边的比key要大

这里看图来举个例子：

假设我们把这个数组里面的最左边的6选作为key，让right先走

其中right找小数，left找大数，目的其实是为了让左边的比key小右边的比key大

找完之后互相交换

继续找，继续交换

直到相遇，发现该值比key小，交换一下

这样的话就走完一趟了

这里有人会提出疑问

我们在之前为什么要求让right先走？

那如果我发现相遇的时候的值比key大怎么办？

其实我们让right先走这样设置的目的就是为了防止相遇的时候的值比key大的情况产生，就能保证始终比key小了

当走到最后一步时，如果先走的是left而不是right的话，left在找大的时候直接略过了3，使得相遇的时候的数字变成9，那最后一步要让比key小的数字和key互换就实现不了，所以最左边数字为key的时候，要让右边的right先走。也正是右边先走才能使得两种相遇形式，即左遇右（右边先找到小数就停，左边没找到继续走使得相遇）和右遇左（右边找不到小数直接走使得和左所在位置相遇），这两种情况都会使right找到小的（仔细画图分析）

那如果右边做key怎么来？左边先走

接下来，我们来完成多趟

在确定了之前的key之后我们把中间的现在放着key的左右两边拆开，就像分成左子树和右子树一样

对左一段和右一段分别重复上述操作，左边和右边就成了这样

继续如上操作

发现已经是有序的了

当最后只剩下一个的时候就是有序的

实现快速排序

对于单次排序，我们需要排除一种可能，也就是顺序数组可能会使得right一直找不到，使得right最后越界也没有完成任务

开始进入的时候while (left<right),并不能排除right越界，要在找大和找小的时候再判断一次

while (left<right&&a[right] > a[keyi])
while (left<right&&a[left]<a[keyi])

还要注意在找大和找小的时候=不能忘记，如果忘记就会使得当left和right遇到同样大的时候不++和–，最后直接交换陷入死循环，所以找大别带上等于，找小也别带上等于

while (left<right&&a[right] >= a[keyi])
while (left < right&&a[left]<=a[keyi])

所以细节很多，最后正确的单趟应该是这样

void QuickSort(int* a, int sz)
{
	int left = 0, right = sz - 1;
	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[keyi], &a[left]);//最后交换一下key的值和相遇的值
}

接下来完成多趟，完整实现

首先为了要递归，那么函数的参数肯定还用sz是不合适的，那么改成start和end，同时增加一个递归终止条件

那么这样就是Hoare版的快速排序

void QuickSort(int* a, int begin,int end)
{
	if (begin >= end)
	{
		return;
	}
	int left = begin, right = end;
	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]);
	}
	int meeti = left;
	Swap(&a[keyi], &a[left]);//最后交换一下key的值和相遇的值
	//左[begin,meeti-1] 右[meeti+1,end]
	QuickSort(a, begin, meeti - 1);
	QuickSort(a, meeti+1, end);
}

那么这个思想就是类似于二叉树的–“分治”排序

实现多种方法

这里我们把单趟排序抽离出来，将单趟返回参数来递归，那么

PartSort(a, begin, end)其实是由多种写法的，接下来分析多种写法

首先这个本体是不变的

void QuickSort(int* a, int begin,int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = PartSort(a, begin, end);//传key值
	//左[begin,meeti-1] 右[meeti+1,end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi+1, end);
}

为什么begin要>=而不是判断=，这是因为可能begin会超过end

Hoare法（左右指针法）

这里我们称之前所讲的方法为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[left], &a[right]);
	}
	Swap(&a[keyi], &a[left]);//最后交换一下key的值和相遇的值
	return left;
}

试试看其他几种方法实现单趟排序

挖坑法

还是取出left的值用key保存，比如说下图的6
这里不同的点在于当前left所指向的变成了一个坑，也就是该位置可以覆盖

同样的还是右边的right开始走，找小，找到小数之后这次不一样了，不是交换，而是把right的值放到坑里面，于是形成了新的坑

再然后left找大，填到坑里面，再产生新坑

最后会相遇，然后放进去key就好了

int PartSort2(int* a, int left, int right)
{
	int key = a[left];
	while (left < right)
	{	//找小
		while (left < right && a[right] >= key)
		{
			--right;
		}
		//放到左边的坑中，右边形成新的坑
		a[left] = a[right];
		//找大
		while (left < right && a[left] <= key)
		{
			++left;
		}
		//放到右边的坑中，左边形成新的坑
		a[right] = a[left];
	}
	a[left] = key;
	return left; 
}

那么这就是挖坑法，理解一下优点,本质上没有区别还有就是右边坑的话，左边先走

前后指针法

先是有两个指针，分别是cur和prev，开始的时候分别在一前一后
然后cur去找比key小的值，找到以后++prev，再交换prev和cur位置的值

前两次的交换之后没什么变化,因为cur==prev，所以等会写代码的时候可以排除这个可能性
第三次之后看到了变化，其实观察这个操作的意义是在把大的往后放，小的往前放

直到cur走出数组尾之后停止

最后把key位置和prev位置互相交换

这样的单趟的目的是什么呢，就是使得prev左边的数都比key小，右边的数都比key大

int PartSort3(int* a, int left, int right)
{
	int prev = left;
	int cur = left+1;
	int keyi = left;
	while (cur <= right)
	{
		if (a[cur] < a[keyi]&&++prev!=cur)
		{
			Swap(&a[left], &a[right]);
		}
		++cur;//不进或者交换之后都要往后走
	}
	Swap(&a[keyi], &a[prev]);
	return prev;//返回分隔的值 
}

前后指针法如果右边做key，那么其实还是从左边走，错位一下，到key左边就可以停了

时间复杂度测试

接下来用同样的方法，随机生成数组感受一下快排的速度

debug版在优化递归的时候不太好，性能不会太明显，建议用release来测性能

debug版 100000

release版 1000000

理想时间复杂度计算

最好的情况是：

理想的快排应该是每次的key恰巧是中位数，然后相当于二分法一样的走下去

时间复杂度是
$$
O(log_2^N*N)
$$

最坏的情况是

有序的数组，则此时每个排序都取最左边为key

这样的时间复杂度是
$$
O(N^2)
$$
因此这样的话来看，我们之前写的快排太不稳定，这样不是一个合格排序，我们要对这个快排优化，让它对所有的情况都好用，我们发现问题出在key的选取

于是我们可以采取

三数取中法（通过采取改进选key的方法来优化）
小区间排序优化

空间复杂度是
$$
O(logN)
$$

优化快排

三数取中法（通过采取改进选key的方法来优化）

既然问题出在选key，那么我们使得选恰好中间的数能够最优时间复杂度，于是我们可以每次找出头尾和中间那个三个数字中的中间数，并返回给key，使key的选取变得优化

int GetMidIndex(int* a, int left, int right)
{//找出头尾和中间那个三个数字中的中间数
	int mid = (left + right) >> 1;
	if (a[left] < a[mid]){
		if(a[mid]<a[right]){
			return mid;
		}else if(a[left]>a[right]){
			return left;
		}else{
			return right;
		}
	} else{
		if (a[mid] > a[right]){
			return mid;
		}else if (a[left] < a[right]){
			return left;
		}else {
			return right;
		}
	}
}
void QuickSort(int* a, int begin,int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = PartSort1(a, begin, end);
	//左[begin,meeti-1] 右[meeti+1,end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi+1, end);
}

三数取中法+Hoare

int PartSort1(int* a, int left, int right)
{
	int midIndex = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midIndex]);//到这步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[keyi], &a[left]);//最后交换一下key的值和相遇的值
	return left;
}

三数取中法+前后指针

int PartSort3(int* a, int left, int right)
{
	int midIndex = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midIndex]);//到这步left里的值将会使头中尾的中间值
	int prev = left;
	int cur = left+1;
	int keyi = left;
	while (cur <= right)
	{
		if (a[cur] < a[keyi]&&++prev!=cur)
		{
			Swap(&a[left], &a[right]);
		}
		++cur;//不进或者交换之后都要往后走
	}
	Swap(&a[keyi], &a[prev]);
	return prev;//返回分隔的值 
}

下图是对100000个数量的有序数组排序的比较，可以看出三数取中法有效解决了左右指针的缺陷, 甚至当遇到顺序数组的时候效率反而最高

小区间排序优化

也就是递归型的快排，是从头至尾一直是递归的，不断左右分段，像二叉树，不过即使到了最后几个数没有顺序，都要一直递归，于是想法是最后分割到数据到10个的时候用插排或选择解决，毕竟再用希尔和堆排序还要建堆和产生gap，那么又因为之前测过的插排优于选排，所以最后一个小区间里面就使用插排

那么我们改变这个本体

void QuickSort(int* a, int begin,int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = PartSort(a, begin, end);//传key值
	//左[begin,meeti-1] 右[meeti+1,end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi+1, end);
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	//1.如果这个区间是数据多，继续选key单趟，分割子区间
	//2.如果子区间数据量太小，再去递归不合适，不划算
	if (end - begin > 100)
	{
		int keyi = PartSort3(a, begin, end);
		//左[begin,meeti-1] 右[meeti+1,end]
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
	else
	{
		InsertSort(a + begin, end - begin + 1);
	}
}

当然如果用编译器其实优化效果不是很明显，因为编译器已经就递归做到了一些优化，但不像三数取中，优化来的好

==注意==：优化可以通过改变end-begin的值，具体多少要还是看数据的数量

非递归快排

注意可以用栈也可以用队列，如果非递归就观察一下三数取中可能会有问题

递归，现代编译器优化的比较好，性能问题不是很大，最大的问题在于，递归的深度太深，程序本身没问题，但是栈空间不够，导致栈溢出，只能改非递归==stack overflow警告==😁

如果能递归，还是递归，只要不会爆栈的话，递归还是香的

改成非递归有两种方式：

直接改循环，比如斐波那契数列
树遍历非递归和快排非递归，只能用栈模拟递归过程

接下来我们用栈来模拟递归过程

其实分治递归的思想和从栈中放入数据再取出来一样，不是递归，但是和递归很像

我们把单趟排序的区间给入栈，然后依次取栈里面的区间出来单趟排序，再循环需要处理的子区间入栈，直到栈为空。

void QuickSortNonR(int* a, int begin, int end)
{
	Stack st;
	StackInit(&st);
	StackPush(&st, begin);
	StackPush(&st, end);

	while (!StackEmpty(&st))
	{
		int left, right;
		right = StackTop(&st);
		StackPop(&st);

		left = StackTop(&st);
		StackPop(&st);

		int keyi = PartSort1(a, left, right);
		if (left < keyi - 1)
		{
			StackPush(&st, left);
			StackPush(&st, keyi - 1);
		}

		if (keyi + 1 < right)
		{
			StackPush(&st, keyi + 1);
			StackPush(&st, right);
		}
	}
	StackDestroy(&st);
}

注：非递归方法中栈的实现就放在GitHub中，码上来显得文章冗长，所以不写上来了，那么后期也会就栈这个数据结构仔细展开

如果用队列的话就有点像是层序遍历，用栈的话有点像是左子树走完再走you’zi’shu

4. 归并排序

在这里插入图片描述

基本想法

先把这个区间分成两半，然后均分成两个数组进行排序，最后得出两个有序的子区间之后再归并在一起就成为了有序数组

怎么归并？

设置左右指针两个互相比一比，取小的尾插到下面的数据，然后往后走，直到一个区间结束，再把另外一个区间尾插到结束

但是要归并的前提是有序，如果我还是没有序怎么办？就继续拆拆拆

拆到一个的时候就是有序的，然后归并就可以了

那么也就是说这样一个区间经过这样的过程就是有序的了

实现归并排序

void _MergeSort(int* a, int left,int right,int *tmp)
{
	if (left >= right)
		return;

	int mid = (left + right) >> 1;
	//[left,mid] [mid+1,right]
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid+1, right, tmp);
	
	//两段有序子区间归并tmp，并拷贝回去
	int begin1 = left,end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int i = left;
	while (begin1<=end1&&begin2<=end2){
		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++];
	}
	//归并完之后，拷回原数组
	for (int j = left; j <= right; ++j)
	{
		a[j] = tmp[j];
	}
}

void MergeSort(int* a, int sz)
{
	int* tmp = (int*)malloc(sizeof(int) * sz);
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	_MergeSort(a, 0, sz - 1,tmp);
	free(tmp);
        tmp = NULL;
}

cpp version

开一个额外空间
获取mid，递归分到最小子区间
一步步回溯，进行归并
双指针比大小归并
剩下的没有归并完的直接归并
反过来这时候tmp修改

template<class T>
void _MergeSort(vector<T>& v,int begin,int end,vector<T>& tmp)
{
	//分割
	if (begin >= end)
		return;
	int mid = begin + (end - begin)/2;
	//[begin, mid] [mid+1,end]
	_MergeSort(v, begin, mid , tmp);
	_MergeSort(v, mid+1, end, tmp);
	
	//归并
	int begin1 = begin, end1 = mid;
	int begin2 = mid+1, end2 = end;
	int index = begin;
	//printf("归并[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);
	//比大小拷到数组
	while (begin1<=end1 && begin2<=end2)
	{
		if (v[begin1] < v[begin2])
			tmp[index++] = v[begin1++];
		else
			tmp[index++] = v[begin2++];
	}
	//没走完的全部归并
	while (begin1<=end1)
		tmp[index++] = v[begin1++];
	while (begin2 <= end2)
		tmp[index++] = v[begin2++];
	//v = tmp;
	for (int i=begin;i<=end;++i)
	{
		v[i] = tmp[i];
	}
}

template<class T>
void MergeSort(vector<T>& v)
{ 
	vector<T> tmp(v);
	_MergeSort(v, 0, v.size() - 1, tmp);
}

归并的复杂度

排序算法	时间复杂度	空间复杂度
归并排序	O(N*log^N^)	O(N)

release版海量数据排序，所需时间如下

注：这里的快排是三数取中+Hoare

100000数据

1000000数据

这里忽略前三个排序

非递归实现归并排序

类似的，我们知道递归带给快排的问题，也会给归并排序带来，所以我们尝试用非递归方式实现归并排序

思路和注意事项

想法

要一半一半分开这个区间，放入tmp中，然后再取回来放到a中，使开始的gap=1，然后每次gap翻一倍，每次以gap为大小的区间是有序的，直到最后总长一半

注意事项

随着两两划分是有可能到最后一个只有一个数，[i+gap,i+2*gap-1]，也就是说第二个区间可能是不存在的

那需要修改一下，不存在就不要归了

还有一种可能性是第二组区间有但是不完整
还有一种可能性是第二组区间没有，第一组区间也不完整

把1和3归为一类去处理，直接不去归并了

要检查的是第二种可能，要修正一下

修改1

如果修正方法是越界就把end–，但是还是会导致同样的数字被重复写

// end1 越界，修正
if (end1 >= n)
	end1 = n - 1;

// begin2 越界，第二个区间不存在
if (begin2 >= n)
{
	begin2 = n;
	end2 = n - 1;
}

发现这种问题实际上我们可以打一个条件断点来寻找问题

// 条件断点
if (begin1 == 8 && end1 == 9 && begin2 == 9 && end2 == 9)
{
	int x = 0;
}

修改2

// 时间复杂度：O(N*logN) 空间复杂度：O(N)
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	int gap = 1;

	while (gap < n)
	{
		// 间距为gap是一组，两两归并
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			// end1 越界，修正
			if (end1 >= n)
				end1 = n - 1;

			// begin2 越界，第二个区间不存在
			if (begin2 >= n)
			{
				begin2 = n;
				end2 = n - 1;
			}

			// begin2 ok， end2越界，修正end2即可
			if (begin2 < n && end2 >= n)
				end2 = n - 1;

			// 条件断点
			/*if (begin1 == 8 && end1 == 9 && begin2 == 9 && end2 == 9)
			{
			int x = 0;
			}*/

			//printf("归并[%d,%d][%d,%d] -- gap=%d\n", begin1, end1, begin2, end2, gap);

			int index = i;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
					tmp[index++] = a[begin1++];
				else
					tmp[index++] = a[begin2++];
			}
			while (begin1 <= end1)
				tmp[index++] = a[begin1++];
			while (begin2 <= end2)
				tmp[index++] = a[begin2++];
		}
		memcpy(a, tmp, n * sizeof(int));
		gap *= 2;
	}
	free(tmp);
}

cpp version

template<class T>
//类似于后序，不像快排好用栈，其实循环就可以
void MergeSortNonR(vector<T>& v)
{
    vector<T> tmp(v);
    int gap = 1;
    int n = v.size();
    while (gap<n)
    {
        //间距为gap的一组数据分组归并
        for (int i=0;i<n;i+=2*gap)
        {
            //修改越界现象，原因是gap*2一下子只能覆盖2的指数
            int begin1 = i, end1 = i + gap-1;//控制的是个数下标要-1
            int begin2 = i + gap, end2 = i + 2 * gap - 1;
            //越界修正
            //end1越界
            if (end1 >= n)
                end1 = n - 1;
            //begin2修正，第二个区间不存在，直接停止
            if (begin2>=n)
            {
                begin2 = n;
                end2 = n - 1;
            }
            //begin2 ok ,2区间end结束
            if (begin2<n && end2 >= n)
                end2 = n - 1;
            int index = i;
            //比大小拷到数组
          //  printf("归并[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);
            while (begin1 <= end1 && begin2 <= end2)
            {
                if (v[begin1] < v[begin2])
                    tmp[index++] = v[begin1++];
                else
                    tmp[index++] = v[begin2++];
            }
            //没走完的全部归并
            while (begin1 <= end1)
                tmp[index++] = v[begin1++];
            while (begin2 <= end2)
                tmp[index++] = v[begin2++];
        }
        for (int i=0;i<v.size();++i)
        {
            v[i] = tmp[i];
        }
        gap *= 2;
    }
}

补充

我们这里要提到外排序和内排序，如何对大数据文件进行排序

归并排序天然支持外排序

举个栗子：

假如我们有10亿个整数在文件中，需要排序,计算后大小约等于4个G，不能直接放在内存中运算假如我们的内存是0.5G

我们可以对文件每次读1/8，也就是512M到内存中去排序（这里的排序不能用归并，因为归并空间复杂度O（N），可以用快排），然后写到文件里，再继续重复这个过程，最后将这几个有序小文件分别读数进行归并，两两归就成为4个，再两两归，两两归，最后合成一个

第二种可能性是第一个文件和第二个文件归并，然后第二个和第三个文件归并大文件，最后使得

5. 计数排序

计数排序有成为鸽巢原理，是对哈希直接定址法的变形应用

之前的排序都是比较大小来进行排序的，计数排序采取一种新思路，他的思想是

统计相同元素出现个数
根据统计结果将序列回收到原来的序列中

基本想法

如何统计每个数的次数
这里我们有一个A[i]数组，A[i]的值就是对Count数组该位置++

for(int i-0;i<sz;++i)
{
	++Count[A[i]];
}

然后根据count数组按照count数组的数据的下标和值是多少，产生相应值数量的下标区间
这个叫做绝对映射
注：

加入我给了如上几个数字，有一半多都没有映射，那我不可能去浪费0-9存空
所以我为什么不把下标为0的保存10然后下标为5的保存15，跳过1-9呢？
这就叫相对映射

那么因为绝对映射还是存在浪费的，所以在这里的计数排序我们采用相对映射

实现计数排序

void CountSort(int* a, int sz)
{
	int max = a[0], min = a[0];
	for (int i = 0; i < sz; ++i)
	{
		if (a[i] > max)
		{
			max = a[i];
		}
		if (a[i] < min)
			min = a[i];
	}
	int range = max - min + 1;
	int* count = (int *)malloc(sizeof(int) * range);
	memset(count, 0, sizeof(int) * range);
	for (int i = 0; i < sz; i++)
	{
		count[a[i] - min]++;
	}
	int i = 0;
	for (int j = 0; j < range; ++j)
	{
		while (count[j]--)
		{
			a[i++] = j+min;
		}
	}
}

cpp-version

template<class T>
void CountSort(vector<T>& v)
{
    T max = *max_element(v.begin(),v.end());
    T min = *min_element(v.begin(), v.end());
    vector<T> tmp(max-min+1, 0);
    // 计数
    for (int i=0;i<v.size();i++)
    {
        tmp[v[i] - min]++;
    }
    int range = max - min + 1;
    // 排序
    int j = 0;
    for (int i = 0; i < range; ++i)
    {
        while (tmp[i]--)
        {
            v[j++] = i + min;
        }
    }
}

时间复杂度分析

计数排序的复杂度

排序名	时间复杂度	空间复杂度
计数排序	O(N+range)	O(range)

所以说其实是和range有关的,最好是这组数据中,数据的范围都比较集中,很适合用计数排序,这个排序还是很优秀的,也有局限性,该排序只适合整数,浮点数字符串都不行,数据不集中也不行

分析八大排序

八大排序分析

该表格不建议去背,而是应该去理解

稳定性

什么是稳定性?

数组中相同的值排完序之后,其相对位置不变,就是稳定,否则就是不稳定
eg:下面的数组中如果排完序之后橙5被换到蓝5后面去了,就是不稳定的,反之是稳定的

那稳定的价值是什么呢?

比如说考试系统,考完之后要排名,考试的时候提交试卷以后自动判卷拿到成绩,成绩按照交卷顺序排到数组中,我们对数组排序,进行排名

要求:分数相同,先交卷的排在前面

如果稳定性差的排序肯定是可能会颠倒顺序,这不满足我们的要求

==注:==

直接选择排序是不保证稳定的(保证选大的时候只选后一个大的,选小的可以选前面的那一个)

如果我们按照图中的要求去排序

希尔排序是不稳定的,因为有可能相同大小的值被放预排到了不同组里面去,很有可能变

堆排序不稳定,当建完堆之后,把root和最后一个叶子一换,就把顺序变了

快排不稳定,由于找大找小的过程中可能存在交换,一换顺序有可能发生变化

高效性

就高效性来看的话,快排,堆排和归并都是
$$
O(N*log_2^N)
$$
综合来说最好的还是快排,堆排效率总体来说还是略慢快排,然后归并需要更多空间复杂度,另外希尔排序gap取值不同,效果不同

然后就是插入->冒泡->选择,选择很可惜是最次的

摩拳擦掌

1. 快速排序算法是基于（）的一个排序算法。

分治法
贪心法
递归法
动态规划法

2. 对记录（54,38,96,23,15,72,60,45,83）进行从小到大的直接插入排序时，当把第8个记录45插入到有序表时，为找到插入位置需比较（）次？（采用从后往前比较）

3. 以下排序方式中占用O（n）辅助存储空间的是

简单排序
快速排序
堆排序
归并排序

4.下列排序算法中稳定且时间复杂度为O(n^2^)的是（）

快速排序
冒泡排序
直接选择排序
归并排序

5.关于排序，下面说法不正确的是

快排时间复杂度为O(N*logN)，空间复杂度为O(logN)
归并排序是一种稳定的排序,堆排序和快排均不稳定
序列基本有序时，快排退化成冒泡排序，直接插入排序最快
归并排序空间复杂度为O(N), 堆排序空间复杂度的为O(logN)

6.下列排序法中，最坏情况下时间复杂度最小的是（）

堆排序
快速排序
希尔排序
冒泡排序

快排是不稳定的，快排时间复杂度最差是O(N^2^)

7.设一组初始记录关键字序列为(65,56,72,99,86,25,34,66)，则以第一个关键字65为基准而得到的一趟快速排序结果是（）(挖坑)

34，56，25，65，86，99，72，66
25，34，56，65，99，86，72，66
34，56，25，65，66，99，86，72
34，56，25，65，99，86，72，66

8. 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。用冒泡排序对数列4 5 6 3 2 1进行升序排序，则第3趟之后的结果是（）

4 3 2 1 5 6
4 5 3 2 1 6
2 1 3 4 5 6
3 2 1 4 5 6

冒泡是周围2个一次次排序交换，然后每一趟只做size-外层循环次

9. 使用选择排序对长度为100的数组进行排序，则比较的次数为（）

5050
4950
4851
2475

选择排序，每次都要在未排序的所有元素中找到最值，如果有n个元素，则
第一次比较次数： n - 1
第二次比较次数： n - 2
….
第n - 1次比较次数： 1
所有如果n = 100
则比较次数的总和：99 + 98 + …… + 1
共4950次。

10. 有字符序列 FBJGEAIDCH，现在打算对它按字母的字典顺序用希尔排序进行排序，那么在第一趟后（步长为5）的序列为（）

CAEBFDIGJH
AIDCHFBJGE
ABDCEFIJGH
BFJGEAIDCH

11. 现有数字序列 5 11 7 2 3 17，目前要通过堆排序进行降序排序，那么由该序列建立的初始堆应为（）

2 3 7 11 5 17
17 11 7 2 3 5
17 11 7 5 3 2
2 3 5 7 11 17

要降序排列，所以要建小堆，每次把堆顶元素放在当前堆的最后一个位置

12. 对数字序列28 16 32 12 60 2 5 72进行升序的快速排序（以第一个关键码为基准的方法），一次划分后的结果为（）

2 5 12 16 28 60 32 72
2 16 5 12 28 60 32 72
2 16 12 5 28 60 32 72
5 16 2 12 28 32 60 72

建堆要进行向下调整算法（从最后一个非叶子节点开始进行向下调整算法，直到根元素）
快速排序以基准值为中心，对元素进行划分，这里以28为基准值，则小于28的和大于28的进行交换，完成一次划分
首先：32和5交换： 28 16 5 12 60 2 32 72
然后60和2交换： 28 16 5 12 2 60 32 72
最后28和最后一个小于28的元素进行交换：2 16 5 12 28 60 32 72

13. 下列选项中，不可能是快速排序第2趟排序后的结果的是（）

2 3 5 4 6 7 9
2 7 5 6 4 3 9
3 2 5 4 7 6 9
4 2 3 5 7 6 9

快排的阶段性排序结果的特点是，第i趟完成时，会有i个以上的数出现在它最终将要出现的位置，即它左边的数都比它小，它右边的数都比它大。题目问第二趟排序的结果，即要找不存在2个这样的数的选项。
A: 第一趟的基准值可以为2，第二趟的基准值可以为3
B: 第一趟的基准值可以为2，第二趟的基准值可以为9
C: 第一趟的基准值只能是9，但是第二趟的基准值就找不出来，没有符合要求的值作为基准值，所以不可能是一个中间结果。
D: 第一趟的基准值可以为9，第二趟的基准值可以为5

14. 以下哪种排序算法对[1, 3, 2, 4, 5, 6, 7, 8, 9]进行排序最快（）

直接插入排序
快速排序
归并排序
堆排序

顺序有序最好的是直接插入排序复杂度是O(N)

15. 下面的排序算法中，初始数据集的排列顺序对算法的性能无影响的有（）

① 快速排序

② 希尔怕徐

③ 插入排序

④ 堆排序

⑤ 归并排序

⑥ 选择排序

①④⑤
④⑤⑥
②③⑥
②③⑤⑥

16. 用某种排序方法对关键字序列 25 84 21 47 15 27 68 35 20 进行排序，序列的变化情况采样如下：

20 15 21 25 47 27 68 35 84

15 20 21 25 35 27 47 68 84

15 20 21 25 27 35 47 68 84

请问采用的是以下哪种排序算法（）

选择排序
希尔排序
归并排序
快速排序

对于八大排序算法的源代码如有需要，可以到我的GitHub查看八大排序算法，如果大家觉得有收获的话，请给我点赞，关注和收藏吧，谢谢支持😄

Allen

https://allen9012.github.io/BlogNet/BlogNet/2022/09/18/%E5%85%AB%E5%A4%A7%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Allen !

数据结构和算法

Allen's OJ

2022-09-18 Allen

项目

Hash 容器

2022-09-04 Allen

高阶数据结构 Hash

八大排序算法

八大排序算法

Intro

插入排序

直接插入排序

实现插入排序

先写单趟排序

再写多趟，控制end的位置和插入的值

直接插排复杂度

希尔排序

实现希尔排序

一次希尔排序

完成多次排序，改变gap让其越来越接近顺序

希尔排序时间复杂度

2. 选择排序

直接选择排序

直接选择排序的想法

实现选择排序(不完全对)

改正选择排序

正确的选择排序

堆排序

实现堆排序

堆排序的时间复杂度

3. 交换排序

冒泡排序

基本想法

实现冒泡排序

时间复杂度分析

快速排序

基本想法（Hoare）

实现快速排序

实现多种方法

Hoare法（左右指针法）

挖坑法

前后指针法

时间复杂度测试

理想时间复杂度计算

优化快排

三数取中法（通过采取改进选key的方法来优化）

三数取中法+Hoare

三数取中法+前后指针

小区间排序优化

非递归快排

4. 归并排序

基本想法

实现归并排序

归并的复杂度

非递归实现归并排序

思路和注意事项

想法

注意事项

修改1

修改2

补充

5. 计数排序

基本想法

实现计数排序

时间复杂度分析

分析八大排序

八大排序分析

稳定性

高效性

摩拳擦掌

1. 快速排序算法是基于（ ）的一个排序算法。

2. 对记录（54,38,96,23,15,72,60,45,83）进行从小到大的直接插入排序时，当把第8个记录45插入到有序表时，为找到插入位置需比较（ ）次？（采用从后往前比较）

3. 以下排序方式中占用O（n）辅助存储空间的是

4.下列排序算法中稳定且时间复杂度为O(n^2^)的是（ ）

5.关于排序，下面说法不正确的是

6.下列排序法中，最坏情况下时间复杂度最小的是（ ）

7.设一组初始记录关键字序列为(65,56,72,99,86,25,34,66)，则以第一个关键字65为基准而得到的一趟快速排序结果是（）(挖坑)

8. 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。用冒泡排序对数列4 5 6 3 2 1进行升序排序，则第3趟之后的结果是（ ）

9. 使用选择排序对长度为100的数组进行排序，则比较的次数为（ ）

10. 有字符序列 FBJGEAIDCH，现在打算对它按字母的字典顺序用希尔排序进行排序，那么在第一趟后（步长为5）的序列为（ ）

11. 现有数字序列 5 11 7 2 3 17，目前要通过堆排序进行降序排序，那么由该序列建立的初始堆应为（ ）

12. 对数字序列28 16 32 12 60 2 5 72进行升序的快速排序（以第一个关键码为基准的方法），一次划分后的结果为（ ）

13. 下列选项中，不可能是快速排序第2趟排序后的结果的是（ ）

14. 以下哪种排序算法对[1, 3, 2, 4, 5, 6, 7, 8, 9]进行排序最快（ ）

15. 下面的排序算法中，初始数据集的排列顺序对算法的性能无影响的有（ ）

16. 用某种排序方法对关键字序列 25 84 21 47 15 27 68 35 20 进行排序，序列的变化情况采样如下：

你的赏识是我前进的动力

1. 快速排序算法是基于（）的一个排序算法。

2. 对记录（54,38,96,23,15,72,60,45,83）进行从小到大的直接插入排序时，当把第8个记录45插入到有序表时，为找到插入位置需比较（）次？（采用从后往前比较）

4.下列排序算法中稳定且时间复杂度为O(n^2^)的是（）

6.下列排序法中，最坏情况下时间复杂度最小的是（）

8. 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。用冒泡排序对数列4 5 6 3 2 1进行升序排序，则第3趟之后的结果是（）

9. 使用选择排序对长度为100的数组进行排序，则比较的次数为（）

10. 有字符序列 FBJGEAIDCH，现在打算对它按字母的字典顺序用希尔排序进行排序，那么在第一趟后（步长为5）的序列为（）

11. 现有数字序列 5 11 7 2 3 17，目前要通过堆排序进行降序排序，那么由该序列建立的初始堆应为（）

12. 对数字序列28 16 32 12 60 2 5 72进行升序的快速排序（以第一个关键码为基准的方法），一次划分后的结果为（）

13. 下列选项中，不可能是快速排序第2趟排序后的结果的是（）

14. 以下哪种排序算法对[1, 3, 2, 4, 5, 6, 7, 8, 9]进行排序最快（）

15. 下面的排序算法中，初始数据集的排列顺序对算法的性能无影响的有（）