【数据结构】经典八大排序（Plus版）

每一个不曾起舞的日子，都是对生命的辜负。

注：此文章均以升序讲解

排序分类 🚀

1. 插入排序🚀

1.1 基本思想🚀

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

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

1.2 直接插入排序:🚀

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。

代码：

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

1.3 插入排序特性🚀

1. 元素集合越接近有序，直接插入排序算法的时间效率越高（在已排好序的情况下其时间复杂度为O(N).
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1),它是一种稳定的排序算法
4. 稳定性：稳定

那么所谓的稳定性是什么呢？我想在以链表的排序进行解释，这样好说明。在排序之前，或许会有重复的元素，他们的值相同，但是节点的地址不同，并且一前一后，当排序时，难免会将两个具有相同值的节点的前后顺序颠倒，因为这样对于排序来说值相同前后是无关紧要的，但是他们的节点是不同的，节点与节点的区别在于地址不同，因此，出现了这种情况就代表了排序中的不稳定，相反，这两个节点排序之后的前后顺序相同也就代表着排序是稳定的。

2. 希尔排序（缩小增量排序）🚀

2.1 基本思想🚀

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数gap，把待排序文件中所有记录分成gap个组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后，取重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

先以一次排序进行演示，按照9 1 2 5 7 4 8 6 3 5

为初始数据的话，假设gap = 3，分成的就是这样几组：

1. 9 5 8 5
2. 1 7 6
3. 2 4 3

通过将其分别排序可以变成这样：

1. 5 5 8 9
2. 1 6 7
3. 2 3 4

最后的数据就是这样：

5 1 2 5 6 3 8 7 4 9

先来看看粗略理解的希尔排序

//初始的顺序：9   1   2   5   7   4   8   6   3   5
//预排序
int gap = 3;
for (int j = 0; j < gap; ++j)//将gap组依次分别进行排序
{
    // [0, end]插入 end+gap  [0, end+gap]有序  --间隔为gap的数据
    for (int i = j; i < n - gap; i += gap)
    {
        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;
    }
}
//此时数组得数据顺序变成：`5   1   2   5   6   3   8   7   4   9`
//再插入排序
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  5  6  7  8  9
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

这样的预排序可以看出是在直接插入排序的基础上进行改变，里面的两层循环就是将直接插入排序中的1变成gap，得到的这个数据我们称其为预排序，通过这样的排序之后再进行插入排序时将会大幅度的缩短时间（尤其是初始数据为逆序，将其排成升序），这就是希尔排序的思想。上面举的例子为gap=3,那么gap的标准应该如何进行选择呢？这个问题在总结特性的时候会说到，并且后续标准希尔排序代码也会用到。

然而这样的排序似乎有很多疏漏，gap的值应该随着数据量的变化而发生改变，而不是定死的赋予其值的大小，因为我们在插入排序基础上加上预排序变成希尔排序的目的就是让其效率变高，而效率变高本身就是对极其庞大的数来说的，因此，为了使效率变高，我们每次应使gap为不同的值一直进行预排序（上面的只赋值给gap一次，即只进行了一趟排序，就是gap = 3），而我们也发现，gap=1的时候就是直接插入排序，那我们就可以每次这样处理：gap = gap / 3 + 1 ,因为gap不能为0，因此，需要+1，于是外面就可以再来一层循环，while（gap>1）然后gap = gap/3+1,这样就是真正的希尔排序了。但由于循环层数过多（已经达到了4层），因此，我们将思路从上述的：将gap组依次进行排序（这句话在上面代码里）变成让gap组一起排序，这样就是把两个循环合并成了一个循环：（如下代码展示）

gap组依次进行排序：

