排序

排序的概念

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

稳定性：假定在待排序的记录序列中，存在多个具有相同关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的，否则称为不稳定的。

内部排序：数据元素全部放在内存汇中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能再内外存之间移动数据的排序。

常见的排序算法

  • 插入排序
    • 直接插入排序
    • 希尔排序
  • 选择排序
    • 选择排序
    • 堆排序
  • 交换排序
    • 冒泡排序
    • 快速排序
  • 归并排序
    • 归并排序

没有一个排序能解决所有问题，它们各有特点。

插入排序

基本思想

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

例如：玩扑克牌，理牌的过程。先把你的牌放到一堆，你先不要动，发完之后直接将你所有的牌拿起来，进行理牌。

**时间复杂度是O(n²)**。

最坏情况——逆序(6,5,4,3,2,1)就是一直都要放到第一个位置，完成升序。

最好情况——顺序(1,2,3,4,5,6)没有一个数据需要挪动。

直接插入排序

把第一个数当做一个有序区间，把第二个数当做要插入的数进行比较大小，重新排序，然后把前两个数当做一个有序区间……依次类推。

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void InsertSort(int* a, int n)//升序实现(降序同理)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int temp = a[end + 1];//将要插入的数赋值给temp，因为跟前面的数进行比较的，end位置的数要移动到end+1上
		while (end >= 0)
		{
			if (temp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;//完成两种情况，1在中间找到了位置插入，2比所有的元素都小，插入到第一位。
			}
		}
		a[end + 1] = temp;
	}
}
解释&图示
1
2
3
4
5
6
7
8
/*解释:
	数组中[0,end]区间是有序的,要插入的数在end+1这个位置上，
	将end+1这个位置上的值插入到[0,end]中，最后完成排序的数组[0,end+1]这个新的区间也是有序的*/
/*		1.定义一个end找到数组的结尾元素(就是从第一个元素开始定义结尾)
		2.定义一个end+1找到end的下一个位置
		3.从end+1这个位置依次往前(end--)进行比较，如果比前一个数小就将end位置上的这个数放到end+1上
		4.如果大于等于前面的这个数就放到前面的这个数的后面
*/

image-20210622181717080

个人理解
1
2
3
4
5
6
7
/*理解:
	就是将一个数组分成几组，依次进行排序，先取数组中第一个元素该元素下标为0，这时候end就是0,end+1就是他后面的元素，将end+1这个位置上的元素与end上的这个元素进行比较大小，完成第一次排序。
	接着end是1，end+1就是2，将数组下标为2的这个元素与前面两个是元素进行比较，完成第二次排序。
	如果end+1比end大就跳出当前while循环，a[end+1] = temp就相当于没动。
	......依此类推。
	知道end=元素个数-1，end+1就是最后一个元素的下标
*/
动画演示

代码测试
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
#include<stdio.h>
//直接插入排序
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int temp = a[end + 1];
		while (end >= 0)
		{
			if (temp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = temp;
	}
}
//打印输出
void PrintArry(int* a,int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
}
void TestInsertSort()
{
	int a[] = { 5,4,2,6,1,3 };
	InsertSort(a, sizeof(a) / sizeof(int));
	PrintArry(a, sizeof(a) / sizeof(int));
}
int main(void)
{
	TestInsertSort();
	return 0;
}

image-20210622191017197

希尔排序

可以认为是在直接插入排序的优化。

步骤：

  1. 先进行预排序，让数组接近有序(不用挪很多)。
  2. 直接插入排序。
预排序

分组排

在直接插入排序中，最坏的情况就是逆序(6,5,4,3,2,1)了， 我们要挪动很多次。

假设间隔gap为一组，假定gap为2.

使得大的数更快的移到后面，小的数更快的移动到前面。

进行多组间隔为gap的预排序，gap从大到小，越接近有序。

gap越大，大的数越快到达后面，小的数越快到达前面。

gap越大，预排完，越不接近有序。

gap越小，预排完，越接近有序。

间隔gap为1，就是直接插入排序。

图示

image-20210622200937700

