万字总结——常见的八大排序算法（插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序）_常见的排序算法

一、排序

1.1 排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

1.2 常见的排序算法

时间复杂度：O(1)＜O($\sqrt{n}$)＜O(logn)＜O(n)＜O(nlogn)＜O(n²)＜O(n³)＜O(2ⁿ)＜O(n!)
logn 以几为底无关紧要，因为它们之间只差一个常数。

二、直接插入排序

2.1 基本思想

直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

实际中我们玩扑克牌时，就用了插入排序的思想:

2.3 步骤

1. 从第一个元素开始，此时认为这个元素有序
2. 将下一个元素（第二个元素）tmp往前插入，从后往前依次比较大小
3. 如果元素比tmp大，则将该元素往后移动一个位置再与前一个元素比较；如果该元素比tmp小，则将tmp置于该元素之后；如果tmp前没有元素，则将tmp置于第一个元素的位置
4. 此时前两个元素有序，取第三个元素作tmp，重复以上步骤

动图演示：

2.3 代码

以下代码全部默认为从小到大排序(升序)

void InsertSort(int* a, int n)
{
	//[0,end]有序，插入end +1的位置，让[0,end+1]有序
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
			a[end + 1] = tmp;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2.4 特性

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N²)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

三、希尔排序

3.1 基本思想

希尔排序法又称缩小增量法，是对直接插入排序的优化。
希尔排序法的基本思想是：先选定一个整数gap，把待排序文件中所有记录分成个组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后，取gap = gap/n + 1(n = 3/4...)或 gap/=2重复上述分组和排序的工作。当gap=1时，所有记录在统一组内排好序。

设置gap的目的：使数组快速接近有序，当最后gap到达1时，此时数组接近有序，便于直接插入排序。

3.2 步骤

1. 设定gap的值，每间隔gap的元素视为一个数组，对每组元素进行插入排序；
2. gap的值倍数式减小，每次gap的值减小时都重复步骤1；
3. 最后gap的值必然减小到1，此时就是对整个数组进行一次直接插入排序。

动图演示：

例如这组数据是
{8，9，1，7，2，3，5，4，6，0}
首次取gap=5，即视间隔为5的数为一组进行插入排序：
｛８　　　　３　　　　｝－＞
｛３　　　　８　　　　｝
｛　９　　　　５　　　｝－＞
｛　５　　　　９　　　｝
｛　　１　　　　４　　｝－＞
｛　　１　　　　４　　｝
｛　　　７　　　　６　｝－＞
｛　　　６　　　　７　｝
｛　　　　２　　　　０｝－＞
｛　　　　０　　　　２｝
即原先的数组变为
｛８９１７２３５４６０｝－＞
｛３５１６０８９４７２｝
当gap=2时，即视间隔为5的数为一组进行插入排序：
｛３　１　０　９　７　｝－＞
｛０　１　３　７　９　｝
｛　５　６　８　４　２｝－＞
｛　２　４　５　６　８｝
即
｛３５１６０８９４７２｝－＞
｛０２１４３５７６９８｝
当最后gap=1时，即直接插入排序。

依照这个思路写的循环是这样的：