for (int j = 0; j < gap; ++j)//将gap组依次分别进行排序
{
    // [0, end]插入 end+gap  [0, end+gap]有序  --间隔为gap的数据
    for (int i = j; i < n - gap; i += gap)
    {
        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

变成gap组一起排序：

//优化成两层循环,但效率上实际没太大差别
for (int i = 0; i < n - gap; ++i) //gap组数据依次多组并排
{
    // [0, end]插入 end+gap  [0, end+gap]有序  --间隔为gap的数据
    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

2.2 希尔排序代码🚀

void ShellSort(int* a, int n)//希尔排序
{
    // gap > 1 预排序
	// gap == 1 直接插入排序
	//优化成两层循环,但效率上实际没太大差别
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; ++i) //gap组数据依次多组并排
		{
			// [0, end]插入 end+gap  [0, end+gap]有序  --间隔为gap的数据
			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
30
31

2.3 希尔排序特性🚀

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定：

《数据结构(C语言版)》— 严蔚敏

《数据结构-用面相对象方法与C++描述》— 殷人昆

因为我们的gap是按照Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，我们暂时就按照蓝色框的时间复杂度来算。

3. 选择排序🚀

3.1 基本思想🚀

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

• 在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素
• 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
• 在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

3.2 直接选择排序🚀

void SelectSort(int* a, int n)
{
    int begin = 0, end = n - 1;
    while (begin < end)
    {
        //选出最小的放在begin位置
        //选出最大的放在end位置
        int mini = begin, maxi = begin;
        for (int i = begin + 1; i <= end; ++i)
        {
            if (a[i] > a[maxi])
            {
                maxi = i;
            }
            if (a[i] < a[mini])
            {
                mini = i;
            }
        }
        Swap(&a[begin], &a[mini]);

        if (maxi == begin)//修正一下maxi,因为上一个begin位置已经被换走了
        {
            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

3.3 选择排序特性🚀

直接选择排序的特性总结：

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

4. 堆排序🚀

4.1 基本思想🚀

对于堆排序，之前的文章已经详细的讲到，因此，我将堆排序的链接放在这里，这里主要展示堆排序代码：

堆排序讲解

4.2 堆排序代码🚀

void Swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
void 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;
		}
	}
}

void HeapSort(int* a, int n)//堆排序
{
	//建堆 
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}

	//选数
	int i = 1;
	while (i < n)
	{
		Swap(&a[0], &a[n - i]);
		AdjustDown(a, n - i, 0);
		++i;
	}
	
}
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

4.3 堆排序特性🚀

1. 时间复杂度不分情况好坏而变化
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

5. 冒泡排序🚀

5.1 基本思想🚀

冒泡排序，大家再熟悉不过，就是将其反复交换排序，但是这里将展示冒泡的优化。在冒泡排序的交换过程中，在冒泡排序交换节点的过程中我们新增一个flag,每一次交换排序时如果发现顺序不对那么相邻之间的两个元素就会交换位置，当然，如果在一趟交换排序中一次都没有交换，那么就说明接下来的元素已经是有序的，但对于一般的冒泡排序来说，即便有序，仍然需要将所有都遍历到，但我们的目的是将其优化，也就是当确定这趟排序中已经有序，那么我们就不需要继续排序，跳出这个循环即可，而这个时候就是需要flag这个变量判断：

5.2 冒泡排序代码🚀

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

void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int flag = 0;
		for (int j = 0; j < n - i - 1; j++)
		{
			if (a[j] > a[j + 1])
			{
				Swap(&a[j], &a[j + 1]);
				flag = 1;
			}
			
		}
		if (flag == 0)
		{
			break;
		}
	}
}
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

5.3 冒泡排序特性🚀

1. 此优化后的代码当完全有序时的时间复杂度为O(N)
2. 时间复杂度：O(N)
3. 空间复杂度：O(1)
4. 稳定性：稳定

6. 快速排序（重点）🚀

6.1 快速排序介绍🚀

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

// 假设按照升序对array数组中[begin, end]区间中的元素进行排序
void QuickSort(int* a, int begin, int end)
{
    if(begin >= end)
        return;
    
    // 按照基准值对a数组的 [begin, end]区间中的元素进行划分
    int keyi = partion(a, begin, end);
    // 划分成功后以div为边界形成了左右两部分 [begin, keyi-1] 和 [keyi+1, end]
   
    QuickSort(a, begin, keyi-1); // 递归排[begin, keyi-1] 
    QuickSort(a, keyi+1, end);// 递归排[keyi+1, end]
}
1
2
3
4
5
6
7
8
9
10
11
12
13

partion函数就有着这种作用：将选中的keyi位置（keyi一般在开头或结尾的位置）对应的元素为基准，使左边的元素都小于a[keyi]，右边的元素都大于a[keyi]（因为是要升序）

即：

通过这样就能确定key下标对应元素排序之后的位置，因为左边都比其小，右边都比其大，然后通过递归将其左右两个区间分别按照这样的操作来确定元素的位置,当子区间剩下一个元素时就截止，最后得到的就是升序的数据。（看完这个在看看上面的代码）而partion函数有三种，分别是：

1. hoare版本
2. 挖坑法
3. 前后指针法

接下来就详细说说partion函数的三个版本：

6.2 hoare版本🚀

注：partion函数在这里别名为PartSort1函数

此单趟排序：

1. 选一个key。（一般是第一个或者最后一个）
2. 单趟排序，要求小的在key左边，大的在key右边

此为key在左边，R先走（key在右边，就需要L先走） 规则解释如下

hoare版本的思路是这样的：我们把最左侧的下标用keyi保存之后，需要让R先出发，遇到比a[keyi]小的元素则需要停下，然后L出发，当L找到比a[keyi]大的元素之后，让R和L对应的元素交换，接着R继续走去寻找比a[keyi]小的元素，重复此步骤直到L和R相遇，相遇之后的所对应的元素一定比a[keyi]对应的数小（下文证明描述），最后将这个相遇时对应的元素与a[keyi]进行交换，更新keyi的位置为相遇位置并返回相遇的位置，至此，此函数结束，新的a[keyi]的左侧数据比它小，右侧数据比它大。

• 那为什么相遇对应的元素一定比a[keyi]对应的元素小呢？

由于L和R不能同时走，因此，相遇有两种情况：1. L撞R，2. R撞L

• L撞R：L撞R说明此时R已经停下，而L正在寻找比a[keyi]大的元素，，但R停下的原因就是R找到比a[keyi]小的元素，因此这时候相遇的位置的元素一定比a[keyi]小。
• R撞L：R撞L说明此时L已经停下，我们知道，L停下就说明找到了比a[keyi]大的元素,此时R也停下，在R运动之前，二者之间一定会交换，交换后的L对应的元素一定比a[keyi]小，当R继续运动撞上L时，此时相遇的位置对应的元素一定比a[keyi]小。

介绍完之后，看看如下实际步骤：

最终将3与6互换。

PartSort1代码：

//[left. right]
int PartSort1(int* a, int left, int right)
{
	int keyi = left;
	while (left < right)//为了防止错开里面的条件都要加上此条件
	{
		//右边先走，R找小
		while (left < right && a[right] >= a[keyi])//一定要把相等的给过滤掉，否则会产生死循环
		{
			--right;
		}

		//L找大
		while (left < right && a[left] <= a[keyi])//一定要把相等的给过滤掉，否则会产生死循环
		{
			++left;
		}

		if(left < right)
		    Swap(&a[left], &a[right]);
	}

	int meeti = left;

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

	return meeti;
}
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

将其嵌入QuickSort就可以通过逻辑图来看：

由于是二叉树递归实现，当数组有序或接近有序的时候，采用这种方法效率很低，逻辑图会变成这样：

因此，我们需要将这种接近有序的情况也进行处理，使其效率上升，通过改变key的位置从而提升效率。那么key可以如何调整呢，其实key可以随机选一个位置，这样大概率会避免这种情况，但也有可能随机取到的位置就是最左侧或者最右侧的位置，因此也不是足够严谨，通过这一系列的考虑，我们可以利用如下的思想来选择key的位置：

优化选key逻辑：

1. 随机选一个位置做key。
2. 针对有序，选正中间做key。
3. 三数取中。第一个，中间位置，最后一个 选出中间大小的值

上述三个方法均可适用，但为了其通用性以及制定标准，三数取中是不二之选。

三数取中：即将left mid right 三个位置对应的元素进行比较，选择中间大的数的下标给key,再将a[key]与a[left]交换一下，这样，就避免了因有序或者接近有序而造成效率的低下。

三数取中：

int GetMidIndex(int* a, int left, int right)//优化，三数取中
{
    int mid = left + (right - left) / 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

优化后：

//以下均为快速排序涉及的函数
void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int GetMidIndex(int* a, int left, int right)//优化，三数取中
{
	int mid = left + (right - left) / 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;
		}

	}


}
//[left, right]
int PartSort1(int* a, int left, int right)
{
	//三数取中
	int mid = GetMidIndex(a, left, right);
	Swap(&a[left], &a[mid]);

	int keyi = left;
	while (left < right)//为了防止错开里面的条件都要加上此条件
	{
		//右边先走，R找小
		while (left < right && a[right] >= a[keyi])//一定要把相等的给过滤掉，否则会产生死循环
		{
			--right;
		}

		//L找大
		while (left < right && a[left] <= a[keyi])//一定要把相等的给过滤掉，否则会产生死循环
		{
			++left;
		}

		if(left < right)
		    Swap(&a[left], &a[right]);
	}

	int meeti = left;

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

	return meeti;
}
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