预排序代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
voidShellSort(int* a, int n)
{
	int gap = 2;//gap=1时就是直接插入排序
	for (int i = 0; i < n - gap; i++)
	{
		int end = i;
		int temp = a[end + gap];
		while (end >= 0)
		{
			if (temp < a[end])
			{
				a[end + gap] = a[end];
				end -= gap;
			}
			else
			{
				break;
			}
		}
		a[end + gap] = temp;
	}
	
}

image-20210623100526254

解释
1
2
3
4
5
6
7
/*
这个代码巧妙就巧妙在于，可以把间隔为gap的多组数据进行同时插入排序
假定gap=2分为多组
1.当i=0时，end = 0;end+1=2;
2.i = 1时，end = 1;end +1 = 3;
......
*/
动画演示

gap到底给多少

gap给的大，大的数去后面快，小的数去前面也快。整体的增益明显。

gap给固定的值是不对的，同一个gap，数据越多效果越差。

所以gap给的值一般与n有关，前提：保证最后gap是1，>1的时候都是预排序，要保证最后一次gap为1进行直接插入排序

代码实现
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
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int temp = a[end + gap];
			while (end >= 0)
			{
				if (temp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = temp;
		}
	}
}
代码测试
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
#include<stdio.h>
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int temp = a[end + gap];
			while (end >= 0)
			{
				if (temp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = temp;
		}
	}
}
//打印输出
void PrintArry(int* a,int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
}
void TestInsertSort()
{
	int a[] = { 6,5,4,3,2,1 };
	ShellSort(a, sizeof(a) / sizeof(int));
	PrintArry(a, sizeof(a) / sizeof(int));
}
int main(void)
{
	TestInsertSort();
	return 0;
}

image-20210623114920050

速度对比

那么希尔排序在执行速度方面到底比直接插入排序要快多少呢，我们编写一个代码来测试他的执行速度。

注意

在测试速度的时候可以将解决方案改为Release,Release的优化更多，执行速度会快一些。

image-20210623202316892

代码实现
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
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
//直接插入排序
void InsertSort(int* a, int n)//升序实现(降序同理)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int temp = a[end + 1];
		while (end >= 0)
		{
			if (temp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = temp;
	}
}
//希尔排序
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int temp = a[end + gap];
			while (end >= 0)
			{
				if (temp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = temp;
		}
	}
}
//测试排序性能
void TestSortSpeed()
{
	srand(time(0));
	//创建2个数据个数为100000万个的数组来测试两个排序所用的时间
	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:\t%d\n", end1 - begin1);
	printf("ShellSort:\t%d\n", end2 - begin2);
	//释放
	free(a1);
	free(a2);

}
int main(void)
{
	TestSortSpeed();	
	return 0;
}

结果：

image-20210623200420146

很明显，希尔排序的效率快了不是一星半点。

时间复杂度

希尔排序——gap =2；log以2为底N的对数，gap =3;log以3为底N的对数

​ 解释:

image-20210623201432081

当gap很大的时候，数据跳的就很快，差不多每个数据都会挪一次，挪了N次。下面的预排序时间复杂度是O(N)。

image-20210623201926854

当gap很小的时候，进行的预排序就越接近有序,这时的时间复杂度也是O(N)。

综上所述，希尔排序的时间复杂度是O(logN*N)或者O(log3 N *N)以3为底N的对数乘N。（3是gap，gap是可以改变的）

（时间复杂度logN的底数在没有的定说明的情况下都是1）

也有的说它的平均时间复杂度是O(N^1.3)

假设有10万个数，直接插入排序时间复杂度N^2 = 10w*10w = 100亿

希尔排序时间复杂度N*logN = 10w *log20w = 10w *17

可以看出二者的效率差的很多。

选择排序

基本思想

每次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部的待排序数据元素排完。

直接选择排序

几乎是最简单的一个排序，最好理解的排序，选出最小的数放到前面。

这里实现的是一个比较优化的版本——一次选出两个数。

