探索数据结构世界之排序篇章（超级详细，你想看的都有）

-文章开头必看
1.！！！本文排序默认都是排升序
2.排序是否稳定值指指排完序之后相同数的相对位置是否改变
3.代码相关解释我都写在注释中了，方便对照着看

1.插入排序

1.1直接插入排序

• 插入排序是一种高效的简单排序算法，它的工作原理是将一个未排序的元素插入到一个已排序的列表中，并保持列表的有序性。对于已经部分有序的数组来说，插入排序是非常高效的
• 但是插入算法的时间复杂度为O(n^2)因此对于大型数组来说并不是理想的选择，但只要有部分有序，性能就会比冒泡好很多
• 类似斗地主摸牌，摸一张往前面已经排好的序列中插入

void InsertSort(int* a, int n)
{
	int end = 0;
	for (int i = 0; i < n - 1; i++)
	{
		//单趟
		//0-end是已经排好序了的
		end = i;
		int tmp = a[end + 1];//正在被插入（被排序）的值
		while (end >= 0)
		{
			//如果该数比end处的数小
			if (tmp < a[end])
			{
				//往后挪
				a[end + 1] = a[end];
			}
			//说明该数已经比end处大或者相等了
			else
			{
				break;
			}
			//每次控制完end要往前走一步
			end--;
		}
		//走到这有两种情况
		//①while循环结束了：此时tmp最小，放在第一个位置，也就是end+1
		//②else的break：此时tmp > a[end]，可以把tmp放到end后面了
		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
23
24
25
26
27
28
29
30
31

分析：

• 时间复杂度最好情况（数列已经有序）下是O(n)
  此时只是tmp位置由前往后同时仅仅只比较了一轮，因此就是O(n)
• 最坏情况（数列逆序）下O(n^2)
  此时tmp位置在不断后移的同时，每次都要前面有序的数列往后挪动，因此是O(n^2)
• 空间复杂度O(1)，没有开辟辅助空间
• 稳定性：稳定
  因此这个算法在排序的时候，tmp是找到比自身大数，使其后挪直到找到比自身小或者相等的数，然后插入到这个数的后面，因此相同的数的相对位置不会改变，也就是说这个算法是稳定的

1.2希尔排序

希尔排序称为“缩小增量排序”，是一种基于插入排序的改进算法。它的工作原理是将一个数组分为若干个子序列，每个子序列的元素都是相隔某个增量h的距离然后对每个子序列进行插入排序，将整个数组变成一个基本有序的数组。最后再对整个数组进行一次插入排序，使得整个数组完全有序。希尔排序的时间复杂度为O(n^1.3)，并且它的性能相对于直接插入排序有了很大的提升。但是希尔排序的时间复杂度会受到增量选择的影响，如何选择合适的增量是希尔排序算法的关键之一。

1.2.1单趟

	int gap = 3;//间隔三个数为一组
	int end = 0;
	for (int i = 0; i < n - gap; i += gap)//i < n - gap和a[end + gap]的范围相呼应
	{
		end = i;
		int tmp = a[end + gap];
		while (end >= 0)
		{
			if (tmp < a[end])//这里就类似插入排序
			{
				a[end + gap] = a[end];
			}
			else
			{
				break;
			}
			end = end - gap;
		}
		a[end + gap] = tmp;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1.2.2多趟基础版——排完一组再排一组

	int gap = 3;
	
	for (int j = 0; j < gap; j++)//走gap趟
	{
		for (int i = j; i < n - gap; i += gap)//内层就是单趟了
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
				}
				else
				{
					break;
				}
				end = end - gap;
			}
			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

1.2.3多趟优化版——多组并排

	int gap = 3;

	for (int i = 0; i < n - gap; i++)//只需要一层循环，走到哪组排哪组就是了。但是时间复杂度和上一种是一样的
	{
		int end = i;
		int tmp = a[end + gap];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + gap] = a[end];
			}
			else
			{
				break;
			}
			end = end - gap;
		}
		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

1.2.3完整版

void ShellSort(int* a, int n)
	int gap = n;//上面只是排完了一组，现在要逐步减小gap的值，使其能完整的排序
	
	while (gap > 1)//gap等于1之后不能再进循环了，再进循环除等之后就是0了
	{
		//gap /= 2;//性能比/3+1稍差些
		//gap /= 3;//尽量还是/2，因为如果7个数，第一次/3，gap是2，第二次就成0了
		gap = gap / 3 + 1;//这样就可以保证最后一定是1了

		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
				}
				else
				{
					break;
				}
				end = end - gap;
			}
			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

希尔排序性能分析（假设整个数组初始是逆序）

• ①刚开始gap很大的时候，如n/3，则有n/3组数据，每组数据比较3次（1+2），合计 n/3 * 3 = O(n)
  ②到中间过程时，假设gap = n/9,n/9组数据，每组9个数据，单租1+2…+9 = 36，合计36 * n/9 = O(4n)（但是在①的基础上已经调整部分顺序了，不会是完全逆序，所以实际性能会好于4n）
  ③最后，gap = 1，整个序列以及十分接近有序了，因此也是O(n)
  因此整个过程性能（比较次数）变化是先增加然后减少，成向上箭头状
• 时间复杂度最好O(n^1.3),最坏O(n²)
• 空间复杂度O(1)
• 希尔排序是不稳定的
  因为预排序的时候相同的数据可能分在不同的组中，因为其相对位置就不敢保证不变了

• 希尔排序是对直接插入排序的优化
  让较大的数据很快的跳到后面，较小的数很快跳到前面。当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。

2.选择排序

2.1直接选择排序

• 选择排序也是一种简单的排序算法，它的工作原理是每次从未排序的部分中找到最小的元素并将其放在已排序部分的末尾。这个操作会一直持续到整个数组都已被排序。选择排序对于部分有序的数组比较有效。
• 类似斗地主摸牌，牌发完之后一起整理，整理过程：先选出最小的放在最前面，然后选次小放在最小的右边，然后第三小…
• 该过程既然是在未排序的数列中遍历一遍找出最小的，那我们还可以顺便找出最大的，这样效率会更好一点