这个之后仍然可以进行优化：小区间优化

通过此递归类似于完全二叉树的结构，想一想由于递归最后三层调用堆栈根据完全二叉树的架构相当于总体的87.5%（从下到上：50%+25%+12.5%），因此，为了节省调用堆栈的空间，可以让最后的这2^3=8个数据用其他排序来代替递归完成，这样就节省了一大半以上的调用堆栈的性能，那么如何改动呢，这里直接在QuickSort函数里面进行修改即可：

void QuickSort(int* a, int begin, int end)//快速排序
{
	if (begin >= end)
	{
		return;
	}

	// 由于递归最后三层调用堆栈根据完全二叉树的架构相当于总体的87.5%（50%+25%+12.5%），因此，为了节省调用堆栈的空间，可以让最后的这2^3=8个数据用其他排序来代替递归完成
	if (end - begin <= 8)
	{
		//随便一个排序都可，这里利用直接插入排序
		InsertSort(a + begin, end - begin + 1);//上面有此函数
	}
	else
	{
		int keyi = PartSort1(a, begin, end);
		//[begin, keyi-1] keyi [keyi+1, right]
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, 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

6.3 挖坑法🚀

注：partion函数在这里别名为PartSort2函数

与hoare版本不同的是，挖坑法的思路是碰到一个就去赋值一个，而不是像hoare中两个都找到进行交换。挖坑法的思路是这样的：

第一步：同样的先进行三数取中避免有序或接近有序，这一点与hoare的思想是一样的，接下来我们用key保存最左侧的值（此值经过这个函数调用结束后就会回到排序后的应有的位置上，即左边比key小，右边比key大，上面的hoare用的是keyi,keyi保存的是下标），并且我们将这个最左侧的位置记录为坑位，用hole = left 保存。

第二步：同样根据右找小，左找大的原则直到相遇，不过具体的行动有所改变。先让右侧的right往左找小，找到之后，就将此值填到坑位，此位置就变成新的坑位，即：hole = right ;接下来左侧的left向右找大，找到之后，将此值填到新的坑位，再将此位置变为坑位：hole = left ，一直到left与right相遇。

第三步：通过前面的步骤，left与right相遇后的位置会变成新的坑位,此时将key保存的数字填入此坑位，此坑位就是数组有序后key的位置。

以此为例就是这样：

代码：

void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
int PartSort2(int* a, int left, int right)//2. 挖坑法
{
    //三数取中
    int mid = GetMidIndex(a, left, right);
    Swap(&a[left], &a[mid]);

    int key = a[left];
    int hole = left;//最左侧初始化坑位
    while (left < right)
    {
        //右边找小，填到左边坑
        while (left < right && a[right] >= key)
        {
            right--;
        }
        a[hole] = a[right];//找完就填坑
        hole = right;//右边就成了新的坑

        //左边找大，填到右边坑
        while (left < right && a[left] <= key)
        {
            left++;
        }
        a[hole] = a[left];//找完就填坑
        hole = left;//左边就成了新的坑
    }
    a[hole] = key;
    
    return hole;
}
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

6.4 前后指针法🚀

注：partion函数在这里别名为PartSort3函数

同样最开始是三数取中，然后不同的是前两个版本的方式都是从两侧相向出发，而这个前后指针法则是在同一侧一起出发，那么具体思路是：

定义两个变量cur，prev，这两个变量都作为下标向后运动，让prev = left,cur = left+1,对应前后指针，对于cur这个变量的要求是找比a[keyi]小的数，一旦找到，就先++prev，因为prev是从keyi的位置开始的，而keyi这个位置是循环结束需要进行交换的，因此++prev,然后将a[prev]和a[cur]的值进行交换，再cur++,目的是让比a[keyi]小的数都在左侧，大的都在右侧，直到cur>right截止循环，此时的prev对应的位置就是a[keyi]排序后对应的位置，将a[keyi]的值与a[prev]进行交换，最后返回prev。

执行具体步骤：

PartSort3代码：

int PartSort3(int* a, int left, int right)//3. 前后指针法
{
    //三数取中
    int mid = GetMidIndex(a, left, right);
    Swap(&a[left], &a[mid]);

    int keyi = left;

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

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

        ++cur;
    }
    Swap(&a[prev], &a[keyi]);//prev对应的数字一定比key小，可推导，实际上prev对应的一定比key小，cur对应的一定比key大

    return prev;
}
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

6.5 快速排序完整代码（递归）🚀

这里我们采用第一种hoare版本的PartSort1进行实现：

//以下均为快速排序包含的函数
void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int GetMidIndex(int* a, int left, int right)//优化，三数取中
{
	int mid = left + (right - left) / 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;
		}

	}


}