代码实现
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
void SelectSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int mini = begin;
		int maxi = end;
		for (int i = begin; i <= end; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}
		Swap(&a[begin], &a[mini]);
        //begin和maxi的重叠情况
        /*解决数组下标为begin这个位置的元素恰好就是maxi,
        	经过上面这个Swap(&a[begin], &a[mini]);
        	把对应数组下标[maxi]这个位置的值换到了数组下标				[mini]这个位置上，
        	此时的最大值在数组[mini]这个下标处。
        */
		if (begin == maxi)
		{
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);
		begin++;
		end--;
	}
}
注意

begin和maxi的重叠情况，如下图所示情况，相关解释已在上面的代码中给出。

image-20210628172121776

动画图解

时间复杂度

O(N²)

N,N-2.N-4……

直接选择排序几乎是效率最差的一个排序

堆排序

解释

堆排序涉及到二叉树了，(相关链接——【树】之二叉树(C语言)(含图解)_半生瓜のblog-CSDN博客),这篇文章中二叉树是用链表来实现的，除了用链表，二叉树其实还可以用数组来实现，按层序来处理。

**堆的逻辑结构是一棵完全二叉树(每一层都是满的，不满的是从左往右顺序放的)**。——想象出来的

image-20210624172913562

堆的物理结构是一个数组。

image-20210624172928416

也就是说，我们实际用的是数组，但是可以把他想象成一个二叉树。并且可以通过下标来计算他们的父子关系。

image-20210624173420805

​ 计算关系：

1
2
3
leftchild = parent* 2+1
rightchild = parent* 2+2
parent = (child-1) / 2

例如：这个数组中下标为3的d,它的左孩子的下标就是3*2+1 =7, 是h，看图,确实是h。

下标为4的e,它的父结点就是(4-1)/2 = 1(舍去小数)

堆的两个特性

结构性：用数组表示的完全二叉树。

有序性：任一结点的关键字是其子树所有结点的最大值(或最小值)。

最大堆(MaxHeap)也称大顶堆(大根堆)；最大值

最小堆(MinHeap)也称小顶堆(小跟堆)；最小值

大堆要求:树中所有的父亲都大于等于孩子。

小堆要求：树中所有的父亲都小于等于孩子。

大堆：对顶数据是最大的

小堆：对顶数据是最小的

示例：下图就是一个小堆

image-20210624182711156

如何建堆

堆排序本质就是选择排序，它也可以选数。

示例：

建小堆

（大堆同理，换个符号）

image-20210624194607431

向下调整算法

前提：左右子树都是小堆。

选出左右孩子中小的那个跟父亲比较，如果比父亲小就交换，然后再接着往下进行，依次类推。调到叶子结点就终止。

动画演示

向下调整算法