void ShellSort(int* a, int n)
{
    int gap = n;
    while (gap > 1)
    {
        gap /= 2;    // gap /= 3 + 1;
        for (int j = 0; j < gap; j++)
        {
        	for (int i = j; i < n - gap; i+=gap)
        	{
        		//...
        	}
        }
1
2
3
4
5
6
7
8
9
10
11
12
13

方法二即将这两个循环整合在一起，先对每一组的第一段进行插入排序，再对每组的第二段插入排序…但效率上和以上代码是相同的。
以下代码便使用了方法二。

3.3 代码

void ShellSort(int* a, int n)
{
    int gap = n;
    while (gap > 1)
    {
        gap /= 2;    // gap /= 3 + 1;
        //gap > 1时都是预排序
        // gap = 1时就是直接插入排序
        //把间隔为gap的数据同时排
        for (int i = 0; i < n - gap; ++i)
        {
            int end = i;
            int tmp = a[end + gap];
            while (end >= 0)
            {
                if (a[end] > tmp)
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

3.4 特性

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样再排序就会很快。对整体而言，可以达到优化的效果。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在许多书中给出的希尔排序的时间复杂度都不固定：
   《数据结构(C语言版)》— 严蔚敏
   
   《数据结构-用面相对象方法与C++描述》— 殷人昆
   
   因为我们的gap是按照Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，我们暂时就按照：O(n^1.25)——1.6*O(n^1.25)来算。

四、选择排序

4.1 基本思想

选择排序的基本思想是：每一趟从待排序的元素中选出最小（/最大）的记录，顺序放在已排好序的子文件的最后（/最前），直到全部记录排序完毕。

4.2 步骤

1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始（尾部）位置；
2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾（开头）。
3. 重复步骤2，直到所有元素均排序完毕。

动图演示：

我们可以对此算法进行优化，在每次对未排序的元素进行遍历中同时选出最小和最大的元素，分别放在原序列的序列头和序列尾，这样只需遍历序列的一半次数即可。

4.3 代码

void Swap(int* p1, int* p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}
void SelectSort(int* a, int n)
{
    int begin = 0, end = n - 1;
    while (begin < end)
    {
        int maxi = begin, mini = begin;
        for (int i = begin; i <= end; i++)
        {
            if (a[i] > a[maxi])
            {
                maxi = i;
            }
            if (a[i] < a[mini])
            {
                mini = i;
            }
        }
        Swap(&a[mini], &a[begin]);
        if (maxi == begin)//考虑特殊情况
        {
        //当begin和maxi相同的时候,由于a[mini]和a[begin]进行了交换，最大值不在原本的位置，所以要换回来
            maxi = mini;
        }
        Swap(&a[maxi], &a[end]);
        ++begin;
        --end;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

4.4 特性

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用；
2. 时间复杂度：O(N²)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

五、堆排序

5.1 基本思想

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

具体讲解见：C语言实现二叉树、堆、堆排序

5.2 步骤

1. 对要排序的数组建堆，此时堆顶（也就是数组第一个元素）要么最大，要么最小；

2. 交换数组第一个和最后一个元素；

3. 对堆顶的元素进行向下调整，保持最大堆或最小堆的特性；

4. 数组长度减1；

5. 重复步骤2、3、4，直至数组长度为1（下标为0），结束。

动图演示：

步骤解析：

5.3 代码

void HeapSort(int* a, int n)
{
	//升序建大堆，降序建小堆，取决于AdjustDown函数中的符号
    for (int i = (n-1-1)/2; i >= 0; i--)
    {
        AdjustDown(a, n, i);
    }
    
    int end = n - 1;//最后一个元素的下标
    while (end > 0)
    {
        Swap(&a[0], &a[end]);
        AdjustDown(a, end, 0);
        --end;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

5.4 特性

1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

六、冒泡排序

6.1 基本思想

冒泡排序是所有排序里最简单的一种，其基本思想是：对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部。

6.2 步骤

1. 从a[0]开始，与下一个元素a[1]比较，若是逆序则交换；再让a[1]与下一个元素a[2]比较,逆序则交换……重复此步骤，直到a[n-2]与a[n-1]比较完为止；
2. 此时a[n-1]最大，且可视为有序，接下来只需要比较前n-1个数，找出最大的数挪到a[n-1]前面；
3. 重复步骤1，直到比较完a[n-3]与a[n-2]为止，此时最后两个数有序；
4. 重复以上步骤。

动图演示：

6.3 代码

void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		bool exchange = false;//如果变量未改变则表示数组已经有序，提前结束
		for (int j = 1; j < n - i; j++)
		{
			if (a[j - 1] > a[j])
			{
				int tmp = a[j];
				a[j] = a[j - 1];
				a[j - 1] = tmp;
				exchange = true;
			}
		}
		if (!exchange)
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

6.4 特性

1. 容易理解，但效率极低；
2. 时间复杂度：O(n²)
3. 空间复杂度：O(1)
4. 稳定性：稳定

七、快速排序

7.1 基本思想

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素key作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

比如给一组数据，选取一个值key（通常是最左边的值或最右边的值），经过操作后使key左边的数都比key小，key右边的数都比key大，这样就把数据分成了两组，再对两边的数据进行如上操作，直到每组数据只剩1个数据或没有数据为止。

这是快速排序递归实现的主要思路，我们发现它和二叉树前序遍历有些像，学习二叉树过后会有更好的理解。

7.2 步骤与代码

以下均以升序为例。

将区间按照基准值划分为左右两半部分有三种常见方式：

7.2.1 版本一: hoare版本

Hoare版本的快速排序是一种基于分治策略的排序算法，我们先考虑单趟排序的步骤：

1. 先选取数组左边（右边）的第一个数作为key；
2. 定义一个左下标left指向最左边的数，定义一个右下标right指向最右边的数；
3. 让right先往左（left先往右）遍历寻找一个比key小（大）的数字，找到后停下来；
4. 再让left向右（right向左）遍历寻找一个比key大（小）的数字，找到后停下来；
5. 把找到的这两个数交换；
6. 重复3、4、5步骤；
7. 直到left和right相遇，再把这个相遇的位置的数字和key交换就完成了一趟快速排序（此时左边的数比key小，右边的数比key大）。

图片演示：(以最左边的值为key)

这样一次单趟排序就完成了。但在写代码时有几个坑一定要注意：

1. left必须从key开始不能从keyi+1开始，假设key是数组中最小的，代码就错误了。（同样right不能从keyi-1开始）

2. 在二层循环中left(right)与key比较时要加上等于号。 按照思路，arr[left]大于key时停止，反过来，继续走的判断条件即arr[left]小于key。但是当遇到等于key的元素时，代码就会陷入死循环，比如这种情况：
   
   也可能导致数组越界，比如这种情况，right一直没遇到比0小的数字，且会越过0：
   
   所以务必要加上等于号。

3. 我们在二层循环比较left与right为置的元素时，是不受一层循环left < right条件约束的，这样当left与right相遇时可能不会终止（加等号后），比如。因此要在内层循环中也加上条件left < right。但要注意的是，left < right条件一定要加在前面，因为&&有短路性质，如果加在后面就先越界再判断了。

4. 若选最左边的数为key，那么right先走（若选最右边的数为key，那么left先走）。因为在交换后，left指向的元素一定比key小，right指向的元素一定比key大。
   如果right先走，要么在比key小的元素位置停，left与right相遇时一定在比key小的位置，要么right先遇到left，这时也在比key小的位置，交换后这个比key小的元素就在key的左边了。
   而如果left先走，情况一：left走到比key大的元素位置，right遇left；情况二：left直接遇到right，这时它们指向的元素比key大，这两种情况下，它们相遇位置的元素与key交换后，就跑到了key的左边，但是key左边的要求是比key小，因此要注意代码顺序。
   

单趟排序代码：

void Swap(int* a,int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp; 
}
void PartSort(int* arr,int left,int right)
{
	int keyi = left;
	while (left < right)//left等于right时退出循环
	{
		while (left < right && arr[right] >= arr[keyi])//防止越界加上left < right条件
		{
			right--;//right先走
		}
		while (left < right && arr[left] <= arr[keyi])
		{
			left++;
		}
		Swap(&arr[left], &arr[right]);
	}
	Swap(&arr[keyi], &arr[left]);//此时left与right相同
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

只要将单趟排序写出来，整个排序就变得简单了，递归即可。

在单趟排序后，再分别对key左边的数据与右边的数据进行排序，使其变为有序，这样整个数组便有序了。因此我们需要知道key的下标，所以将PartSort的返回类型改为int类型，返回keyi。
别忘了写返回的条件，当每个部分的元素个数<=1时就意味着无需排序了。

图示：

完整代码:

void Swap(int* a,int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp; 
}
int PartSort(int* arr,int left,int right)
{
	int keyi = left;
	while (left < right)//left等于right时退出循环
	{
		while (left < right && arr[right] >= arr[keyi])//防止越界加上left < right条件
		{
			right--;
		}
		while (left < right && arr[left] <= arr[keyi])
		{
			left++;
		}
		Swap(&arr[left], &arr[right]);
	}
	Swap(&arr[keyi], &arr[left]);//此时left与right相同
	return keyi;
}

void QuickSort(int* arr, int begin, int end)//使用时要传下标
{
	if (begin >= end)
		return;
	int keyi = PartSort(arr, begin, end);
	//[begin,keyi+1] keyi [keyi+1,end]
	QuickSort(arr, 0, keyi - 1);
	QuickSort(arr, keyi + 1, end);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

---

7.2.2 版本二：挖坑法

挖坑法在效率上与hoare版本没有什么不同，但挖坑法更易于理解。挖坑法的单趟排序与hoare版本思路大体一样，但结果可能不同，但快排代码相同。

步骤：

1. 以最左边的元素为key，key所在位置的下标就是一个坑hole，这便是挖坑（理解为把它存到key中，但这个位置上元素还在）；
2. 定义left和right表示下标，它们分别指向数列的最左和最右两个元素；
3. 从right开始，把它所指向的元素和key比较。如果比key大或等于，则right向左移动；如果比key小，则把right所指向的元素填入坑中，right所指向的位置又挖了一个坑（挖一填一）；
4. 接下来，我们切换到left指针进行比较。如果left指向的元素等于小于key，则left向右移动；如果元素大于key，则把left指向的元素填入坑中，left所在的位置成为坑；
5. 如果两个指针相遇，相遇的位置必然是个坑，把key放到最后的坑中。

图片演示：

完整代码：

int PartSort2(int* arr, int left, int right)
{
	int key = arr[left];
	int hole = 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;
}

void QuickSort(int* arr, int begin, int end)
{
	if (begin >= end)
		return;
	int keyi = PartSort2(arr, begin, end);
	//[begin,keyi+1] keyi [keyi+1,end]
	QuickSort(arr, 0, keyi - 1);
	QuickSort(arr, keyi + 1, end);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

---

7.2.3 版本三： 前后指针法

前后指针法相较于前两种方法更简单，但理解上更抽象，没有前两种方法直观。三种方法在效率上是一样的。

步骤：

1. 以最左边的元素为key，初始化两个指针（下标），prev指向序列的第一个元素，cur指向prev的下一个元素；
2. 如果cur位置的元素大于key，那么继续让cur指针向右移动；
3. 如果cur位置的元素小于key，那么prev位置加一，并交换prev和cur所指向的元素，再把cur的位置加一；（prev是走了后再换，cur是换了后再走）
4. 重复上述过程，直到cur指针超过序列的最右侧位置；
5. 最后，将prev指向的元素与key所在的位置交换，就划分了左右区间。

最开始prev和cur是相邻的，当cur遇到比key大的元素时，prev与cur开始拉开距离，并且prev与cur之间的元素都是比key大的元素，因为cur一遇到比key小的元素就与++prev交换了（++prev是先自增走到比key大的位置再交换），这样保证prev走过的位置都比key要小，当cur走完的时候，prev正处在最右边一个比key小元素的位置，与key的位置交换后便完成了单趟排序。

图片演示：

完整代码：

void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
//前后指针法
int PartSort3(int* arr, int left, int right)
{
	int keyi = left;//最后要交换取key的下标
	int prev = left;
	int cur = prev + 1;
	while (cur <= right)
	{
		//&&左边为真才会执行右边
		if (arr[cur] < arr[keyi] && ++prev != cur)//相邻时交换就是自己和自己交换无意义
		{
			//注意++prev写条件里了，prev已经走到了比key大的位置
			Swap(&arr[prev], &arr[cur]);
		}
		cur++;//不管遇到比key大的还是小的，cur都要自增
	}
	Swap(&arr[keyi], &arr[prev]);
	return prev;
}

void QuickSort(int* arr, int begin, int end)
{
	if (begin >= end)
		return;
	int keyi = PartSort3(arr, begin, end);
	//[begin,keyi+1] keyi [keyi+1,end]
	QuickSort(arr, 0, keyi - 1);
	QuickSort(arr, keyi + 1, end);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

动图演示：

7.3 优化

在此之前，请大家试试用快排来通过这道题目：排序数组

但是你会发现快排过不了此题，反而别的排序可以过，因为这是一道专门针对快排出的题目！因此，我们来看看快排如何优化。

优化1. 三数取中法选key

快速排序的时间复杂度在最好情况下是O(n*logn)，但在最坏情况下是O(n²)（比如有序数列），三数取中是对有序序列情况的优化。

三数取中，是指选取数组最左、最右和中间三个元素，取中间大小的那个元素与key所在的位置交换，那么这个数就成了key（key的位置没变，不影响之前的代码思路），这样能让序列划分得更均匀一些，减小时间复杂度。

代码：

int GetMidIndex(int* arr, int left, int right)
{
	int mid = (left + right) / 2;
	if (arr[left] < arr[mid])
	{
		if (arr[mid] < arr[right])
			return mid;
		//arr[mid] > arr[right]
		else if (arr[left] < arr[right])
			return  right;
		//arr[left] > arr[right]
		else return left;
	}
	//arr[left] > arr[mid]
	else
	{
		if (arr[right] < arr[mid])
			return mid;
		else if (arr[right] < arr[left])
			return right;
		else return left;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

通过GetMidIndex()函数找到中间大小元素的下标midi，再把这个元素与序列最左边的元素交换位置（以key为最左边元素为例），只需在PartSort()函数开头加上代码：

int midi = GetMidIndex(arr,left,right);
Swap(&arr[left],&arr[midi]);
1
2

完整代码：

int GetMidIndex(int* arr, int left, int right)
{
	int mid = (left + right) / 2;
	if (arr[left] < arr[mid])
	{
		if (arr[mid] < arr[right])
			return mid;
		else if (arr[left] < arr[right])
			return  right;
		else return left;
	}
	else
	{
		if (arr[right] < arr[mid])
			return mid;
		else if (arr[right] < arr[left])
			return right;
		else return left;
	}
}
void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

//hoare法
int PartSort1(int* arr, int left, int right)
{
	int midi = GetMidIndex(arr, left, right);
	Swap(&arr[left], &arr[midi]);
	int keyi = left;
	while (left < right)
	{
		while (left < right && arr[right] >= arr[keyi])
		{
			right--;
		}
		while (left < right && arr[left] <= arr[keyi])
		{
			left++;
		}
		Swap(&arr[left], &arr[right]);
	}
	Swap(&arr[keyi], &arr[left]);
	return keyi;
}

//挖坑法
int PartSort2(int* arr, int left, int right)
{
	int midi = GetMidIndex(arr, left, right);
	Swap(&arr[left], &arr[midi]);
	int key = arr[left];
	int hole = 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;
}

//前后指针法
int PartSort3(int* arr, int left, int right)
{
	int midi = GetMidIndex(arr, left, right);
	Swap(&arr[left], &arr[midi]);
	int keyi = left;
	int prev = left;
	int cur = prev + 1;
	while (cur <= right)
	{
		if (arr[cur] < arr[keyi] && ++prev != cur)
		{
			Swap(&arr[prev], &arr[cur]);
		}
		cur++;
	}
	Swap(&arr[keyi], &arr[prev]);
	return prev;
}


void QuickSort(int* arr, int begin, int end)
{
	if (begin >= end)
		return;
	int keyi = PartSort3(arr, begin, end);
	//[begin,keyi+1] keyi [keyi+1,end]
	QuickSort(arr, 0, keyi - 1);
	QuickSort(arr, keyi + 1, end);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

但是！！！此题采用三数取中任然过不了，因为它同时也针对了三数取中（三个数都接近最大或最小），所以mid就不能去中间值了，可以使用随机数（仅限此题），把PartSort中的mid定义为left + (rand()%(right - left))就好。

int mid = left + (rand()%(right - left));
1

---

优化2. 小区间优化——使用插入排序(见-8.6)

---

优化3. 三路划分

三路划分是针对重复元素情况的一种方法，我们知道原本的快排并没有特地去针对重复元素，所以在序列全是重复元素或大多重复元素时，效率就会变得很低。此题就有这样一个测试用例，所以快排会<超出时间限制>。

使用三路划分在应对普通数据时效率略低一些，日常不需要使用，但它能应对的场景更全面。

思路：
三路划分的目的是使key位于中间，比key小的元素在key的左边，比key大的元素在key的右边，形成三个区间，这样递归时只用递归最左边和最右边的区间。

三路划分的实现思路与前后指针法的思想类似
步骤：

1. 定义left指针（下标）指向序列开头(key)，right指针指向序列结尾，cur指针指向left的下一个位置；
2. 如果cur位置的元素小于key，那么交换left位置与cur位置的元素，left右移一位，cur右移一位；
   如果cur位置的元素大于key，那么交换cur位置的元素与right位置的元素，right左移一位；
   如果cur位置的元素等于key，cur右移一位；
3. 重复步骤2，直到cur > right为止，此时right指向最后一个key。

图示：

不难发现，left所指向的值永远是key，left的作用就是把key换到后面去，而cur的作用是把不是key的值往前面或后面换。
代码：
相当于把PartSort的代码优化了，这里直接写在了QuickSort中

void QuickSort(int* arr,int begin,int end)
{
  if(begin >= end)
  return;
  int left = begin,right = end;
  int cur = left + 1;
  //三数取中防有序（midi随机版）
  int midi = left + (rand()%(right - left));
  Swap(&arr[left], &arr[midi]);
  //三路划分防重复
  int key = arr[begin];
  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//=key
    {
      cur++;
    }
    //区间变成[begin,left-1],[left,right],[right + 1,end]
  }
  //中间区间不用递归
  QuickSort(arr,begin,left-1);
  QuickSort(arr,right+1,end);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

这样就AC了

7.4 快排的非递归形式

相比于非递归形式，递归有一些可能的弊端：

1. 栈溢出：递归形式的快速排序在处理大量数据时可能导致栈溢出。因为每次递归调用都会消耗一定的栈空间，当递归深度过大时，超出了系统栈空间限制，就会引发栈溢出错误。非递归形式的快速排序则不存在这个问题，因为它使用循环代替递归，不需要额外的栈空间。
2. 效率问题：在某些情况下，递归形式的快速排序可能效率较低。当数据规模较大时，递归调用会产生一定的额外开销，这可能导致性能下降。非递归形式的快速排序可以避免这种开销，因为它通过循环实现，没有递归调用的额外成本。

快排非递归形式要用到手写的栈¹（c++可直接使用）,所以先要引入写好的栈"Stack.h"

思想与递归形式相同，都是先单趟排序整个区间[begin,end]，再排[begin,keyi-1],再排[keyi+1,end]…只不过非递归是用循环实现的。

步骤：

1. 创建一个栈，先将end入栈，再将begin入栈（这样出栈的时候先出begin，方便理解，反着来也可以）；
2. 取栈顶元素定义为left,并出栈，再取栈顶元素定义为right，并出栈；即单趟排序的区间，对区间进行单趟排序并取返回值keyi；
3. 如果keyi - 1大于left，就表明这个区间有2个及以上的元素，将keyi - 1和left分别入栈；如果keyi + 1小于end，将end与keyi + 1分别入栈；
4. 重复步骤2、步骤3，直到栈为空为止；
5. 销毁栈。

代码：

void QuickSortNonR(int* arr, int begin, int end)
{
    Stack st;
    StackInit(&st);//初始化
    StackPush(&st, end);
    StackPush(&st, begin);
    while (!StackEmpty(&st))
    {
        int left = StackTop(&st);//后入的begin,先取左
        StackPop(&st);
        int right = StackTop(&st);
        StackPop(&st);
        int keyi = PartSort(arr, left, right);//单趟排序，三种都可
        if (keyi + 1 < right)
        {
            StackPush(&st, right);
            StackPush(&st, keyi + 1);
        }
        if (keyi - 1 > left)
        {
            StackPush(&st, keyi - 1);
            StackPush(&st, 0);
        }
    }
    StackDestroy(&st);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

八、归并排序

8.1 基本思想

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

对于两个有序序列合并，我们可以使用双指针的方法完成。

可以参考此题：牛客 - 合并有序序列

#include <stdio.h>

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int a[n],b[m];//牛客可用变长数组
    for(int i = 0; i < n; i++)
        scanf("%d",&a[i]);
    for(int i = 0; i < m; i++)
        scanf("%d",&b[i]);
    int add[n+m];
    int i = 0,j = 0;//分别指向两个数组的第一个元素
    int l = 0;
    while(i < n && j < m)//结束条件，防止越界
    {
        if(a[i] <= b[j])
            add[l++] = a[i++];
        else 
            add[l++] = b[j++];
    }
    //还要考虑数组a或数组b中剩下的元素
    while(i < n)
    {
        add[l++] = a[i++];
    }
    while(j < m)
    {
        add[l++] = b[j++];
    }
    for(int e = 0; e < n+m; e++)
        printf("%d ",add[e]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

归并排序正是这个思路，我们要做的就是把序列平均分成左右两个序列，使左右两个序列有序。这时要用到递归分别对左右区间分割，直到每个区间只剩下两个元素，将这两个元素分割，那么左右元素即有序，对其进行合并，那么这个区间就有序了。这个思想类似二叉树的后序思想。

需要注意的是，归并排序并不能在原数组上进行，因为会覆盖掉原本的数据，所以要格外开辟一个数组用来储存排序后的元素，然后将替换回原数组，这也是归并排序的弊端。

8.2 步骤

1. 开辟一个与原数组大小一致的数组tmp，对原数组a进行归并；
2. 取数列首下标begin与尾下标end的中间值mid，分别对左区间[begin,mid]与右区间[mid + 1,end]递归，直到区间只有一个元素就返回；
3. 定义begin1和end1分别指向左区间的首下标和尾下标，定义begin2和end2分别指向右区间的首下标和尾下标，将这两个有序序列（区间）合并，存入tmp；
4. 将tmp中合并的序列拷贝到原数组；
5. 重复步骤2，步骤3，步骤4。

图解：

动图演示：

8.3 代码

void _Mergesort(int* a, int* tmp, int begin, int end)
{
	if (begin == end)//递归返回条件
		return;
	int mid = (begin + end) / 2;//取中间下标
	//后序递归
	_Mergesort(a, tmp, begin, mid);//递归左区间
	_Mergesort(a, tmp, mid + 1, end);//递归右区间
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;//记录tmp的下标
	//合并两个有序序列
	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++]; 
	}
	//替换，注意要从+begin的位置开始替换
	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);//开辟
	_Mergesort(a, tmp, 0, n - 1);//递归函数
	free(tmp);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

8.4 特性

1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)，递归占logN,拷贝占N
3. 空间复杂度：O(N)
4. 稳定性：稳定

8.5 归并排序的非递归形式

归并的非递归形式与递归形式略有不同，递归是先左后右区间，但是非递归是整个序列一起操作，先11归，再22归，44归…

·我们可以定义变量gap表示每个区间的元素个数，比如gap = 1,11归，gsp = 2，22归，gap呈 2ⁿ 增长，直到gap >= n（序列总长度）结束。
我们可以通过循环来控制要合并的两个区间位置：

	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;
		//...
	}
1
2
3
4
5
6

[begin1,end1],[begin2,end2]表示要合并的两个区间，i走到下个要合并区间的起始位置。
但实际情况不会如上图演示的那么简单，只要数据量不是2ⁿ,代码就会出错。
出错情况有三种：

解决方式有两种：
方式一：归并一次拷贝一次
这种方法采用的是退出的思路

• 对于情况一和情况二，在前几组，归并一组就拷贝回原数组；最后一组的第二个区间不存在，那就不用归并，直接退出循环不拷贝。
• 对于情况三，则需要修改end2的位置再进行归并。

代码：

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	int gap = 1;//每个区间数据个数
	while (gap < n)
	{
		int j = 0;//tmp数组的下标
		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;
			if (end1 >= n || begin2 >= n)//无需归并与拷贝
			{
				break;
			}
			//修正
			if (end2 >= n)
			{
				end2 = n - 1;
			}
			//归并
			while (begin1 <= end1 && begin2 <= end2)
			{
				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;
	}
	free(tmp);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

方法二：归并完拷贝整个序列
在所有组的gap个数据归并完时，将tmp整体拷贝回原序列，这种方法采用的是修正的思路。

• 当end1越界，end1修正为n - 1
• 当begin2、end2越界，[begin2,end2]修正为不存在(begin2 > end2)的区间
• 当end2越界，end2修正为n - 1

代码：

void MergeSortNonR2(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	int gap = 1;//每个区间数据个数
	while (gap < n)
	{
		int j = 0;//tmp数组的下标
		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;
			//修正
			if (end1 >= n)
			{
				end1 = n - 1;
				begin2 = n + 1;
				end2 = n;
			}
			else if (begin2 >= n)
			{
				begin2 = n + 1;
				end2 = n;
			}
			else if(end2>= n)
			{
				end2 = n - 1;
			}
			//归并
			while (begin1 <= end1 && begin2 <= end2)
			{
				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, tmp , sizeof(int) * n) ;
		gap *= 2;
	}
	free(tmp);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

8.6 快排和归并的的小区间优化

小区间优化是一种策略，旨在在数组元素较少时避免过多的递归调用，从而减少资源消耗，提高算法效率，算是一种锦上添花的优化。

对于小规模的数组，插入排序可能会更快。当子数组的大小小于一定阈值（如10），可以切换到插入排序。

快排：

void QuickSort(int* arr, int begin, int end)
{
	if (begin >= end)
		return;
	if(end - begin + 1 < 10)
	{
		InsertSort(a + begin, end - begin + 1);
		return;
	}
	int keyi = PartSort3(arr, begin, end);
	//[begin,keyi+1] keyi [keyi+1,end]
	QuickSort(arr, 0, keyi - 1);
	QuickSort(arr, keyi + 1, end);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

归并：

void _Mergesort(int* a, int* tmp, int begin, int end)
{
	if (begin == end)
		return;
	if(end - begin + 1 < 10)
	{
		InsertSort(a + begin, end - begin + 1);
		return;
	}
	//...剩下代码与原代码相同
}
1
2
3
4
5
6
7
8
9
10
11

九、计数排序

9.1 基本思想

经常刷题的可能对计数更熟悉，因为它经常被用到。

计数排序（Counting Sort）是一种非基于比较的排序算法，它的优势在于在对一定范围内的整数排序时，它的复杂度为O(n+k)，快于任何比较排序算法。

计数排序的基本思想是：通过统计每个元素出现的次数，然后根据这些统计信息构建有序的结果数组。

比如{1,5,2,1,7,5,5}这个数组中，1出现了2次，2出现了1次，5出现了3次，7出现了1次。
那么就排序为2个1,1个2,3个5,1个7。

9.2 步骤

1. 确定数值范围：确定待排序元素的数值范围，即最小值（min）和最大值（max）。这个范围将用于创建一个统计数组（计数数组），该数组的大小为 max - min + 1；
2. 初始化统计数组： 创建一个统计数组，其索引范围为从 [0 ,max - min]，其所有元素都被初始化为0，用来计数；
3. 累积计数： 遍历统计数组每个元素出现的次数，对于每个元素，将其值减去最小值的值作为统计数组的索引；
4. **生成排序结果:**按元素顺序和个数一个一个拷贝回原数组。

9.3 代码

#include <stdlib.h>
#include <string.h>
void CountSort(int* a, int n)
{
	int max = a[0], min = a[0];
	for (int i = 0; i < n; i++)
	{
		if (a[i] > max)
			max = a[i];
		if (a[i] < min)
			min = a[i];
	}
	int range = max - min + 1;//范围
	int* countA = (int*)malloc(sizeof(int) * range);
	memset(countA, 0, range * sizeof(int));//初始化为0
	//统计每个元素出现的次数
	for (int i = 0; i < n; i++)
	{
		countA[a[i] - min]++;
	}
	//排序
	int k = 0;
	for (int i = 0; i < range; i++)
	{
		while (countA[i]--)
		{
			a[k++] = i + min;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

9.4 特性

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 只适用于整型；
3. 时间复杂度：O((N+Range))
4. 空间复杂度：O(Range)

---

1. 关于C语言实现栈 ↩︎