//[left. right]
int PartSort1(int* a, int left, int right)//1.Hoare版本
{
	//三数取中
	int mid = GetMidIndex(a, left, right);
	Swap(&a[left], &a[mid]);

	int keyi = left;
	while (left < right)//为了防止错开里面的条件都要加上此条件
	{
		//右边先走，R找小
		while (left < right && a[right] >= a[keyi])//一定要把相等的给过滤掉，否则会产生死循环
		{
			--right;
		}

		//L找大
		while (left < right && a[left] <= a[keyi])//一定要把相等的给过滤掉，否则会产生死循环
		{
			++left;
		}
		if(left < right)
		    Swap(&a[left], &a[right]);
	}
	int meeti = left;
	Swap(&a[left], &a[keyi]);
    
	return meeti;
}
//[begin, end]
void QuickSort(int* a, int begin, int end)//快速排序
{
	if (begin >= end)
	{
		return;
	}

	// 由于递归最后三层调用堆栈根据完全二叉树的架构相当于总体的87.5%（50%+25%+12.5%），因此，为了节省调用堆栈的空间，可以让最后的这2^3=8个数据用其他排序来代替递归完成
	if (end - begin <= 8)
	{
		//随便一个排序都可，这里利用直接插入排序
		InsertSort(a + begin, end - begin + 1);
	}
	else
	{
		int keyi = PartSort1(a, begin, end);
		//[begin, keyi-1] keyi [keyi+1, right]
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, 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

6.6 快速排序非递归实现🚀

递归的最大问题就是极端场景下，深度太深，会发生栈溢出，因此我们需要用数据结构中的栈来模仿递归过程

非递归实现快速排序，我们就需要用到栈章节中的Stack.h和Stack.c

栈的代码

非递归实现快速排序在思想上是用栈的特性来模拟递归，那么模拟的思路如下：

我们仍然需要上面的partion函数，即PartSort系列中的一个来进行排序，而栈的作用就是用来存储下标区间，想一想递归实现的快速排序，也是先在整体然后切割成一份一份的区间进行一个元素一个元素的排序，非递归也是如此，由于递归采用了先左后右的思想，因此，在栈里面我们也先入右区间再入左区间以便Top时先左后右，先将最左侧的left和最右侧的right进入后，通过一趟排序PartSort3（任意一个都可）能将中间的keyi排序后的位置确定，并返回keyi下标，接下来我们将其看成三部分：

1. [left, keyi-1]
2. keyi
3. [keyi+1,right]

而第二部分已经排好序，因此我们需要将3和1按照先后顺序依次入栈（改变顺序也可以，但为了模仿递归，每次都将按照这个顺序）都入栈之后继续分别将两个区间中的左右赋值给left和right，每个区间就能再分成三个部分，而每一个区间分成之后的第二个部分都会用PartSort3排好序，当区间中的left>=right时就不进行操作，直接进入下一个循环。值得注意的是，这里的非递归的顺序与递归其实是一样的，因为每次先入右区间再入左区间之后，下一次的循环中的left和right都会取出左区间，然后进行StackPop，这样每次执行左右区间一起入栈之后，都会对左区间进行操作，而右区间将保存在栈中，待左区间排好之后，右区间才会开始。

通过递归转化成非递归，相应的操作也会转化成相应的操作：

1. 递归变成循环
2. 递归的返回条件变成循环条件：栈是否为空

来看看具体步骤的结果：

此时会发现除了我们排好的keyi，其他的顺序也发生变化，当然，这是由于PartSort3造成的（PartSort系列的函数的执行结果与功能相同，但执行方式不同，不同的PartSort会对除了keyi以外的顺序产生不同的结果），但这本身也不是我们需要关注的，只要keyi的位置达到我们想要的就足够了

第二次开始之后就是入四个数，分别为右区间和左区间也就是第一部分和第三部分，入之后，左区间的两个值被left和right获取并Pop掉，而右区间的则保存在栈中，通过st->a的指针指向的数为6就能看出0和3已将被Pop掉了，6下面的9由于监视的变量是指针，因此只能看到栈顶的数，不过栈顶为6已经说明了左区间的两个数已经被用过并且Pop掉了。

接下来的步骤同样按照以上的逻辑执行……

快速排序非递归实现： 注：需要引用Stack.c (上面的链接)

void QuickSortNonR(int* a, int begin, int end)//快速排序非递归
{
	ST st;
	StackInit(&st);

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

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

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

		/*if (left >= right) 把这个也可以换成下述分别的if，这样可以减少入栈次数
		{
			continue;
		}*/

		int keyi = PartSort3(a, left, right);
        // [left, keyi-1]  keyi  [keyi+1, right]

		if (keyi + 1 < right)
		{
			StackPush(&st, keyi + 1);
			StackPush(&st, right);
		}
		
		//上下两组push顺序调换也可以，不过为了模拟递归的过程，这里仍是先入右区间，再入左区间
		if (left < keyi - 1)
		{
			StackPush(&st, left);
			StackPush(&st, keyi - 1);
		}
	}

	StackDestory(&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
32
33
34
35
36
37
38
39
40
41

用队列也能完成，用队列就是以层序遍历的方式进行，模拟不出函数调用堆栈的实际情况，只是访问的顺序不一样，要保持需要的那个顺序，那就要用栈。

6.7 快速排序特性：🚀

上面叙述了这么多，但是其特性是一致的，哪怕非递归也是模仿递归思想实现的，因此，我们在这里进行总结：

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

2. 时间复杂度：O(N*logN）

3. 空间复杂度：O(logN)

4. 稳定性：不稳定

5. 在八大排序算法中，快速排序是非常快的也是非常重要的，但是普通的快速排序还没有那么快，快的是优化后的快排，即加上三数取中

对于快速排序，仍有一个库函数qsort可以实现（这个其实应该在C语言中就讲到，由于鄙人当时偷懒……）在这里就提到一下，具体的使用方法可以参考这篇文章：【C语言】快速排序函数qsort（）

7. 归并排序🚀

7.1 基本思想🚀

介绍：

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

事实上，绿色下方的操作并不存在，而是将归的逻辑展现出来与实际上的递进行联系，有递就有归，对于归并排序，上面的介绍是官方的定义，而下面将是我对于归并排序的理解：

当我们看到归并排序时，就会想到归并的前提，必须是两个有序的数组才能进行归并，而且需要创建新的数组使另两个需要归并的元素进行尾插，就比如合并有序链表利用的就是这个思想。但我们话说回来，对于一组随机顺序的数组将其归并排序，就需要将其分解成两组有序的数组从而进行尾插新数组排序，然而，一个随机数组在不利用其他排序的情况下分解成两个数组使其变成有序是没办法操作的，换句话说就是分成的两个数组不一定是有序的，那么就需要将分解的两个数组分别再分解成两个数组，目的就是让其分解之后的数组有序，才能让这个分解之前的数组通过归并变得有序，这时候我们应都有一个常识：如果一个数组只有一个元素，那么这个数组一定是有序的！ 当然，如果在分解的途中，没有到分解成一个元素时才有序，我们仍然需要分解到一个数组，因为分解的两个数组是否有序是随机的，我们无法进行判断，而如果数组中只有一个元素，那么通过传进去的两个参数begin和end分别代表数组的头和尾，如果begin >= end，那么就说明这个数组只有一个元素，可以return; 到这里，再看看上面的展开图就会发现都是分解到了一个数组只有一个元素之后，才进行归并，（下面的紫色实际上与上部分的红色是重合的，是红色部分的归的步骤，而红色部分是向下递）因此到这里可以看出，采用这种方法是递归实现的。

上面已经提到，归并需要中间新建数组使需要合并的有序数组来进行尾插，最后赋值给原数组。但是递归怎么可以控制新建数组的个数或者确定是同一个数组呢？通过建立递归的子函数就可以实现，即在递归函数中开辟与需要归并数组等大小的数组，在子函数进行递归即可！

7.2 归并排序递归代码🚀

void _MergeSort(int* a, int begin, int end, int* tmp)// 类似于二叉树的后序遍历
{
	if (begin >= end)
	{
		
		return;
	}


	int mid = (end + begin) / 2;
	// [begin, mid] [mid+1, end]

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

	//归并 取小的尾插
	//[begin, mid] [mid+1,end]
	int begin1 = begin, end1 = mid;
	int begin2 = mid+1, end2 = end;
	int i = begin;
	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++];
	} 

	// 拷贝回原数组 -- 归并哪部分就拷贝哪部分过去
	memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}

void MergeSort(int* a, int n) // 归并排序递归实现
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}

	_MergeSort(a, 0, n - 1, tmp);//子函数递归
	free(tmp);
	tmp = NULL;
}
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