最多调整高度次logN

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
void AdjustDown(int* a, int n, int root)
{
	int parent = root;
	int child = parent * 2 + 1;//默认是左孩子
	while (child <n)//别超出数组下标的范围
	{
		//选出左右孩子中大的那一个并且有两个孩子
		//如果右孩子小于左孩子
		if (child+1 < n && a[child + 1] < a[child])
		{
			//因为默认是左孩子，所以将左孩子的下标+得到右孩子的下标
			child += 1;
		}
		//如果左孩子小于等于右孩子则直接来到这里，此时child的值就是左孩子的下标

		//只有一个孩子情况直接来到这里
		//选出左右孩子小的那一个再和父对比
		//如果孩子的值小于父亲的值，就交换这两个值(在数组中)的位置
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);// 交换这两个值
			//孩子的孩子重复上述操作
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
建堆

（建大堆同理，换个符号即可。）

如果左右子树不是小堆怎么办呢？

那就不能直接使用向下调整算法，就得先把不是小堆的子树变成小堆。

倒着从最后一棵非叶子结点的子树开始调。

注意：这个数组是按照想象出来的那棵完全二叉树从上王往下一层一层的往里面存的，所以，数组的最后一个数据(下标为n-1)，就是完全二叉树最下面一层的最右边的结点，从这个结点开始从上往下寻找各自的父亲（意思就=是上面的:倒着从最后一棵非叶子结点的子树开始调。）。

建堆的时间复杂度是:O(N)

推导过程:

假设该堆为满二叉树，堆高度为h,假设每层高度hi,没层结点个数为ni,

则建堆的时间复杂度为：
image-20210628112912208

建堆的次数公式：

image-20210628113153431

利用高中所学知识，错位相减法，化简得。

t(n) = -h+2^h-1 ,（其中满二叉树的2^h-1 = N）

1
2
3
4
5
6
7
8
void HeapSort(int* a,int n)
{
	//注意这里的i是从最后一个结点开始找上面的父亲(最后一个非叶子结点)
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
}
测试
1
2
给出测试数组
    int a[] = {7,2,6,3,4,1,5,9,8};

结果

image-20210627202722050

验证

image-20210627202850375

建小堆完成。

建大堆同理，换一个比较符号即可。

堆排序为什么要建大堆？

堆排序的本质是选择排序。

如果是建小堆，最小数在数组顶部，已经被选出来了，那么在剩下的数中要建一个堆，但是剩下的数都乱了，需要重新建堆，才能选出下一个数，建堆的时间复杂度是O(N),这样建队就没有效率优势了。并且建堆选数，还不如直接遍历选数。

第一次建堆O(N)

剩下的部分选数，时间复杂度是logN

示例:

小堆

image-20210627204550544

大堆

image-20210627204951603

正确的方式——建大堆，然后交换第一个数和最后一个数，继续进行向下调整算法，第二个和导数第2个数……。

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void HeapSort(int* a,int n)
{
	//注意这里的i是从最后一个结点开始找上面的父亲(最后一个非叶子结点)
	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);//(还有n-1个数，end正好就是n-1)
		end--;
	}
}
动画图解

大约3min

打印输出结果：

image-20210628101941008

性能测试：

image-20210628115338108

交换排序

基本思想

比较值，交换顺序。

冒泡排序

前一个数比后一个数大(小)就交换位置。

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
void BubbleSort(int* a, int n)
{
	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]);
			}
		}
	}
}

或

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void BubbleSort(int* a, int n)
{
    //end控制边界
	int end = n;
	while (end > 0)
	{
		for (int j = 1; j < end; j++)
		{
			if (a[j - 1] > a[j])
			{
				Swap(&a[j - 1], &a[j]);
			}
		}
		end--;
	}
}

优化

已经有序了就不要交换了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		int exchange = 0;
		for (int j = 1; j < n - i; j++)
		{
			if (a[j - 1] > a[j])
			{
				swap(&a[j - 1], &a[j]);
				exchange = 1;
			}
        }
        if (exchange == 0)
			{
				break;
			}
		}
	}
}
对比

和直接插入排序对比谁更好呢？

直接插入排序。

image-20210701172736752

如果是有序的情况下，他们的次数都是n。

如果是接近有序，12354

冒泡排序:N-1 + N -2

直接插入排序: N

(直接插入排序对有序，接近有序，局部有序，适应性更强。)

快速排序

基本思想

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

挖坑法

选一个位置的值做关键字(key)，一般选择第一个或最后一个。

image-20210719094644325

选谁做key，谁原本的位置就是个坑(Pivot)，将key的值保存起来，然后它原来的位置就可以被覆盖了，

动画图解1

排一个数

原数组

image-20210719102402838

第一次排序完成后结构如下

image-20210719102328426

结构解释&动画图解2

image-20210719152209627

此时关键字6的位置已经被确定，它左边的数都比它小，右边的数都比它大，如果它左右两边都是有序的，那么整个数组就有序里。

那么怎么让他的左右两边都是有序的呢？

分治递归。

image-20210719154256998

每次只选一个数，这个数只要保证自己的位置确定了就行。

这个区间被缩减到只有一个值的时候，就可以认为是有序的了。

image-20210719160216275

得到结构：有序数组

image-20210719161213193

本质上和二叉树的遍历是类似的。