2.2.1单趟

	int mini = 0;
	int maxi = 0;

	for (int i = 1; i < n; i++)
	{
		if (a[i] > a[maxi])
		{
			a[maxi] = a[i];
		}
		if (a[i] < a[mini])
		{
			a[mini] = a[i];
		}
	}
	a[0] = a[mini];
	a[n - 1] = a[maxi];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.2.2多趟

	int begin = 0;
	int end = n - 1;

	while (begin < end)
	{
		int mini = begin;
		int maxi = begin;

		for (int i = begin + 1; i <= end; i++)
		{
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
			if (a[i] < a[mini])
			{
				mini = i;
			}
		}

		//有问题
		//有可能maxi就是在begin的位置，如果把begin交换走了，maxi的位置也会变
		//Swap(&a[begin], &a[mini]);
		//Swap(&a[end], &a[maxi]);
		
		Swap(&a[begin], &a[mini]); 
		if (maxi == begin)
		{
			//本来在begin位置的最大值换到mini位置了
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);

		++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
35
36

2.2.4完整版

void SelectSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;

	while (begin < end)
	{
		int mini = begin;
		int maxi = begin;

		for (int i = begin + 1; i <= end; i++)
		{
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
			if (a[i] < a[mini])
			{
				mini = i;
			}
		}

		//有问题
		//有可能maxi就是在begin的位置，如果把begin交换走了，maxi的位置也会变
		//Swap(&a[begin], &a[mini]);
		//Swap(&a[end], &a[maxi]);
		
		Swap(&a[begin], &a[mini]); 
		if (maxi == begin)
		{
			//本来在begin位置的最大值换到mini位置了
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);

		++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
35
36
37
38
39

-性能分析

• 时间复杂度O(n²)
  遍历未排序的部分，时间复杂度为O(n)。由于这个操作需要重复n次（对于n个元素），所以总的时间复杂度为O(n^2)
• 空间复杂度O(1)
• 不稳定
  很多人可能会以为他是个稳定，但是我举个例子你就知道了
  3 3 1 2 2 1
  先找到最小的，是位于第三位的1，因此要和第一位的3交换，此时第一位的3换到第三位之后其和第二位的三的相对位置就反了

2.2堆排序

• 堆是一种特殊的数据结构，它满足某些特定的性质。堆可以用于解决一些特定的问题，如优先级队列、求最大值和最小值等。堆排序就是利用堆的这种特性来实现的。首先构建一个最大堆或最小堆，然后将根节点与最后一个元素交换位置，这样最大的元素就放在了正确的位置:然后调整根节点以下的子树为一个最大堆或最小堆;重复这个过程直到整个数组都已被排序

2.2.1向上调整建堆

//前提是前面的数是堆
//时间复杂度：O(logN)
static AdjustUp(int* a, int child)//child指的是数组中的位置
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

void HeapSort(int* a, int n)
{
	//向上调整建堆
	//排升序建大堆
	//原因：先建大堆，选出最大的，再与末尾交换，size--，然后再来一个向下调整即可，时间复杂度为logN * N
	//
	//建小堆，选出最小的，接下来从第二个开始向上调整建堆，建堆时间复杂度就是logN * N
	//（向上调整时间复杂度logN，又因为这样做会把原有堆的规律打乱，每个数都需要重新建堆）
	//算上每次要选出最小的，总计时间复杂度就是logN * N * N

	//建堆
	for (int i = 0; i < n; i++)
	{
		AdjustUp(a, 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
17
18
19
20
21
22
23
24
25

2.2.2向下调整建堆

//前提是左右子树都是大堆/小堆
//时间复杂度：O(logN)
static AdjustDown(int* a, int n,int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		//选出左右子树中最大的
		if (child + 1 < n && a[child] < a[child + 1])
			child++;

		//比较
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

//向下调整也可以建堆
//时间复杂度O(N)
//一些前提须知：①该位置的左右子树必须是同类型的堆②一个节点既可以看作大堆也可以看作小堆
//运用递归的思想，那我们要从最后一个节点的父节点开始向下调整即可
void HeapSort2(int* a, int n)
{
	//建堆
	int fa = ((n - 1) - 1) / 2;

	while (fa >= 0)
	{
		AdjustDown(a, n, fa);
		fa--;
	}

	//排序
	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
17
18
19
20
21
22
23
24

性能分析

• 时间复杂度O(nlogN)
  每次建堆是是O(logN)，n个数就是O(nlogN)
• 空间复杂度O(1)
• 不稳定
  这个很明显的，建堆的过程能否保持相对顺序我就不说了，就单单看建完堆之后堆顶要和最后一个数交换就能看出来这相对位置肯定会被破坏

3.交换排序

3.1冒泡排序

冒泡排序是最简单的排序算法之一，它通过重复地比较相邻的两个元素，如果它们的顺序错误就交换它们，直到没有元素需要交换为止。这个过程就像泡泡逐渐向上升一样，因此得名冒泡排序。虽然它的效率不高，但是在一些简单的场景中还是有用的。主要用在教学场景中，是个很不错的入门算法

3.1.1基础版

void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n - 1; j++)
	{
		for (int i = 0; i < n - 1 - j; i++)//每趟都能把当前最大的数排到后面，因此下一趟这个数可以不参与了
		{
			if (a[i] > a[i + 1])
			{
				Swap(&a[i], &a[i + 1]);
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3.1.2优化版

void BubbleSort(int* a, int n)
{
		for (int j = 0; j < n - 1; j++)
		{
				int flat = 1;//加个flat变量用于监控整趟下来数据是不是已经处于有序的状态了。你看，此时如果flat是1，如果下面整个循环下来if语句都没进去过，说明此时数据大小关系都是前一个小于等于后一个，也就是有序的，flat也不会被改成0，后面也不用再排序了，直接break跳出就像
				for (int i = 0; i < n - 1 - j; i++)
				{
					if (a[i] > a[i + 1])
					{
						Swap(&a[i], &a[i + 1]);
						flat = 0;
					}
				}
				if (flat == 1)
					break;
		}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

性能分析

• 时间复杂度，最好情况（顺序）是O(n)，最坏情况（逆序）是O(n^2)
  空间复杂度O(1)
  稳定的

3.2快速排序

快速排序是一种高效的排序算法，采用分治策略。它的工作原理是将一个数组分成两个子数组，然后将它们分别进行排序。这个过程可以通过递归和非递归实现，最终得到一个有序的数组。

• 这里先解释一下快排为什么如果数组是有序时时间复杂度很差
  因为快排主要思想就是递归，而递归的层次和其每次递归区间的划分有关系，如果数组是有序的话，那么每次的key都是最小（逆序时为最大，同理）的，然后往下递归时，每次都只有右子树，那么整个二叉树的高度是n，而不是常见的O(logN)，导致总的时间复杂度不是O(nlogN)，而是O(n^2)

3.2.1hoare写法

快速排序的基本思想是通过一趟排序将待排序的数据分割成两部分。其中一部分的所有数据都比另一部分的所有数据要小。这个过程被称为一次划分。
具体实现步骤如下:
1.首先从序列中任意选择一个元素，把它作为枢轴。
2将小于等于枢轴的所有元素都移动到枢轴的左侧，大于枢轴的元素则移动到枢轴的
右侧。
3.以枢轴为界，划分出两个子序列，左侧子序列所有元素都小于右侧子序列。
4.枢轴元素不属于任一子序列，并且枢轴元素当前所在位置就是该元素在整个排序完成后的最终位置。
5重复上述步骤，对左右两个子序列继续进行排序，直到整个序列有序。
这就是快速排序的基本思路，它由C.A.RHoare在1962年提出，是对冒泡排序的一种改进。

//优化
//为了避免数组接近有序时性能很差
//我们在选key的时候采取三数取中的策略
//这个方法就是可以让每次找的key都相对来说是不大不小的

int GetKey(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])//mid是最大值
			return right;
		else
			return left;
	}
	else//left > mid
	{
		if (a[mid] > a[right])
			return mid;
		else if (a[right] > a[left])//mid是最小的
			return left;
		else
			return right;
	}

}
 
//写法一——hoare版本，写起来很复杂

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

	int midi = GetKey(a, left, right);
	Swap(&a[left], &a[midi]);

	int key = left;
	int LeftMove = left + 1;
	int RightMove = right;

	while (LeftMove < RightMove)
	{
		//前面这个条件就是为了避免没有满足条件的值的情况下RighrMove一直--
		while(LeftMove < RightMove && a[RightMove] >= a[key])//如果这里是>的话，在左右两边都碰到和key相等的情况下，会死循环
		{
			RightMove--;
		}
		while (LeftMove < RightMove && a[LeftMove] <= a[key])
		{
			LeftMove++;
		}
		Swap(&a[LeftMove], &a[RightMove]);
	}
	if(a[key] > a[RightMove])
		Swap(&a[key], &a[RightMove]);

//此时key已经在正确的位置了，而key的左边都是比key小的，key的右边都是比key大的，因此再递归的去排左边和右边
	QuickSort(a, left, LeftMove - 1);
	QuickSort(a, LeftMove + 1, 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

相遇位置比key小，怎么做到的？
答案：右边先走
分析：
相遇情况①
Right动Left不动，去跟L相遇
相遇位置是L位置，L和R在上一轮交换过，因此此时L位置的值还是比Key小的
相遇情况②
L动R不动，去跟R相遇
R先走，找到比key小的，停下来，这是L找大没找到一直往右走，直到遇到R，此时R位置的值也是比key小

3.2.2挖坑法

挖坑法的思路是改进于hoare的版本。首先将第一个数据存放在临时变量key中，此时第一个位置就形成一个坑位。这个写法还是有LeftMove和RightMove，干的活都是一样的，但此时他们俩谁先走都OK了，后续也和上一版一样

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

	int midi = GetKey(a, left, right);
	Swap(&a[left], &a[midi]);

	int key = a[left];
	int LeftMove = left;//这里最好不要写成left+1，因为这样在后续递归中，如果子递归只有两个数（其中一个是key）且不进循环的时候
	//在填坑过程会很麻烦，要么直接给hole复制，但是这样另外一个地方值没有改变。要么Swap，但是找不到hole地址了，也是会出错
	//写成left，后续子递归只有俩时也会正常判断，直到只有一个值，在最上头的if就return了
	int RightMove = right;
	int hole = left;

	while (LeftMove < RightMove)
	{
		while (LeftMove < RightMove && a[RightMove] >= key)
		{
			RightMove--;
		}
		a[hole] = a[RightMove];
		hole = RightMove;
		while (LeftMove < RightMove && a[LeftMove] <= key)
		{
			LeftMove++;
		}
		a[hole] = a[LeftMove];
		hole = LeftMove;
	}
	a[hole] = key;

	QuickSort(a, left, hole - 1);
	QuickSort(a, hole + 1, 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

3.2.3双指针法

本质是把一段大于key的区间往右推，同时把小的换到左边
其他的都在代码中

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

	int midi = GetKey(a, left, right);
	Swap(&a[left], &a[midi]);

	int key = left;
	//prev的情况有两种
	//在cur还没遇到比key大的值的时候，prev紧跟着cur
	//遇到之后，prev此时在比key大的这组数前面
	int prev = left;                               
	int cur = prev + 1;//cur找比key小的，找到之后，++prev，然后交换prev和cur的值
	                                                                                                                             
	while (cur <= right)
	{	//&&后面的意思是，如果prev++之后和cur在同一个位置，那就不交换
		//并且只能写在后面，prev只有在满足前面条件的情况下才需要++
		if (a[cur] < a[key] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		++cur;//不管哪种情况，cur是一直往后走的
	}

	Swap(&a[prev], &a[key]);
	
	QuickSort(a, left, prev - 1);
	QuickSort(a, right + 1, 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

3.2.4小区间优化——优化过多的递归层次

因为这个递归规程类似二叉树，然而我们知道，二叉树最下面一层约占二叉树节点数的50%，倒数第二层25%
所以这个程序75%的消耗的花在最下面两层
所以我们可以改变一下到最下面几层递归的形式
希尔不适合×（优势就是在于能让大的数快速的跳跃到后面，不适合这种小区间的）
直接插入适合√（除非小区间完全逆序，不然都只需要动几下）

int SingleSort(int* a, int left, int right)
{
	int midi = GetKey(a, left, right);
	Swap(&a[left], &a[midi]);

	int prev = left;
	int cur = prev + 1;

	int keyi = left;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}

		++cur;
	}

	Swap(&a[prev], &a[keyi]);
	return prev;
}

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

	if ((right - left + 1) > 10)//如果区间差大于10就是大区间，用递归。反之，小区间就用插入排序
	{
		int keyi = SingleSort(a, left, right);

		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
	}
	else//优化之处
	{
		InsertSort(a + left, right - left + 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

3.2.5三路划分优化——优化数组中过多的重复值带来的效率过低的问题

• 点击看题目
• 为了解决这个问题，用正常的快排只能通过部分测试用例，在测试用例是大量重复数据时会超时
• 快排再面对数组中有大量重复值时效率是很低的(O(n^2)),
• 就拿数组全是一个数来举例
  key在最左边，right找比key小的，一直会向左找到key位置，和key交换
  然后递归，此时都只有右子树了，这样后续都只有右子树，整个二叉树的高度就是n，
  因此时间复杂度就是O(n^2)

三路划分的优化就是找比key小的、相等的、大的（可以看做hoare写法和双指针的结合）

• 这个写法每次排完序之后，整个数组就会划分成三段，比key小的——等于的key的——大于key的
  然后后续再递归的时候就只递归比key小的和比key大的
• 之前的写法每次排只能确定一个数的位置，而这个写法则每次可以确定一组等于key的数的位置，效率大大提高
• 不过此时还是过不了，LeetCode太坏了，有针对性测试用例干扰，所以我们还要把三数取中给改一下

三数取中怎么改？

• 每次不取这三个数的中间值了，改为随机值（得是数组中存在的）就行

int GetKey2(int* a, int left, int right)
{
	//int mid = (left + right) / 2;//这样写还是要被LeetCode针对
	int mid = left + (rand() % (right - left));//这样产生的mid就是数组随机位置的值了

	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
			return mid;
		else if (a[left] < a[right])//mid是最大值
			return right;
		else
			return left;
	}
	else//left > mid
	{
		if (a[mid] > a[right])
			return mid;
		else if (a[right] > a[left])//mid是最小的
			return left;
		else
			return right;
	}
}

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

	int midi = GetKey2(a, left, right);
	Swap(&a[left], &a[midi]);

	int key = a[left];//key值要保存一下，后续该位置的值就会被修改
	int cur = left + 1;
	int LeftMove = left;
	int RightMove = right;

	while (cur <= RightMove)
	{
		if (a[cur] < key)
		{
			Swap(&a[cur], &a[LeftMove]);
			cur++;
			LeftMove++;
		}
		else if (a[cur] == key)
		{
			cur++;
		}
		else//a[cur] > key
		{
			Swap(&a[cur], &a[RightMove]);
			RightMove--;
			//这里cur的位置不用动，因为你不知道交换前RightMove的值是否大于key，需要再下一次再进行比较
		}
	}

	//二路递归 left-LeftMove-1  RightMove-right+1
	QuickSort(a, left, LeftMove-1);
	QuickSort(a, RightMove+1, 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

这里其实用别的排序就可以过，选快排只是为了介绍一下三路划分

3.2.6非递归写法

• 快速排序的非递归写法主要利用栈来手动模拟递归调用
• 首先，从数组中选择一个数作为标准数。然后，将所有比标准数小的数放在它的左边，所有比标准数大的数放在它的右边。这样，标准数就被放在它应该在的位置上，不需要再移动。
  接下来，对标准数左右两边的数字重复上述操作
• 具体步骤包括:
  1.选择数组的最后一个元素作为标准数。
  2.使用栈存储待处理的子数组的起始和结束索引。
  3.当栈非空时，取出栈顶的起始和结束索引，执行快速排序的划分操作。
  4.将划分后得到的子数组的起始和结束索引
  压入栈中。
• 这种方法避免了递归调用的开销，提高了效率，并且不会有递归深度过大导致的栈溢出风险(因为动态栈是开辟在堆上的，堆的内存比栈多很多很多)

void QuickSort_NonR(int* a, int begin, int end)
{
	ST st;
	STInit(&st);

	STPush(&st, end);
	STPush(&st, begin);

	while (!STEmpty(&st))
	{
		int left = STTop(&st);
		STPop(&st);
		int right = STTop(&st);
		STPop(&st);

		int key = SingleSort(a, left, right);

		if (key + 1 < right)
		{
			STPush(&st, right);
			STPush(&st, key + 1);
		}
		if (left < key - 1)
		{
			STPush(&st, key - 1);
			STPush(&st, left);
		}
	}

	STDestroy(&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
27
28
29
30
31

性能分析

• 正常随机数据下，性能都是较好的
  性能最好的时候：每次的key都是中间值，然后n个数，二路递归（参与递归的个数会减少），高度是logn，因此是O(logN)
  性能最差的时候（有序和接近有序的时候）：n个数，每次key都是最小值或者最大值，因此高度是n，个数最开始是n，然后n-1，n-2，因此是O(N^2)
• 空间复杂度,这也依赖数组初始的顺序，和时间复杂度一样,最好是O(logN)，最差时是O(N)
  不稳定的

4 .归并排序

4 .1归并排序

归并排序的主要思路是利用分治策略进行排序
具体地说，它有三个主要的步骤:
1.分解 :首先，将待排序的数列分成两个大致相等的子序列。这个过程会一直递归，直到每个子序列只包含一个元素。
2.解决:然后，对每个子序列执行归并排序。这一步也是递归的，直到子序列可以被看作是已经排序好的。
3合并: 最后，将两个已经排序好的子序列合并成一个排序好的序列
在实际操作中，可以采用迭代法来实现归并排序。这包括申请足够大的空间来存储合并后的序列，设定两个指针分别指向两个已排序序列的起始位置，然后比较两个指针所指向的元素，选择较小的元素放入到合并空间，并移动指针到下一位置。这个过程会一直重复，直到某一指针到达序列尾。

4.1递归写法

void Merger(int* a, int* tmp, int begin, int end)
{
	//递归————————————
	if (end <= begin)
		return;

	int mid = (end + begin) / 2;

	//类似二叉树的后序
	Merger(a, tmp, begin, mid);
	Merger(a, tmp, mid + 1, end);

	//归并————————————
	int index = begin;

	int begin1 = begin;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = end;

	//归并——找小
	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++];

	//将tmp拷贝回a数组
	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}

void MergerSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}

	Merger(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
41
42
43
44
45
46
47
48
49
50
51

4.2非递归写法

用不了栈或队列
为什么快排可以，因为快排是先序，而归并是后序！
先序的话区间入栈之后-排完-出栈，但是归并是走到底才开始排
可能会说，走到底再排也可以先把区间入进去呀？
不可以，因为后续的区间是根据前面区间排完结果而来的
那非递归的思路要来自斐波那契数列的非递归了。就是把递归倒过来走，我们递归是把大化小，那非递归就从小开始排，然后不断扩大区间

void Merger_NonR(int* a, int n)
{
	//创建临时数组
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}

	//11归——22归——44归
	for (int gap = 1; gap < n; gap *= 2)
	{
		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 index = i;

			//数组个数不是2次幂，避免越界的修正1
			//只有end1，begin2，end2会发生越界，begin1不会，因为begin1=i，i n时，end1 >= n。都是不用归并了，因此break的情况//也就是归并的第二组不存在
			//为什么不用归并了，因为在前面的小区间归并的时候已经是有序的了
			if (begin2 >= n)
			{
				break;
			}
			if (end2 >= n)
			{
				end2 = n - 1;//修正end2的下标，让最后一组在合理范围内归并
				//这里为什么还要归并
				//因为end2越界，而前面没越界的时候，前面一组和这一组的顺序还没排好啊，虽然数量不对等，但还要排序啊
			}

			//归并——找小
			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++];

			//将tmp拷贝回a数组
			//修正2
			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));//i在这一次拷贝的过程中不变啊！begin1会变
		}
	}
	
	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
54
55
56
57
58
59

性能分析

• 递归情况下时间复杂度O(nlogN)
• 空间复杂度O(N)，需要开辟同等大小的数组用作归并
• 稳定

5.非比较排序

5.1计数排序

• 计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用
• 计数排序的主要思路是利用一个额外的数组C，其中第i个元素表示待排序数组A中值等于的元素的个数。核心步骤在于将输入的数据值转换为键存储在额外开辟的数组空间中。
  具体实现逻辑如下:
  1首先，找出待排序的数组中最大和最小的元素。
  2.然后，根据找到的最大和最小值确定计数数组C的长度，一般等于待排序数组的最大值与最小值的差加上1。
  3.接下来，扫描一遍原始数组，以当前值作为下标，将该下标的计数器增1。这就完成了分配的步骤。
  4.最后，再次扫描计数器数组，按顺序把值收集起来，形成排序后的数组。总的来说，计数排序是一种线性时间复
• 计数排序在数据范围集中且数据类型为整数时，效率很高，但是适用范围及场景有限

void CountSort(int* a, int n)
{
	int i = 0;
	//统计数组区间
	int min = a[0];
	int max = a[0];
	for (i = 0; i < n; i++)//n是总个数
	{
		if (a[i] < min)
			min = a[i];
		if (a[i] > max)
			max = a[i];
	}
	//计数
	int range = max - min + 1;//range是值的范围差,需要开这么多个位置
	int* count = (int*)calloc(range , sizeof(int));
	for (i = 0; i < n; i++)
		count[a[i] - min]++;
	//排序
	for (int j = 0; j < n; j++)
	{
		for (i = 0; i < range; i++)
		{
			while (count[i]--)
				a[j++] = 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

性能分析
时间复杂度O(MAX(n + range)),依赖与n和range的量级了
空间O(range)
它就不讨论稳定性了
一般稳定性用于讨论能排结构体类似数据的算法中，因为稳定性的意义在于它保证了排序结果的正确性。如果一个排序算法是稳定的，这意味着在排序过程中，具有相同关键字的记录的相对次序会保持不变。例如，在一个包含多个相同关键字的记录序列中，如果某个记录在另一个记录之前，那么在排序后的序列中，这个记录仍将在另一个记录之前。
如果排序的内容仅仅是一个复杂对象的某一个数字属性，那么稳定性将毫无意义。但在某些情况下，比如需要根据多个属性进行排序时，稳定性就显得尤为重要。此外，如果排序前和排序后相同关键字的相对位置发生了变化，可能会导致排序结果的错误，从而影响到后续的处理和分析。

6.所有排序代码合集

Sort.h

#pragma once

#include
#include
#include

//一律写升序
//
//目前性能排序
// 快排 > 堆排序 ≈ 希尔排序 > 归并 >> 直接插入 > 冒泡 > 直接选择
//

void PrintArr(int* a, int n);

//插入排序————————————————————————————————————————

//直接插入排序
//性能分析
//最差是O(n^2)
//但只要有部分有序，性能就会比冒泡好很多
void InsertSort(int* a, int n);//斗地主摸牌，摸一张往前面已经排好的序列中插入

//希尔排序（基于插入排序）
//希尔排序性能分析（假设整个数组初始是逆序）
//①刚开始gap很大的时候，如n/3，则有n/3组数据，每组数据比较3次（1+2），合计 n/3 * 3 = O(n)
//②到中间过程时，假设gap = n/9,n/9组数据，每组9个数据，单租1+2...+9 = 36，合计36 * n/9 = O(4n)（但是在①的基础上已经调整部分顺序了，不会是完全逆序，所以实际性能会好于4n）
//③最后，gap = 1，整个序列以及十分接近有序了，因此也是O(n)
//因此整个过程性能（比较次数）变化是先增加然后减少，成向上箭头状
//
void ShellSort(int* a, int n);

//插入排序————————————————————————————————————————
//交换排序————————————————————————————————————————

//冒泡排序
//性能分析
//O(n)~O(n^2)
void BubbleSort(int* a, int n);//优化版：设置一个检测变量，如果在一趟中，并未发生交换，则改变此变量，意味着此序列已经是有序的，可以不用继续后面的趟数了

//快排
//性能分析
//正常随机数据下，性能都是较好的
//性能最好的时候：每次的key都是中间值，然后n个数，二路递归（参与递归的个数会减少），高度是logn，因此是logN
//性能最差的时候（有序和接近有序的时候）：n个数，每次key都是最小值或者最大值，因此高度是n，个数最开始是n，然后n-1，n-2，因此是O(N^2)
void QuickSort(int* a, int n);

//交换排序————————————————————————————————————————
//选择排序————————————————————————————————————————

//堆排序
void HeapSort(int* a, int n);

//直接选择排序
void SelectSort(int* a, int n);//斗地主摸牌，牌发完之后一起整理，整理过程：先选出最小的放在最前面，然后选次小放在最小的右边，然后第三小，，，
							   //优化版：在一趟遍历的过程中，一次性选出最小的和最大的

//选择排序————————————————————————————————————————
//归并排序

//空间复杂度O(n)
//时间复杂度O(n*logN)
void MergerSort(int* a, int n);

//非选择排序
//计数排序——哈希的思想
void CountSort(int* a, int 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
59
60
61
62
63
64
65
66
67

Sort.c

#define _CRT_SECURE_NO_WARNINGS 1

#define _CRT_SECURE_NO_WARNINGS 1

#include"Sort.h"
#include"Stack.h"

static void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

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

//时间复杂度 最坏(逆序)O(n^2) 最好(顺序)O(n)
//空间复杂度 O(1)

//升序
void InsertSort(int* a, int n)
{
	int end = 0;
	for (int i = 0; i < n - 1; i++)
	{
		//单趟
		//0-end是已经排好序了的
		end = i;
		int tmp = a[end + 1];//正在被插入（被排序）的值
		while (end >= 0)
		{
			//如果该数比end处的数小
			if (tmp < a[end])
			{
				//往后挪
				a[end + 1] = a[end];
			}
			//说明该数已经比end处大或者相等了
			else
			{
				break;
			}
			//每次控制完end要往前走一步
			end--;
		}
		//走到这有两种情况
		//①while循环结束了：此时tmp最小，放在第一个位置，也就是end+1
		//②else的break：此时tmp > a[end]，可以把tmp放到end后面了
		a[end + 1] = tmp;
	}
}

void ShellSort(int* a, int n)
{
	//单趟
	
	//int gap = 3;//间隔三个数为一组
	//int end = 0;
	//for (int i = 0; i < n - gap; i += gap)//i < n - gap和a[end + gap]的范围相呼应
	//{
	//	end = i;
	//	int tmp = a[end + gap];
	//	while (end >= 0)
	//	{
	//		if (tmp < a[end])//这里就类似插入排序
	//		{
	//			a[end + gap] = a[end];
	//		}
	//		else
	//		{
	//			break;
	//		}
	//		end = end - gap;
	//	}
	//	a[end + gap] = tmp;
	//}

	//多趟（写法1——先排一组再排另外一组）

	//int gap = 3;
	//
	//for (int j = 0; j < gap; j++)//走gap趟
	//{
	//	for (int i = j; i < n - gap; i += gap)//内层就是单趟了
	//	{
	//		int end = i;
	//		int tmp = a[end + gap];
	//		while (end >= 0)
	//		{
	//			if (tmp < a[end])
	//			{
	//				a[end + gap] = a[end];
	//			}
	//			else
	//			{
	//				break;
	//			}
	//			end = end - gap;
	//		}
	//		a[end + gap] = tmp;
	//	}
	//}

	//多趟（写法二——多组并排）

	//int gap = 3;

	//for (int i = 0; i < n - gap; i++)//只需要一层循环，走到哪组排哪组就是了。但是时间复杂度和上一种是一样的
	//{
	//	int end = i;
	//	int tmp = a[end + gap];
	//	while (end >= 0)
	//	{
	//		if (tmp < a[end])
	//		{
	//			a[end + gap] = a[end];
	//		}
	//		else
	//		{
	//			break;
	//		}
	//		end = end - gap;
	//	}
	//	a[end + gap] = tmp;
	//}

	//完整

	int gap = n;//上面只是排完了一组，现在要逐步减小gap的值，使其能完整的排序
	
	while (gap > 1)//gap等于1之后不能再进循环了，再进循环除等之后就是0了
	{
		//gap /= 2;//性能比/3+1稍差些
		//gap /= 3;//尽量还是/2，因为如果7个数，第一次/3，gap是2，第二次就成0了
		gap = gap / 3 + 1;//这样就可以保证最后一定是1了

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

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

	//优化版

	for (int j = 0; j < n - 1; j++)
	{
		int flat = 1;
		for (int i = 0; i < n - 1 - j; i++)
		{
			if (a[i] > a[i + 1])
			{
				Swap(&a[i], &a[i + 1]);
				flat = 0;
			}
		}
		if (flat == 1)
			break;
	}
}



//前提是前面的数是堆
//时间复杂度：O(logN)
static AdjustUp(int* a, int child)//child指的是数组中的位置
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

//前提是左右子树都是大堆/小堆
//时间复杂度：O(logN)
static AdjustDown(int* a, int n,int parent)
{
	int child = parent * 2 + 1;//从最后一个非叶子结点开始向下调整
	while (child < n)
	{
		//选出左右子树中最大的
		if (child + 1 < n && a[child] < a[child + 1])
			child++;

		//比较
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}

//最大的问题：前提是有一个堆的数据结构存在
//空间复杂度（因为排序额外消耗了一段空间）：O(n)
//void HeapSort(int* a, int n)
//{
//	HP hp;
//	HeapInit(&hp);
//	for (int i = 0; i < n; i++)
//	{
//		HeapPush(&hp, a[i]);
//	}
//
//	int i = 0;
//	while (!HeapEmpty(&hp))
//	{
//		//printf("%d ", HeapTop(&hp));
//		a[i++] = HeapTop(&hp);
//		HeapPop(&hp);
//	}
//	HeapDestroy(&hp);
//}

//优化后：直接在数组的基础上建堆
//升序/时间复杂度 nlog(n)
void HeapSort(int* a, int n)
{
	//向上调整建堆
	//排升序建大堆
	//原因：先建大堆，选出最大的，再与末尾交换，size--，然后再来一个向下调整即可，时间复杂度为logN * N
	//建小堆，选出最小的，接下来从第二个开始向上调整建堆，建堆时间复杂度就是logN * N
	//（向上调整时间复杂度logN，又因为这样做会把原有堆的规律打乱，每个数都需要重新建堆）
	//算上每次要选出最小的，总计时间复杂度就是logN * N * N

	//建堆
	for (int i = 0; i < n; i++)
	{
		AdjustUp(a, i);
	}

	//排序
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

//向下调整也可以建堆
//时间复杂度O(N)
//一些前提须知：①该位置的左右子树必须是同类型的堆②一个节点既可以看作大堆也可以看作小堆
//运用递归的思想，那我们要从最后一个节点的父节点开始向下调整即可
void HeapSort2(int* a, int n)
{
	//建堆
	int fa = ((n - 1) - 1) / 2;

	while (fa >= 0)
	{
		AdjustDown(a, n, fa);
		fa--;
	}

	//排序
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}


//时间复杂度O(n^2)
//第一趟n,第二趟n-2，n-4，，，

void SelectSort(int* a, int n)
{
	//单趟

	//int mini = 0;
	//int maxi = 0;

	//for (int i = 1; i < n; i++)
	//{
	//	if (a[i] > a[maxi])
	//	{
	//		a[maxi] = a[i];
	//	}
	//	if (a[i] < a[mini])
	//	{
	//		a[mini] = a[i];
	//	}
	//}
	//a[0] = a[mini];
	//a[n - 1] = a[maxi];

	//多趟——写法一

	//for (int j = 0; j < (n+1) / 2; j++)//这里为什么是<(n+1)/2，拿俩数试试就知道，目的是只能走左右两边的数
	//{
	//	int mini = j;
	//	int maxi = j;

	//	for (int i = j + 1; i < n - j; i++)
	//	{
	//		if (a[i] > a[maxi])
	//		{
	//			maxi = i;
	//		}
	//		if (a[i] < a[mini])
	//		{
	//			mini = i;
	//		}
	//	}
	//	//有问题
	//	//有可能maxi就是在begin的位置，如果把begin交换走了，maxi的位置也会变
	//	Swap(&a[j], &a[mini]);
	//	Swap(&a[n - 1 - j], &a[maxi]);
	//}

	//多趟——写法二

	int begin = 0;
	int end = n - 1;

	while (begin < end)
	{
		int mini = begin;
		int maxi = begin;

		for (int i = begin + 1; i <= end; i++)
		{
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
			if (a[i] < a[mini])
			{
				mini = i;
			}
		}

		//有问题
		//有可能maxi就是在begin的位置，如果把begin交换走了，maxi的位置也会变
		//Swap(&a[begin], &a[mini]);
		//Swap(&a[end], &a[maxi]);
		
		Swap(&a[begin], &a[mini]); 
		if (maxi == begin)
		{
			//本来在begin位置的最大值换到mini位置了
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);

		++begin;
		--end;
	}
}


//快速排序

//相遇位置比key小，怎么做到的？
//答案：右边先走
//分析：
//相遇情况①
//Right动Left不动，去跟L相遇
//相遇位置是L位置，L和R在上一轮交换过，因此此时L位置的值还是比Key小的
//相遇情况②
//L动R不动，去跟R相遇
//R先走，找到比key小的，停下来，这是L找大没找到一直往右走，直到遇到R，此时R位置的值也是比key小


//优化
//为了避免数组接近有序时性能很差
//我们在选key的时候采取三数取中的策略

int GetKey(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])//mid是最大值
			return right;
		else
			return left;
	}
	else//left > mid
	{
		if (a[mid] > a[right])
			return mid;
		else if (a[right] > a[left])//mid是最小的
			return left;
		else
			return right;
	}

}
 
//写法一——hoare版本，写起来很复杂

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

	int midi = GetKey(a, left, right);
	Swap(&a[left], &a[midi]);

	int key = left;
	int LeftMove = left + 1;
	int RightMove = right;

	while (LeftMove < RightMove)
	{
		//前面这个条件就是为了避免没有满足条件的值的情况下RighrMove一直--
		while(LeftMove < RightMove && a[RightMove] >= a[key])//如果这里是>的话，在左右两边都碰到和key相等的情况下，会死循环
		{
			RightMove--;
		}
		while (LeftMove < RightMove && a[LeftMove] <= a[key])
		{
			LeftMove++;
		}
		Swap(&a[LeftMove], &a[RightMove]);
	}
	if(a[key] > a[RightMove])
		Swap(&a[key], &a[RightMove]);

	QuickSort(a, left, LeftMove - 1);
	QuickSort(a, LeftMove + 1, right);
}


//写法二——挖坑法

//自己写的错误写法，存在bug
//void QuickSort(int* a, int left, int right)
//{
//	if (left >= right)
//		return;
//
//	int midi = GetKey(a, left, right);
//	Swap(&a[left], &a[midi]);
//
//	int key = left;
//	int LeftMove = left + 1;
//	int RightMove = right;
//	int* tmp = &a[key];//把key处的值放到tmp中，形成临时变量
//	int hole = key;
//
//	while (LeftMove < RightMove)
//	{
//		while (LeftMove < RightMove && a[RightMove] >= *tmp)
//		{
//			RightMove--;
//		}
//		if (LeftMove < RightMove)
//		{
//			a[hole] = a[RightMove];
//			hole = RightMove;
//		}
//		while (LeftMove < RightMove && a[LeftMove] <= *tmp)
//		{
//			LeftMove++;
//		}
//		if (LeftMove < RightMove)
//		{
//			a[hole] = a[LeftMove];
//			hole = LeftMove;
//		}
//	}
//
//	if (key < RightMove && *tmp > a[RightMove])
//		Swap(&a[RightMove], tmp);
//	//if (key > LeftMove && a[key] < a[LeftMove])
//	//	Swap(&a[key], &a[LeftMove]);
//
//	QuickSort(a, left, hole - 1);
//	QuickSort(a, hole + 1, right);
//}

//void QuickSort(int* a, int left, int right)
//{
//	if (left >= right)
//		return;
//
//	int midi = GetKey(a, left, right);
//	Swap(&a[left], &a[midi]);
//
//	int key = a[left];
//	int LeftMove = left;//这里最好不要写成left+1，因为这样在后续递归中，如果子递归只有两个数（其中一个是key）且不进循环的时候
//	//在填坑过程会很麻烦，要么直接给hole复制，但是这样另外一个地方值没有改变。要么Swap，但是找不到hole地址了，也是会出错
//	//写成left，后续子递归只有俩时也会正常判断，直到只有一个值，在最上头的if就return了
//	int RightMove = right;
//	int hole = left;
//
//	while (LeftMove < RightMove)
//	{
//		while (LeftMove < RightMove && a[RightMove] >= key)
//		{
//			RightMove--;
//		}
//		a[hole] = a[RightMove];
//		hole = RightMove;
//		while (LeftMove < RightMove && a[LeftMove] <= key)
//		{
//			LeftMove++;
//		}
//		a[hole] = a[LeftMove];
//		hole = LeftMove;
//	}
//	a[hole] = key;
//
//	QuickSort(a, left, hole - 1);
//	QuickSort(a, hole + 1, right);
//}


//写法三——双指针
//本质是把一段大于key的区间往右推，同时把小的换到左边

//void QuickSort(int* a, int left, int right)
//{
//	if (left >= right)
//		return;
//
//	int midi = GetKey(a, left, right);
//	Swap(&a[left], &a[midi]);
//
//	int key = left;
//	//prev的情况有两种
//	//在cur还没遇到比key大的值的时候，prev紧跟着cur
//	//遇到之后，prev此时在比key大的这组数前面
//	int prev = left;                               
//	int cur = prev + 1;//cur找比key小的，找到之后，++prev，然后交换prev和cur的值
//	                                                                                                                             
//	while (cur <= right)
//	{	//&&后面的意思是，如果prev++之后和cur在同一个位置，那就不交换
//		//并且只能写在后面，prev只有在满足前面条件的情况下才需要++
//		if (a[cur] < a[key] && ++prev != cur)
//		{
//			Swap(&a[prev], &a[cur]);
//		}
//		++cur;//不管哪种情况，cur是一直往后走的
//	}
//
//	Swap(&a[prev], &a[key]);
//	
//	QuickSort(a, left, prev - 1);
//	QuickSort(a, right + 1, right);
//}       

//优化
//因为这个递归规程类似二叉树，然而我们知道，二叉树最下面一层约占二叉树节点数的50%，倒数第二层25%
//所以这个程序75%的消耗的花在最下面两层
//所以我们可以改变一下到最下面几层递归的形式
//希尔不适合（优势就是在于能让大的数快速的跳跃到后面，不适合这种小区间的）
//直接插入适合（除非小区间完全逆序，不然都只需要动几下）
//

int SingleSort(int* a, int left, int right)
{
	int midi = GetKey(a, left, right);
	Swap(&a[left], &a[midi]);

	int prev = left;
	int cur = prev + 1;

	int keyi = left;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}

		++cur;
	}

	Swap(&a[prev], &a[keyi]);
	return prev;
}
//
//void QuickSort(int* a, int left, int right)
//{
//	if (left >= right)
//		return;
//
//	if ((right - left + 1) > 10)
//	{
//		int keyi = SingleSort(a, left, right);
//
//		QuickSort(a, left, keyi - 1);
//		QuickSort(a, keyi + 1, right);
//	}
//	else//优化之处
//	{
//		InsertSort(a + left, right - left + 1);
//	}
//}


//写法四——非递归
//借助栈来实现，其实递归的写法本质也是栈结构，只是我们利用非递归的栈是动态栈，存放在堆中，更合理（堆2G+，栈2M）
//
void QuickSort_NonR(int* a, int begin, int end)
{
	ST st;
	STInit(&st);

	STPush(&st, end);
	STPush(&st, begin);

	while (!STEmpty(&st))
	{
		int left = STTop(&st);
		STPop(&st);
		int right = STTop(&st);
		STPop(&st);

		int key = SingleSort(a, left, right);

		if (key + 1 < right)
		{
			STPush(&st, right);
			STPush(&st, key + 1);
		}
		if (left < key - 1)
		{
			STPush(&st, key - 1);
			STPush(&st, left);
		}
	}

	STDestroy(&st);
}


//归并排序——递归写法
//时间复杂度O(nlogN)
//空间O(N)
//
void Merger(int* a, int* tmp, int begin, int end)
{
	//递归————————————
	if (end <= begin)
		return;

	int mid = (end + begin) / 2;

	Merger(a, tmp, begin, mid);
	Merger(a, tmp, mid + 1, end);

	//归并————————————
	int index = begin;

	int begin1 = begin;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = end;

	//归并——找小
	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++];

	//将tmp拷贝回a数组
	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}

void MergerSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}

	Merger(a, tmp, 0, n - 1);

	free(tmp);
}

//归并排序——非递归写法
//用不了栈或队列
//为什么快排可以，因为快排是先序，而归并是后序！
//先序的话区间入栈之后-排完-出栈，但是归并是走到底才开始排
//可能会说，走到底再排也可以先把区间入进去呀？
//不可以，因为后续的区间是根据前面区间排完结果而来的
//那非递归的思路要来自斐波那契数列的非递归了。就是把递归倒过来走，我们递归是把大化小，那非递归就从小开始排，然后不断扩大区间

void Merger_NonR(int* a, int n)
{
	//创建临时数组
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}

	//11归——22归——44归
	for (int gap = 1; gap < n; gap *= 2)
	{
		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 index = i;

			//数组个数不是2次幂，避免越界的修正1
			//只有end1，begin2，end2会发生越界，begin1不会，因为begin1=i，i n时，end1 >= n。都是不用归并了，因此break的情况//也就是归并的第二组不存在
			//为什么不用归并了，因为在前面的小区间归并的时候已经是有序的了
			if (begin2 >= n)
			{
				break;
			}
			if (end2 >= n)
			{
				end2 = n - 1;//修正end2的下标，让最后一组在合理范围内归并
				//这里为什么还要归并
				//因为end2越界，而前面没越界的时候，前面一组和这一组的顺序还没排好啊，虽然数量不对等，但还要排序啊
			}

			//归并——找小
			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++];

			//将tmp拷贝回a数组
			//修正2
			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));//i在这一次拷贝的过程中不变啊！begin1会变
		}
	}
	
	free(tmp);
}


//时间复杂度O(n + range)
//空间O(range)
//适合紧凑的数列
//只适合整数
void CountSort(int* a, int n)
{
	int i = 0;
	//统计数组区间
	int min = a[0];
	int max = a[0];
	for (i = 0; i < n; i++)//n是总个数
	{
		if (a[i] < min)
			min = a[i];
		if (a[i] > max)
			max = a[i];
	}
	//计数
	int range = max - min + 1;//range是值的范围差,需要开这么多个位置
	int* count = (int*)calloc(range , sizeof(int));
	for (i = 0; i < n; i++)
		count[a[i] - min]++;
	//排序
	for (int j = 0; j < n; j++)
	{
		for (i = 0; i < range; i++)
		{
			while (count[i]--)
				a[j++] = 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
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842

test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"Sort.h"
#include"Stack.h"

int main()
{
	//	int a[] = {0 ,100,3,4,2,1,7,88,8,5,6,9,10 };
	int a[] = { 4,2,1,7,8,3,5,6 ,9};
	int size = sizeof(a) / sizeof(a[0]);

	//InsertSort(a, size);
	//PrintArr(a, size);

	//ShellSort(a, size);
	//PrintArr(a, size);

	//BubbleSort(a, size);
	//PrintArr(a, size);

	HeapSort(a, size);
	PrintArr(a, size);	
	
	//SelectSort(a, size);
	//PrintArr(a, size);

	//QuickSort_NonR(a, 0,size-1);
	//PrintArr(a, size);

	//MergerSort(a,size);
	//PrintArr(a, size);

	//Merger_NonR(a, size);
	//PrintArr(a, size);

	//CountSort(a, size);
	//PrintArr(a, size);

	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
35
36
37
38
39
40

Stack.h

#pragma once


#include
#include
#include
#include

typedef int STDataType;

typedef struct Stack
{
	STDataType* data;
	int top;
	int capacity;
}ST;

void STInit(ST* ps);
void STDestroy(ST* ps);

void STPush(ST* ps, STDataType x);
void STPop(ST* ps);

STDataType STTop(ST* ps);

int STSize(ST* ps);
bool STEmpty(ST* ps);
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

Stack.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"Stack.h"

void STInit(ST* ps)
{
	assert(ps);

	ps->data = NULL;
	ps->top = -1;
	ps->capacity = 0;
}

void STDestroy(ST* ps)
{
	assert(ps);

	free(ps->data);
	ps->data = NULL;
	ps->top = -1;
	ps->capacity = 0;
}

void STPush(ST* ps, STDataType x)
{
	assert(ps);

	//CheckCapacity
	if (ps->capacity == ps->top + 1)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->data, sizeof(STDataType) * newcapacity);
		if (NULL == tmp)
		{
			perror("realloc failed");
			exit(-1);
		}

		ps->data = tmp;
		ps->capacity = newcapacity;
	}
	ps->top++;
	ps->data[ps->top] = x;
}

void STPop(ST* ps)
{
	assert(ps);
	assert(ps->top >= 0);

	ps->top--;
}

STDataType STTop(ST* ps)
{
	assert(ps);

	return ps->data[ps->top];
}

int STSize(ST* ps)
{
	assert(ps);

	return( ps->top + 1);
}

bool STEmpty(ST* ps)
{
	assert(ps);

	return ps->top == -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
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