动图：

7.3 归并排序特性🚀

对于递归排序，通过介绍中的逻辑图与代码结合可以看出，先遍历左，再遍历右，再合并回去，这与二叉树的后序遍历的逻辑是相同的，并且每次分成两个子数组不是相同就是个数差一个，因此，此结构类似于满二叉树或者是完全二叉树，其高度为logN,而每一行即每一层可以看成成最大数N,因此，其时间复杂度为O(N*logN)。

归并排序特性总结：

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

当我们总结到这里之后，不像前面一样就结束了，而是继续讲解归并排序，想到上面的快速排序的递归实现特殊性中或许会由于极端场景导致递归次数太多从而造成栈溢出导致程序崩溃，对于归并排序，由于每次取的都是中间，基本上不会出现栈溢出的现象，然而归并排序的非递归实现仍然需要学习，因为面试可能会叫你手撕非递归，那么接下来看看归并排序的非递归实现：

7.4 归并排序的非递归实现（难点）🚀

思想：

上述的快速排序非递归的引出是为了防止出现特殊场合导致栈溢出从而程序崩溃，其中快排的非递归利用了栈，但对于非递归的归并来说，不需要用到栈或者队列，而是像斐波那契数列一样，可以将递归变成循环。

先不考虑一些细节问题，仍然是8个数，将其通过非递归的归并进行排序，那么步骤就是这样：