代码实现
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
void QuickSort(int* a, int left, int right)
{
	//什么时候不需要递归了呢？
	//当这个区间不存在，或者只有一个值，都不用排
	if (left >= right)
	{
		return;
	}

	int begin = left;
	int end = right;
	int pivot = begin;//这里选择左边第一个做坑
	int key = a[begin];


	while (begin < end)
	{
		//左边有坑在右边找小于key的放到坑里
		while (begin < end && a[end] >= key)//注意条件限制，否则会发生错位
		{
			//往前倒，拿到最早遇到的小于key的数
			end--;
		}
		//小与key的放到左边的坑中，自己原来的位置形成新的坑
		a[pivot] = a[end];
		pivot = end;
		//右边有坑在左边找大的放到坑里
		while (begin < end && a[begin] <= key)
		{
			//往后倒，拿到最早遇到的大于key的数
			begin++;
		}
		//大于key的放到右边的坑中,自己形成新的坑
		a[pivot] = a[begin];
		pivot = begin;
	}
	//最后当他们两个相遇了，这个位置就是新的坑位置
	//再将key放到里面
	pivot = begin;
	a[pivot] = key;

	//确定完一个key的位置之后，开始将他们分成两段
	//如果左子区间和右子区间有序，这个数组就有序了
	QuickSort(a, left, pivot - 1);
	QuickSort(a, pivot + 1, right);
}
特性总结

  1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序

  2. 时间复杂度:

    先看单趟排序的时间复杂度 ，O(N)

    最理想的情况就是每次选择的key都能二分 ，位置接近中间。最均匀的情况下，它能被分成一个满二叉树的形状。

    image-20210719172933068

    快速排序的时间复杂度是:N*log以2为底N的对数

    与上述排序的速度对比中我们也能看出来快速排序的快速。

    image-20210719181127087

最坏情况

  1. 快速排序什么情况下最坏?

    有序逆序，因为，这两种每次只能排好一个数，时间复杂度是O(N²)

  2. 官方对于上面这两种情况下有一种解决方法——三数区中。

因为有序的情况下中间这个数恰好是二分的，两边不选最大和最小的数。

代码如下

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
int GetMidIndex(int* a, int left, int right);

//快速排序——挖坑法
void QuickSort(int* a, int left, int right)
{
	//什么时候不需要递归了呢？
	//当这个区间不存在，或者只有一个值，都不用排
	if (left >= right)
	{
		return;
	}
	int index = GetMidIndex(a,left,right);
	Swap(&a[left], &a[index]);

	int begin = left;
	int end = right;
	int pivot = begin;//这里选择左边第一个做坑
	int key = a[begin];


	while (begin < end)
	{
		//左边有坑在右边找小于key的放到坑里
		while (begin < end && a[end] >= key)//注意条件限制，否则会发生错位
		{
			//往前倒，拿到最早遇到的小于key的数
			end--;
		}
		//小与key的放到左边的坑中，自己原来的位置形成新的坑
		a[pivot] = a[end];
		pivot = end;
		//右边有坑在左边找大的放到坑里
		while (begin < end && a[begin] <= key)
		{
			//往后倒，拿到最早遇到的大于key的数
			begin++;
		}
		//大于key的放到右边的坑中,自己形成新的坑
		a[pivot] = a[begin];
		pivot = begin;
	}
	//最后当他们两个相遇了，这个位置就是新的坑位置
	//再将key放到里面
	pivot = begin;
	a[pivot] = key;

	//确定完一个key的位置之后，开始将他们分成两段
	//如果左子区间和右子区间有序，这个数组就有序了
	QuickSort(a, left, pivot - 1);
	QuickSort(a, pivot + 1, right);
}

//三数取中
int GetMidIndex(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])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else// a[left] >a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
小区间优化

消除掉最后几层递归调用。效果很不明显。