（结合下述代码）不难发现，每一次循环，每组归并的元素数量都乘2，因此，定义一个gap=1,通过每次之后gap *= 2，就可以实现，但问题是，这样分组的归并只有满足元素数量是2的n次幂时才可以进行这样的分组排序，若数组有10个元素，一开始也就是10组，每组一个有序的元素；归并循环一次之后会变成5组，每组两个有序的元素，这一步是可以实现的。然而，当继续归并时，第一组和第二组可以归并，第三组和第四组可以归并，但第五组只有一组就不能归并了我，但按照上图的逻辑，会虚化出第六组，下标的左右区间为begin2和end2将会越界，因此为了避免这样的错误，需要对边界进行处理：

对于两个需要归并的数组，有左边结和右边界，归并两个数组时发生的越界情况，无非有这么三种：

1. 第一组越界：第一组的左区间不可能越界，因为begin1是直接被j赋值，j在for循环条件下永远小于n，因此第一组越界是end1越界，需要break;
2. 第二组全部越界：全部越界代表着begin2也就是第二组的左区间就发生了越界，即begin2>=n，此时也需要break;
3. 第二组部分越界：第二组的部分越界说明右区间的end2越界，但仍然说明有对于相应的第一组来讲，这个第二组可以与之匹配，而归并思想与两个数组中元素的数量无关，只与是否有序有关，因此，这里可以将右区间end2进行修改，让其end2 = n-1,这样就会与之匹配。

再思考一下这样的问题，对于前两种操作的break,虽然不会有错误的操作，但是会不会丢失一些元素归并的步骤呢?答案是不会丢失，这就需要结合具体的代码来看了，因此先展示归并排序非递归的代码：

void MergeSortNonR(int* a, int n)//归并排序非递归
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
    {
        perror("malloc fail");
        return;
    }

    int gap = 1;
    while (gap < n)
    {
        for (int j = 0; j < n; j += 2 * gap)
        {
            //归并 取小的尾插

            int begin1 = j, end1 = j + gap - 1;
            int begin2 = j + gap, end2 = j + 2 * gap - 1;

            // 第一组越界
            if (end1 >= n)
            {
                break;
            }

            //第二组全部越界
            if (begin2 >= n)
            {
                break;
            }

            //第二组部分越界
            if (end2 >= n)
            {
                //修正一下end2，继续归并
                end2 = n - 1;
            }
            int i = j;
            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++];
            }
            // 拷贝回原数组 -- 归并哪部分就拷贝哪部分过去
            memcpy(a + j, tmp + j, (end2 - j + 1) * sizeof(int));
        }


        gap *= 2;
    }


    free(tmp);
    tmp = NULL;
}
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

即便break,在后面的循环里，最后一步的归并仍然是将两部分合并成一部分，也就是说，这两部分加起来就是所有的元素，不会发生遗漏，此外，这最后一步中，若原数组元素的数量不是2*n的话，一定会发生第二组部分越界，这时候只需要修正一下end2即可，因此第三种情况的修正是至关重要的，会将第一种和第二种情况弥补回来。