代码如下

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
void QuickSort(int* a, int left, int right)
{
	//什么时候不需要递归了呢？
	//当这个区间不存在，或者只有一个值，都不用排
	if (left >= right)
	{
		return;
	}
	int index = GetMidIndex(a,left,right);
	Swap(&a[left], &a[index]);

	int begin = left;
	int end = right;
	int pivot = begin;//这里选择左边第一个做坑
	int key = a[begin];


	while (begin < end)
	{
		//左边有坑在右边找小于key的放到坑里
		while (begin < end && a[end] >= key)//注意条件限制，否则会发生错位
		{
			//往前倒，拿到最早遇到的小于key的数
			end--;
		}
		//小与key的放到左边的坑中，自己原来的位置形成新的坑
		a[pivot] = a[end];
		pivot = end;
		//右边有坑在左边找大的放到坑里
		while (begin < end && a[begin] <= key)
		{
			//往后倒，拿到最早遇到的大于key的数
			begin++;
		}
		//大于key的放到右边的坑中,自己形成新的坑
		a[pivot] = a[begin];
		pivot = begin;
	}
	//最后当他们两个相遇了，这个位置就是新的坑位置
	//再将key放到里面
	pivot = begin;
	a[pivot] = key;

	//确定完一个key的位置之后，开始将他们分成两段
	//如果左子区间和右子区间有序，这个数组就有序了

	//小区间优化
	if (pivot - 1 - left > 10)//数据个数
	{
		QuickSort(a, left, pivot - 1);
	}
	else
	{
		//如果剩下的数小于等于10个
		//选一个其他排序来搞定这个这个111
		InsertSort(a + left, pivot - 1 - left + 1);
	}
	if (right - 1 - pivot > 10)
	{
		QuickSort(a, pivot + 1, right);
	}
	else
	{
		InsertSort(a + pivot + 1, right - (pivot + 1) + 1);
	}
}
左右指针法

类似于挖坑法。

也是先选一个key,从左右开始向中间移动，左边比key小的，右边找比key大的，然后两个交换位置，最后重叠的位置就是key的位置。

动画图解

一次排序

代码实现
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
int PartSort2(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int index = GetMidIndex(a, left, right);
	Swap(&a[left], &a[right]);

	int begin = left;
	int end = right;
	int key = a[begin];


	while (begin < end)
	{
		//找小
		while (begin < end && a[end] >= a[key])
		{
			--end;
		}
		//找大
		while (begin < end && a[begin] <= a[key])
		{
			++begin;
		}
		Swap(&a[begin], &a[end]);
	}

	Swap(&a[key], &a[begin]);

	return key;
}
void QuickSort(int* a, int left, int right)
{
	//什么时候不需要递归了呢？
	//当这个区间不存在，或者只有一个值，都不用排
	if (left >= right)
	{
		return;
	}
	
	int keyIndex = PartSort2(a, left, right);


	//确定完一个key的位置之后，开始将他们分成两段
	//如果左子区间和右子区间有序，这个数组就有序了

	//小区间优化
	if (keyIndex - 1 - left > 10)//数据个数
	{
		QuickSort(a, left, keyIndex - 1);
	}
	else
	{
		//如果剩下的数小于等于10个
		//选一个其他排序来搞定这个这个111
		InsertSort(a + left, keyIndex - 1 - left + 1);
	}
	if (right - 1 - keyIndex > 10)
	{
		QuickSort(a, keyIndex + 1, right);
	}
	else
	{
		InsertSort(a + keyIndex + 1, right - (keyIndex + 1) + 1);
	}
}
前后指针法

cur找小，每次遇到比key小的值就停下来，++prev,交换prev和cur位置的值。

动画图解

代码实现
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
int QuickSort3(int* a, int left, int right)
{
	int index = GetMidIndex(a, left, right);
	swap(&a[left], &a[index]);
	int key = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (cur < a[key] && ++prev != cur)//自己和自己交换没有意义——&&后面的条件
		{
			Swap(&a[cur], &a[prev]);
		}
		++cur;
	}
	Swap(&a[key], &a[cur]);
	return prev;
}
//快速排序
void QuickSort(int* a, int left, int right)
	{
		//什么时候不需要递归了呢？
		//当这个区间不存在，或者只有一个值，都不用排
		if (left >= right)
		{
			return;
		}
	
		int keyIndex = PartSort3(a, left, right);


		//确定完一个key的位置之后，开始将他们分成两段
		//如果左子区间和右子区间有序，这个数组就有序了

		//小区间优化
		if (keyIndex - 1 - left > 10)//数据个数
		{
			QuickSort(a, left, keyIndex - 1);
		}
		else
		{
			//如果剩下的数小于等于10个
			//选一个其他排序来搞定这个这个111
			InsertSort(a + left, keyIndex - 1 - left + 1);
		}
		if (right - 1 - keyIndex > 10)
		{
			QuickSort(a, keyIndex + 1, right);
		}
		else
		{
			InsertSort(a + keyIndex + 1, right - (keyIndex + 1) + 1);
		}
}