8. 计数排序🚀

8.1 基本思想🚀

对于计数排序，其用到了哈希的思想，因此了解这个排序的前提需要理解哈希的思想。

**思想：**计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：

即通过定义哈希hash[]数组，将原数组中的值分别计数，最后根据hash的顺序和记录的次数从头到尾释放hash的下标，因为hash的下标就是原数组元素的值

因此，hash数组下标的条件就原数组元素的条件。

1. 下标不能为负数
2. 下标不能为小数

对于上述的两个条件，小数是无法制约的，也就是说原数组元素如果是小数是没办法利用计数排序的。但对于负数，我们会采取相对映射的方法进行处理。

绝对映射：hash[a[i]]，就是纯粹的值与值对应

相对映射：hash[a[i] + n],相对映射就是由于a[i]的值是负数或者是集中在一起的数，我们就可以将其加上或者减去一个n，让下标变得合理，也就是负数+n变正数从而满足下标；正数-n可以缩小hash开辟的空间

因此，对于哈希思想，相对映射远远好于绝对映射。

8.2 计数排序代码实现🚀

void CountSort(int* a, int n)//计数排序
{
	int min = a[0];
	int max = a[0];
	for (int i = 1; i < n; i++) // 为了相对映射
	{
		if (a[i] < min)
		{
			min = a[i];
		}
		if (a[i] > max)
		{
			max = a[i];
		}
	}
	//统计次数的数组（哈希思想）
	int range = max - min + 1;
	int* hash = (int*)malloc(sizeof(int)*range);
	if (hash == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	memset(hash, 0, sizeof(int) * range);

	//统计次数
	for (int i = 0; i < n; i++)
	{
		hash[a[i] - min]++;
	}

	//回写 - 排序
	int j = 0;
	for (int i = 0; i < range; ++i)
	{
		//出现几次就回写几个i+min
		while (hash[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

8.3 计数排序特性🚀

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

9.排序特性总结🚀

总结：

对于上述八大排序，有需要掌握递归的，有需要掌握非递归的，有的理解起来很难，但仍有其他类型的排序比如基数排序、猴子排序、桶排序、甚至睡眠排序等等……，但这些排序与八大排序相比来说相差许多，因此，掌握这八大排序足矣！