这三趟排序没有本质上的区别，只是单趟排序的规则不同。

非递归法
递归的缺陷

在极端情况下会发生栈溢出。

栈帧深度太深，栈空间不够用，可能会溢出。

例如:

递归实现1+2+3+…+n

1
2
3
4
int f(int n)
{
    return n<= 1?1:f(n-1)+n;
}

递归改非递归有两种方式

1.直接改循环

2.借助数据结构的栈模拟递归过程

借助栈实现

（栈的相关文章——栈）

栈里面的区间就是需要被单趟分割排序的。

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
void QuickSortNonR(int* a, int n)
{
	//栈是后进先出的,想先出走就得先入右
	Stack st;
	StackInit(&st);
	StackPush(&st, n - 1);
	StackPush(&st, 0);
	while (!StackEmpty(&st))
	{
		int left = StackTop(&st);
		StackPop(&st);

		int right = StackTop(&st);
		StackPop(&st);

		int keyIndex = PartSort1(a, left, right);
		//left - keyIndex-1   keyIndex    keyIndex+1 - right 

		if ( keyIndex + 1 < right)
		{
			StackPush(&st, right);
			StackPush(&st, keyIndex + 1);
		}
		if (left < keyIndex - 1)//还有多个值
		{
			StackPush(&st, keyIndex -1 );
			StackPush(&st, left);
		}
	}
}

补充:

函数调用建立栈帧，栈帧中存储局部变量参数等等。

操作系统中内存的栈和堆与数据结构中的栈和堆要区分开来。

队列也可以实现。

归并排序

基本思想

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法，的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使

概念&动画图解

如果一段区间分为左右两个半区间，假设都有序，用到归并算法。

依次对比，取小的放到新的临时数组。

当其中一个区间结束了直接把另外一个区间剩下的数拷过来。

(类似于两个有序链表的归并)

那么归并之前左右子区间无序怎么办？

往下分，递归接着归并。

为了节省内存空间，分成单个归并完就拷贝回去。

归并排序有空间复杂度的消耗，因为它的核心算法需要开辟一个临时数组。它的空间复杂度是O(N),这是它跟其他算法的主要差异。

代码实现

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
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);

	//归并
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;

	int index = left;
	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++];
	}

	//拷贝回去
	for (int i = left; i <= right; i++)
	{
		a[i] = tmp[i];
	}
}
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
}

void Print(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
}

图解

思想上类似于二叉树的后序遍历。

图中指举出左侧一条路径。

拆分——归并。

image-20210724203050925

非递归实现

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
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	//每组数据个数
	int gap = 1; 
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			// [i, i+gap-1] [i+gap,i+2*gap-1]
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			// 归并过程中右半区间可能就不存在
			if (begin2 >= n)
				break;

			// 归并过程中右半区间算多了, 修正一下
			if (end2 >= n)
			{
				end2 = n - 1;
			}

			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++];
			}

			// 拷贝回去
			for (int j = i; j <= end2; ++j)
			{
				a[j] = tmp[j];
			}
		}
		gap *= 2;
	}
	free(tmp);
}

无论递归非递归归并排序的时间复杂度都是0(N*logN)。

补充

归并排序也叫做外排序。还可以对文件中的数据进行排序。

假设10的数据放到硬盘的文件中，要排序，如何排呢？
可能内存不够，假设有一个G的内存可用，10g的文件拆分成10个1G的文件，并且让10个1G的文件有序。

一次读文件，每一读1G到内存中，放到一个数组，用快速排序对其排序，再写到一个文件，再继续读下一个1G的数据。

特性总结

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

排序算法复杂度及稳定性分析

image-20210725103805011

快速排序加了三数区中基本不会出现最坏情况。

稳定性是看相同的值相对顺序是否发生变化。