【数据结构】三万字图文讲解带你手撕八大排序(附源码)

如果无聊的话就来逛逛 我的博客栈 吧! 🌹

一、前言

Hello小伙伴们我是 $anduin$ 。距离上次更新已经整整一个礼拜了。那么有小伙伴可能会疑惑是不是 $anduin$ 偷懒不写文章呢让我狡辩一下 … 其实是 $anduin$ 最近在刷题但是感觉那些题解写起来质量也不高于是就没发出来。但是一天前$anduin$ 突然想起了好久没更新了于是我决定要写一篇 “硬核” 的文章用这篇文章来弥补这近一个星期的摆烂。于是经过两天的沉浸式写博客本篇文章就诞生了。总体文章有 $30000$ 字左右篇幅较长这是我数据结构专栏中最满意的一篇博客因为这一次写文章的时候掉的头发是最多的(bushi)就用这篇 八大排序 来完美地收尾初阶数据结构吧

咳咳好了现在我们进入正题首先介绍一下文章内容
我们的文章内容主要围绕下图来进行讲解在本篇博客中我会阐述排序的概念八大排序的思想、代码思路、代码实现和时空复杂度分析并且在最后做出总结并且附上源码链接。

今天的内容还是含金量挺高的(尤其是带⭐️的)所以小伙伴们打起精神如果认认真真看完这边博客并下去练习我相信你就可以手撕八大排序

二、排序的概念和运用

所谓排序就是将一串数据按照某种规律或者以某种特性或关键字将数据按照递增或者递减将数据从无序转变为有序的操作。

而排序其实在我们生活中运用十分广泛例如在购物网站上选购一个电脑可以通过综合、销量、评论数、新品价格来排序如果对价格有需求也可以按照价格升序或者降序来排序通过这种方式来买到心仪的商品。

而究其根本这些都需要排序算法来实现。那么在编程中有什么排序算法它们的性能如何如何模拟实现这些算法如果还不太了解的话没关系因为今天的内容就是讲解经典八大排序下面我们就会一一讲解并实现。

三、八大排序讲解及实现

1、直接插入排序

1.1 排序思路

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

我们的扑克牌就使用了插入排序的思想

比如拿到牌之后我们都会理牌那么通常就会按照大小顺序将“对子”“顺子”按照特定顺序将牌理成整体有序或者局部有序。

进行插入排序的步骤

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

这么说可能还不是很直观其实插入排序的过程就可以想象成之前我们学习 顺序表的尾插 我们假定序列 $array[]$ 只有 $1$ 个数。假定每次都是插入一个元素且插入的元素需要将这个 ”顺序表“ 构成有序如果插入元素 $array[i]<arr[i-1]$ 那么就至少需要向前调整 $1$ 次如果 $array[i]\ge array[i-1]$ 那么就 直接插入在 $i$ 下标处 即可。

动图演示插入排序过程

1.2 代码实现

对于 单趟插入排序 假设 $end$ 是上一次排序的最后一个位置那么本次需要排序的元素为 $tmp=a[end+1]$ 。

之后通过一个循环如果 $a[end]>tmp$ 说明 $tmp$ 插入的位置在前面所以把 $a[end+1]=a[end]$ 将元素往后移 $1$ 格并将 $end--$ 将索引向前调整如果 $a[end]<=tmp$ 说明 $tmp$ 在当前位置$end+1$ 就可以直接插入停止循环。

最后 $end$ 停下来的位置永远是插入位置的前一个位置 比如

• 有序序列为 $135$ $end=2$ $a[end]=5$ $tmp=a[end+1]=0$
• $end=2,a[end]=5,tmp=0\to a[end]>tmp\to a[end+1]=a[end]\to a[3]=5end--\to end=1$
• $end=1,a[end]=3,tmp=0\to a[end]>tmp\to a[end+1]=a[end]\to a[2]=3end--\to end=0$
• $end=0,a[end]=1,tmp=0\to a[end]>tmp\to a[end+1]=a[end]\to a[1]=0end--\to end=-1$
• $end=-1\to end<0$终止循环
• $a[end+1]=tmp$ 最终序列 $0135$

这是单趟那么完整的也很简单嘛其实就是 $n-1$ 趟因为第一个元素是不用排的第一趟其实就是排的序列的第二个元素了。每趟最终插入的位置为 $end+1$ 需要防止越界。

void InsertSort(int* a, int n)
{
	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;
			}
		}

		// 填到 end + 1 位置
		a[end + 1] = tmp;
	}
}

1.3 时空复杂度

插入排序的最坏的情况为数组与我们需要排序的目标相悖。比如我们需要排升序但是原始序列为降序 。为最坏情况为 $O(N^2)$ 。如果目的是升序序列也正好是升序的话为最好情况这时时间复杂度为 $O(N)$ 。

取其最坏最终时间复杂度$O(N^2)$ 。

插入排序并没有开辟额外空间所以 空间复杂度$O(1)$

2、希尔排序

2.1 排序思路

希尔排序也属于插入排序但是和直接插入排序又略微不同。

先看一下概念

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

这段话是什么意思呢这句话是说取一个整数作为 间距 $gap$ 对于每个元素与其间隔为 $gap$ 的元素分成一个组对每组排序 。不断调整 $gap$ 对每组进行不断排序在 $gap$ 调整到 $1$ 后进行插入排序就可以将数据排成有序。而按照间距 $gap$ 分组并排序被称为 预排序 。

所以可以归纳希尔排序的步骤就是 两点

1. 预排序
2. 插入排序

比如一次完整希尔排序 就像下图

2.2 代码实现

希尔排序属于插入排序而它的思想其实是和直接插入排序差不多的因为最后一次希尔排序为插入排序。希尔排序无非就是多了几组预排序的过程。

所以它的代码和直接插入排序是十分相似的。

对于插入排序我们其实就可以看做是 $gap=1$ 的希尔排序那么把插入排序一些数据做一下替换就得出了单组希尔排序

// 对于一组
for (int i = 0; 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];
            end -= gap;
        }
        else
        {
            break;
        }
    }
    a[end + gap] = tmp;
}

这里的 $gap$ 不仅是每组中元素的间距也是组数。上面代码只完成了单组对于完整的一组需要在外面套上一层循环需要循环 $gap$ 次

for (int j = 0; j < gap ;j++) 
{
	for (int i = j; i < n - gap; i += gap)
    {
        // ...
    }
}

我们发现当我们学习了直接插入排序之后写一趟希尔排序还是很简单的。原理嘛就和之前插入排序得到思路是相似的只需要把之前的挪动 $1$ 位看成挪动 $gap$ 位。不懂的画一下图就完全ok了。

还有注意一下对单组进行排序时的结束条件 $i<n-gap$ 这里结束条件是这个的原因为最后一组的最后一个元素下标为 $n-gap-1$ 当元素进行插入时不能越界。

而这样写就套了 三层循环 了看起来比较繁杂我们可以做出一些调整上方代码为排 $gap$ 组每次排一组。我们可以改进为 $gap$ 组并排

for (int i = 0; i < n - gap; i++) // 注意这里从 i+= gap 变为 i++
{
    int end = i;
    int tmp = a[end + gap];

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

    a[end + gap] = tmp;
}

这里就只有 两层循环 了代码更加简洁唯一做出改变的就是 $i+=gap$ 变为 $i++$ 。

这里就相当于每一次都是排其他组的数据举个例子当前 $i=0$ 那么此刻排的就是第一组之后 $i++$ $i=1$ 那么此刻就是排的第二组 … 当循环结束这 $gap$ 组数据也就都被排好了。这就是 $gap$ 组并排。

而 希尔排序的预排序的 $gap$ 越大时那么对于单组中的数据就可以更快地到后面(挪动间距为 $gap$)这就造成了数据就越不接近有序而 $gap$ 越小时数据跳动越慢但是越来越接近有序(比如插入排序) 。综合这两点所以我们一般进行希尔排序时$gap$ 是动态变化的$gap$ 的初值一般为数组长度 。之后每次除以一半或者除以三分之一。

比如我们每次除以三分之一

while (gap > 1)
{
    gap = gap / 3 + 1; // 或 gap /= 2;
    // gap 组并排
    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];
                end -= gap;
            }
            else
            {
                break;
            }
        }
        a[end + gap] = tmp;
    }
}

分析

这里调整时是用的 $gap=gap/3+1$为什么在这边 $+1$ 呢原因是希尔排序最后 $1$ 次为插入排序所以最后 $1$ 次 $gap=1$ 如果 $gap$ 初值为 $8$ 如果每次仅仅让 $gap/=3$ 由于c语言中 / 是下取整那么每次 $gap$ 就为 $820$ 最后 $1$ 次为 $0$ 无法完成希尔排序所以要加上一个 $1$ 这样就可以保证最后 $1$ 次 $gap=1$ 。

但是如果每次除以2的情况就不需要因为每次 $gap/=2$ 最终结果必定等于 $1$ 不信的话可以测试几组数据试试。

2.3 时空复杂度⭐️

数据被分为 $gap$ 组每组有 $N/gap$ 个数据。那么对于那么对于单组最坏的挪动次数就是$1+2+3+...+N/gap-1$ 是公差为 $1$ 的等差数列。

一共有 $gap$ 组那么对于一次预排序的总次数就为 $(1+2+3+...+N/gap-1)\times gap$ 但是这里 $gap$ 是不确定的是不好算的。

既然这样我们就换个角度来看对于每次预排序的时间复杂度该怎么计算

假设 $gap$ 每次除以 $3$ 一开始 $N$ 很大$gap=N/3+1$ 将当前 $gap$ 的取值带入上方对于一次预排序的次数的公式中 $(1+2+3+...+\frac{N}{N/3+1}-1)\times (N/3+1)\approx N$ 那么起始处 预排总次数约为 $N$ 。

… … …

快结束时$gap$ 很小这时次数也约为 $N$ 因为此刻由于预排序的作用 数组几乎有序几乎不需要排序遍历一遍大约就可以求出

而中间的结果我们先忽略就看起始两次我们将其认为对于每次预排序时间复杂度为 $O(N)$ 。

如果 $gap$ 每次除以 $3$ 那么就大约进行 $N/3/3/3.../3={\log }_{3}N$

如果 $gap$ 每次除以 $2$ 那么就大约进行 $N/2/2/2.../2={\log }_{2}N$

那么综合起来实际上希尔排序的时间复杂度大约在 $[{\log }_{3}N\ast N,{\log }_{2}N\ast N]$ 这个量级之间 和我们之前学习过的堆排序的时间复杂度相近。

但是这只是我们的一些计算推导实际上希尔排序真正的时间复杂度很难计算上面我们计算只是简单推导而已里面其实涉及到了很多数学只是所以我们再参考一下著名的数据结构书籍中对于希尔排序时间复杂度的分析

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

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

而 $gap$ 是按照 $Knuth$ 大佬提出的方式取值的$Knuth$大佬进行了大量的试验统计我们在这里先认为 希尔排序的最终时间复杂度为 $O(N^{1.3})$ 。

而空间复杂度就很简单了并没有开辟额外的空间所以空间复杂度为 $O(1)$ 。

3、直接选择排序

3.1 排序思路

选择排序的思想非常简单每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。

选择排序的步骤

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

下面使用动图展示一下选择排序的过程

3.2 代码实现

假设我们排升序那么每次就要选最小数的下标 $mini$ 遍历数组找出 $mini$ 然后交换让起始位置 $begin++$ 直到 $begin=n$ 停止此刻数组就有序了。

void SelectSort(int* a, int n)
{
	// 选 1 个数
	int begin = 0;

	while (begin < n)
	{
		int mini = begin;

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

		Swap(&a[begin], &a[mini]);
		begin++;
	}
}

这是我们单次选 $1$ 个数的情况实际上我们还可以一次选两个数 $mini$ 和 $maxi$ 对应最小和最大值

这里代码需要做出一些改变增加一个终止位置 $end$ 。循环找 $mini$ 和 $maxi$ 每次找到之后交换 $begin$ 和 $mini$ 对应的值和 $end$ 和 $maxi$ 对应的值将 $begin++,end--$ 直到 $begin\ge end$ 。

但是这里有一个 注意点

假设序列已经找到了 $mini$ 和 $maxi$

$begin$ 和 $maxi$ 的位置重合了那么 $begin$ 和 $mini$ 在交换的时候就把最小值换到了 $begin(maxi)$ 处最大值被换走了 。那么接下来交换 $end$ 和 $maxi$ 的时候就把 最小值 换到了 $end$ 处。

这就导致了排序错误我们原本期望的序列为图中含有绿色方格的一块。

所以我们需要处理一下但 $begin==maxi$ 时在交换过 $begin$ 和 $mini$ 的值后原 $mini$ 的值为当前的最大值那么就把 $maxi=mini$ 让最大值下一次能交换到正确的位置。

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

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

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

			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}

		Swap(&a[begin], &a[mini]);
		// 特殊处理
        if (begin == maxi)
		{
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);
		begin++;
		end--;
	}
}

3.3 时空复杂度

选择排序无论是选单边还是两边一起选时间复杂度都是铁铁的 $O(N^2)$ 。因为总是要每次遍历选出 最小/大下标然后进行数据交换。

所以选择排序的效率是不太行的一般不常用但是它的思路很简单。

空间复杂度是 $O(1)$ 因为没有开辟额外空间 。

4、堆排序

堆排序我们之前的文章已经详细讲解过详情见这篇博客【数据结构】堆的拓展延伸 —— 堆排序 和 TopK问题

其中时空复杂度我们也分析过

时间复杂度$O(N\times logN)$空间复杂度 $O(1)$ 。

5、冒泡排序

5.1 排序思路

冒泡排序属于交换排序所谓交换排序就是就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。

冒泡排序可能是这篇文章中最”亲切“的排序了。因为这个排序十分形象并且容易理解。这个排序像水面冒气泡一样从底部(数组开头)冒到水面上(数组结尾)一次冒一个数据所以被形象的称为“冒泡排序”。

我们再看一下动图

再从代码层面分析一下

$n$ 个数那么就需要冒泡 $n-1$ 趟将数据冒到结尾在每趟冒泡排序中比较相邻两个元素如果满足条件则交换。

5.2 代码实现

void BubbleSort(int* a, int n)
{
    // n - 1 趟
	for (int j = 0; j < n - 1; j++) 
	{
		int flag = 1;
        // 交换次数随着趟数减少
		for (int i = 0; i < n - j - 1; i++)
		{
			if (a[i] > a[i + 1])
			{
				Swap(&a[i], &a[i + 1]);
				flag = 0;
			}
		}
		if (flag)
		{
			break;
		}
	}
}

仔细看其实这里我们的代码是优化过的如果一趟冒泡排序中没有发生交换说明有序那么 break 退出循环。

比如序列

$112567$ 在一趟冒泡排序中始终满足 $a[i]\le a[i+1]$ 没有发生交换说明它本身是有序的所以无需排序了直接退出。

5.3 时空复杂度⭐️

冒泡排序的时间复杂度为 $O(N^2)$ 大家可能会疑惑冒泡排序不是优化过了吗为什么时间复杂度为 $O(N^2)$

接下来为大家解答冒泡排序每次的比较次数是随着趟数而减少的找一下规律其实可以发现它的总执行次数是一个公差为 $-1$ 的等差数列$(n-1)+(n-2)+...+1$ 根据等差数列求和公式得$\frac{(n-1+1)\times (n-1)}{2}$ 化简得 $\frac{n^2}{2}-\frac{n}{2}$ 根据时间复杂度规律最终为 $O(N^2)$ 。

而我们的优化是只对 数组前半部分有序 或 整体几乎有序 才有优化作用如果有序的部分在后半段每趟排序还是要从头开始一一比较相当于还是重新排序。

而且数组前半部分有序的优化程度也不大最好情况是 优化后 在 整体有序 的情况下遍历一遍数组通过 break 退出这时 最好时间复杂度为$O(N)$ 。

综上取最坏情况时间复杂度为$O(N^2)$。

空间复杂度为 $O(1)$ 。

6、快速排序⭐️

6.1 算法思想

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

6.2 快排递归版本

上方我们已经给出了思想我们这边再具体解释一下。

快排为交换排序的一种。快排在开始时会选择一个 key 做基准值并设定 给定然后进行单趟排序单趟排序后当排序停止会把 key 的索引或 key 值本身与边界某一值交换形成区间划分。

这个区间划分通常为 key 左边的值都小于 key key 右边的值都大于 key 这样就使得区间被划分了。中间的 key 值不用管当前 key 值已经到了正确的位置。那么现在排序就变为对左区间和右区间的排序。

那么每次排序后都会确定一个元素的位置确定位置后继续划分区间…这样的过程实际上就是递归通过递归对设定的基准值分割开的左右区间完成排序。

递归的返回条件为 $左区间索引\ge 右区间索引$ 此刻说明区间只有 $1$ 个元素或无元素。

根据上述解释我们可以大约写出框架

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	// 对左右区间进行划分
    int key = partion(a, begin, end);
    // 递归左右区间
    QuickSort(a, begin, key - 1);
    QuickSort(a, key + 1, end);
}

上述为快速排序递归实现的主框架我们可以发现与这个框架与二叉树前序遍历非常像对于认真看完二叉树博客的小伙伴们在写递归框架时可想想二叉树前序遍历规则即可快速写出来最后我们只要分析如何按照 基准值 来对区间中数据进行划分即可。

而按照基准值划分区间的方法有三种分别为 $hoare$ 版本、挖坑法、双指针版本 接下来我们一一讲解。

6.3 hoare 版本

$hoare$ 大佬的这个版本十分惊艳但是也是遗留 “坑” 最多的一个版本(自认为)。为什么这么说呢等过会我们就知道了。

先看动图

hoare 版本的思想是这样的

首先取左边界为基准索引 $key$ 定义两个指针 $left、right$ 分别指向最左边的元素和最右边的元素。

$right$ 先走如果 $right$ 指向的元素大于 $key$ 指向的元素则 $right--$ 如果指向元素小于 $key$ 指向的元素则停止

停止之后$left$ 开始走如果 $left$ 指向的元素小于 $key$ 指向的元素则 $left++$ 如果指向元素大于 $key$ 指向的元素则停止

当 $eft$ 和 $right$ 都停下后交换 $left$ 和 $right$ 位置的值。

直到 $left\ge right$ 循环停止。

上面过程就保证了 $left$ 和 $right$ 相遇的位置的值是小于 $key$ 的 此刻交换 $a[left]/a[right]和a[key]$ 令 $key=left或right$ 此刻左右区间就已经被划分好了$key$ 就是分割点。

我们这边规定如果取左边作为 $key$ 就要保证左边比 $key$ 小右边比 $key$ 大如果取右边作为 $key$ 则反一下。

下面讲一下细节

细节1我们有没有想过为什么 $left$ 和 $right$ 相遇的位置是小于 $key$ 的是巧合还是必然

这是必然的我们分析一下情况一共有两种情况

1. 第一种是 $right$ 停住$left$ 遇到 $right$ 相遇位置就是 $right$ 停住的位置。

当前情况就是 $right$ 在走时遇到比 $a[key]$ 小的元素停住了然后 $left$ 走时和 $right$ 位置是小于 $key$ 。

1. 第二种是 $left$ 停止$right$ 遇到 $left$ 相遇位置是 $left$ 停住的位置。

$left$ 和 $right$ 已经交换过一次元素所以 $left$ 的位置必定小于 $key$ $left$ 停住了之后$right$ 走直到和 $left$ 相遇相遇位置是小于 $key$ 的。

还有一种特殊情况就是 $right$ 先走右边的数字都比 $a[key]$ 大$right--$ $right$ 一直走到与 $left$ 重合$a[key]$ 和 $a[left]$ 交换后不变。

细节2开头说过 $hoare$ 大佬的版本有很多坑坑在哪里如何解决

其实这里容易引起的错误还是很多的比如

1. $key$ 右边的值都大于 $key$ 如果循环内部不加限制$right$ 就会一直 $--$ 当前还不会越界但是是一个隐患。

2. 左右两边都有和 $key$ 相等的值导致左右两边卡死。

举个例子

例如这种情况$a[key]=6$ 右边先走时由于 $a[right]=a[key]$ 所以不走左边走时由于 $a[left]=a[key]$ 所以不走。这样循环就卡死了

所以我们一开始的思路是需要 改进 的当 $a[right]\ge a[key]$ 时$right--$在 $a[left]<=a[key]$ 时$left++$。这样就解决了 死循环的问题 。

但是修好了这个 bug 另一个 bug 就冒出来了之前说过情况 $1$ 是有隐患的现在就显现出来了一旦加上上面的条件如果 $key$ 都大于 $key$ 那么这边由于没有限制了$right$ 就 ”飙“ 出去了。

所以在 $right$ 和 $left$ 每次走的时候需要加上限制 $left<right$ 。

由此我们就可以写出代码

// hoare 版本
int partion1(int* a, int begin, int end)
{
	int left = begin, right = end;

	int key = left;

	while (left < right)
	{
		// 右边先走
		// 两个条件一个防止跑出去找大于 a[key] 的值
		while (left < right && a[right] >= a[key])
		{
			right--;
		}

		while (left < right && a[left] <= a[key])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	// 交换值, key 作为分割点
	Swap(&a[left], &a[key]);
	key = left;

	return key;
}

怎么样是不是挺 “坑” 的(doge)。

6.4 挖坑法

由于 $hoare$ 大佬版本遗留的 “坑” 比较多所以后面就有一些好心人在 $hoare$ 版本的基础上对快排做出了一些改良比如我们的 挖坑法 。

虽然名字里带“坑”但是这个方法其实非常通俗易懂。

先看动图

挖坑法的思想

挖坑法多了一个 $hole$ 也就是坑位。我们将 key = a[left] 将 $key$ 保存到一个临时变量中假设 $key$ 这个位置的值被挖掉了形成一个坑位。

此时 $hole$ 就是坑位的下标。

依然是右边先走循环条件为 $left<right$ 并且 $right$ 指向的元素大于等于 $key$ 一旦 $right$ 停下来那么就把 $a[hole]=a[right]$ 把 $right$ 指向的值填到坑中此刻 $right$ 作为新的坑。而 $right$ 之前的值也被转移到了别的地方这个位置就被看做为空变成坑。

左边则是相同的思路同理左边停下后让 $a[hole]=a[left]$ 让 $left$ 作为新的坑。

直到 $left\ge right$ 停止。

最后的 $hole$ 就是 $key$ 值该去的地方把这个地方填上 $key$ 此刻 $hole$ 为分割点。

代码实现

int partion2(int* a, int begin, int end)
{
	int left = begin, right = end;
	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;

	// 最后 left 和 right 都在坑上和 hole 是重合的
	return hole;
}

6.5 前后指针版本

前后指针版本是最难的也是“最难”的。

说它最难是因为它本身思路比较抽象可能看动图都不太好理解说它“最难”实际上是反话因为它在某种程度上又很简单。

先看动图

前后指针法的思路

前后指针法的算法思想如下

定义三个变量$prev=begincur=begin+1,key=begin$主要使用 $cur$ 来遍历数组。

如果 $cur$ 指向的元素比 $key$ 小此刻停下来$++prev$ 交换调整后的 $prev$ 位置和 $cur$ 位置的值完事之后 $cur++$ 。

如果 $cur$ 指向的元素大于等于 $key$ 此刻 $cur++$ 其他啥也不干。

就这样循环往复直到 $cur>end$ 此刻交换 $prev$ 和 $key$ 位置的值。

当前的 $prev$ 作为新的 $key$ 为分割点。

这里的 $prev$ 和 $cur$ 有两种状况

1. 紧跟 $cur$ 这时 $a[cur]<a[key]$ 它俩同步往后走
2. 指向比 $key$ 大的位置的前一个$prev$ 和 $cur$ 之间就是 $\ge a[key]$ 的值。

每当 $a[cur]<a[key]$ $cur$ 位置小于 $a[key]$ 的值总是会被推到前面。

循环的过程就相当于是将小于 $a[key]$ 的值往前翻大于 $a[key]$ 的值往后像“翻跟头”一样推着走。

最后 $prev$ 的位置指向比 $a[key]$ 大的位置的前一个那么交换 $a[prev]$ 和 $a[key]$ 让 $key=prev$ 此刻 $key$ 为分割点。

优化思路

实际上我们发现当 $prev$ 紧跟 $cur$ 时它俩指向的是一个位置的元素所以这种情况是没必要交换的所以可以提前判断一下 $++prev!=cur$ 如果不满足这个条件那么干脆就不要交换了反正是同一个位置的值。

接着来写一下代码

int partion3(int* a, int begin, int end)
{
	int prev = begin;
	int cur = begin + 1;
	int key = begin;

	while (cur <= end)
	{
		// 找到比 key 小的值时跟 ++prev 位置交换
		// 小的往前翻大的往后翻

		// 重复数据不会交换 - 优化后
		if (a[cur] < a[key] && ++prev != cur)
			Swap(&a[cur], &a[prev]);

		// 重复数据会交换 - 优化前
		/*if (a[cur] < a[key])
			Swap(&a[++prev], &a[cur]);*/

			// cur 必定会走一步
		cur++;
	}

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

	//return prev; // 也可以 keyprev 和 key 是相等的

	key = prev;

	return key;
}

6.6 缺陷分析及优化

缺陷1有序或接近有序序列时间复杂度过高

其实对于快排来说它的时间复杂度是不稳定的比如上方三个版本在乱序的序列中效率可能还可以因为选取的 $key$ 值是随机的。

但是对于有序序列比如要排正序但是序列是逆序。如果每次选 $key$ 还是按照之前的选法那么每次可能就会选中最边上的一个选中最大或最小的数假设序列长度为 $N$ 每次选取一个极端值就会选取 $N$ 次就会递归 $N$ 层每一层中的时间复杂度为 $O(N)$ 那么最终时间复杂度为 $O(N^2)$ 。

但是这速度对于快排来说是不是说不过去我们能否每次选 $key$ 都 命中一段区间的中位数 让每段区间被二分那么最终就只会递归 $logN$ 层每层时间复杂度为 $O(N)$ 总时间复杂度为 $O(N\times logN)$ 。就像下图像一棵二叉树一样。

所以这边就引申出了第一个优化三数取中

所谓三数取中就是不取最大不取最小在 $begin,end,begin+end/2$ 中选取一个中间值尽量让 $key$ 可以命中每段区间中点。

而这段逻辑的话其实也并不复杂直接上代码

int GetIndexMid(int* a, int begin, int end)
{
	int mid = (begin + end) >> 1;

	if (a[begin] < a[mid])
	{
		if (a[mid] < a[end])
		{
			return mid;
		}
		else if (a[begin] > a[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
	else // a[begin] >= a[mid]
	{
		if (a[mid] > a[end])
		{
			return mid;
		}
		else if (a[end] > a[begin])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
}

缺陷2不必要的递归层数太多空间浪费

假设我们只有 $10$ 个数那么这种情况采用递归是不是浪费空间是不是多此一举

所以当 $end-begin+1<10$ 时可以采用插入排序优化这样子就没必要开那么多层函数栈帧。

对于一棵满二叉树最后一层的节点数占总结点数的 $\frac{1}{2}$ 倒数第二、三层分别为 $\frac{1}{4}、\frac{1}{8}$ 我们就假定快排递归展开后最后形态为完全二叉树。

假设当前有10个节点那么对于下图中红色箭头标出的点来说就无须递归因为再细分也就是一个数

那么大约就可以节省下三层的递归下三层的节点数占总结点数的 $87.5\%$ 省去了大部分的递归。

所以这边就引申出了 第二个优化小区间优化

这边我们范围给大一点当 $end-begin+1<15$ 时就采用直接插入排序优化。

递归框架中发生的变化

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	// 小于一定数目使用 直接插入排序
	if ((end - begin + 1) < 15)
	{
        // 数组位置a + begin
        // 元素个数end - beghin + 1
		InsertSort(a + begin, end - begin + 1);
	}
	else
	{
		int key = partion(a, begin, end);
		// 递归左右区间
		QuickSort(a, begin, key - 1);
		QuickSort(a, key + 1, end);
	}
}

缺陷3(最致命的一点)对于相同数据来说三数取中无效时间复杂度过高

比如 $22222222$ 这个序列来说三数取中是完全无效的特别数据量一大不仅容易超时还容易爆栈。

所以就需要优化这就引申出了第三个优化三路划分。

之前的我们是主要将区间划分为两段$[begin,key-1]$ 和 $[key+1,end]$ 。 左区间值小于 $key$ 右区间值大于 $key$ 可以称为 两路划分 。

现在我们需要进行三路划分就是将区间分割为左区间小于 $key$ 中间区间等于 $key$ 右区间大于 $key$ 。

其实这个思路更为简单简单讲一下思路

设定一个 $cur=begin+1$$left=begin,right=end,key=a[left]$。

就是将区间分割为左区间小于 $key$ 中间区间等于 $key$ 右区间大于 $key$ 。

给定一个循环循环中如果 $a[cur]<key$ 此刻交换 $cur$ 和 $left$ 指向的元素使 $left++$ $cur++$ 。(如果一开始这个条件就满足则会把 $key$ 逐渐往中间推。)

如果 $a[cur]>key$ 此刻 $right$ 这个位置的值比 $key$ 大也有可能比 $key$ 小。交换 $cur$ 和 $right$ 指向元素后如果 $cur++$ 可能该位置元素就不满足最终区间划分条件所以这里只能 $right--$.

如果 $a[cur]==key$ 那么只需要 $cur++$。

当 $cur>right$ 时$right$ 后的元素都是大于 $key$ 的区间也都调整好了这时候循环也就停止了。

实际上这一过程就像把和 $key$ 相等的值往中间推把比 $key$小的值往左边甩把比 $key$ 大的值往右边甩最后等于 $key$ 的就在中间。

最后分割成的区间就是 $[begin,left-1],[left,right],[right+1,end]$这时等于 $key$ 的区间不用递归只需要递归排序左右区间即可。

如果不太理解可以画一下草图这边博主就不带着画了。

这一过程也是挺简单的我们直接看代码

// 三路划分 处理重复数据量大的情况处理完中间区间就是 22222222222
void QuickSortT(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	
    // 三数取中一下
	int mid = GetIndexMid(a, begin, end);
	Swap(&a[mid], &a[begin]);

	int left = begin, right = end;
	int cur = begin + 1;
	int key = a[left];

	// 跟 key 相等的值往后推
	// 比 key 小的甩到左边
	// 比 key 大的甩到右边
	// 和 key 相等的就在中间
	while (cur <= right)
	{
		if (a[cur] < key)
		{
			Swap(&a[cur], &a[left]);
			left++;
			cur++;
		}
		else if (a[cur] > key) //	
		{
			// r 这个位置有可能比 Key 大也有可能比 key 小
			// 所以 cur 不 ++ 
			// 如果 cur 比 key 大之后还是得换回去处理
			Swap(&a[cur], &a[right]);
			right--;
		}
		else
		{
			cur++;
		}
	}

	// 区间被划分为 [begin, left - 1] [left, right] [right + 1, end]
	QuickSortT(a, begin, left - 1);
	QuickSortT(a, right + 1, end);
}

6.7 快排递归版本完整代码

这边调用的 partion 我们用 前后指针 的(代码少些doge)

int GetIndexMid(int* a, int begin, int end)
{
	int mid = (begin + end) >> 1;

	if (a[begin] < a[mid])
	{
		if (a[mid] < a[end])
		{
			return mid;
		}
		else if (a[begin] > a[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
	else // a[begin] >= a[mid]
	{
		if (a[mid] > a[end])
		{
			return mid;
		}
		else if (a[end] > a[begin])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
}
    
int partion3(int* a, int begin, int end)
{
    // 三数取中
	int mid = GetIndexMid(a, begin, end);
	Swap(&a[begin], &a[mid]);

	int prev = begin;
	int cur = begin + 1;
	int key = begin;

	while (cur <= end)
	{
		// 找到比 key 小的值时跟 ++prev 位置交换
		// 小的往前翻大的往后翻

		// 重复数据不会交换
		if (a[cur] < a[key] && ++prev != cur)
			Swap(&a[cur], &a[prev]);

		// 重复数据会交换
		/*if (a[cur] < a[key])
			Swap(&a[++prev], &a[cur]);*/

			// cur 必定会走一步
		cur++;
	}

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

	//return prev;

	key = prev;

	return key;
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	// 小于一定数目使用 直接插入排序
	if ((end - begin + 1) < 15)
	{
		InsertSort(a + begin, end - begin + 1);
	}
	else
	{
		int key = partion3(a, begin, end);
		// 递归左右区间
		QuickSort(a, begin, key - 1);
		QuickSort(a, key + 1, end);
	}
}

6.8 快排非递归版本

其实快排不仅能用递归还是可以使用非递归的非递归的好处就是不需要多次递归开辟多层函数栈帧在空间消耗上略有优势。

快排的非递归需要借助数据结构 - 栈 来完成。

快排递归的过程就相当于对每一段区间进行处理那么非递归我们可以用两个变量来模拟各个区间。

接下来我们开始展开思路

一开始我们将 $begin$ 和 $end$ 分别入栈。给定一个循环如果栈不为空就继续循环。

由于栈是后进先出所以先用 $right$ 接收 $end$ 右区间再用 $left$ 接收左区间在接收完之后将这两个元素分别出栈。

得到了区间之后就对区间进行单趟排序(可以调用上面的 $hoare$ 等)用 $key$ 接收分隔点。

我们再想想处理完一次完整区间后下一次要如何处理

先处理左区间 $[left,key-1]$ 再处理 $[key+1,right]$ 。由于栈先进后出所以要先入右区间在入左区间。

每次循环只会取出两个值那么就是一小段区间在取出左区间后会先处理左区间然后不断分割小区间每次取出两个值一直对栈顶上的两个元素的区间进行处理这样就模拟除了快排的过程。

优化思路

如果区间内只有 $1$ 个元素就无需处理了所以可以加个条件判断一下举个例子对于右区间来说 $key$ 是分割点 $key+1$ 则是右区间的起始位置如果 $key+1<right$ 那么说明区间中不止一个元素这种情况就入栈处理。类比左边也是一样的道理。

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

	// 压栈
	StackPush(&st, begin);
	StackPush(&st, end);

	while (!StackEmpty(&st))
	{
		// 后进先出先出 right
		int right = StackTop(&st);
		StackPop(&st);

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

		// 先取左区间后取右区间
		// 所以先入右区间再入左区间

		int key = partion3(a, left , right);
		// 如果区间内只有1个元素则无需入栈
		if (key + 1 < right)
		{
			StackPush(&st, key + 1);
			StackPush(&st, right);
		}

		if (left < key - 1)
		{
			StackPush(&st, left);
			StackPush(&st, key - 1);
		}
	}

	StackDestroy(&st);
}

6.9 时空复杂度

对于快排的时间复杂度本来是不太稳定的因为处理有序序列或者序列中元素相同的情况下可能会造成 $O(N^2)$ 的时间复杂度。

但是当我们 三数取中 或者 三路划分 后时间复杂度就相对稳定了。

加上这两个功能之后如果画出每层的元素情况就像下图一样像一棵完全二叉树。

由于每次每一块都是被二分一共 $N$ 个节点所以这边大约就是 $logN$ 层。

样图

那么对于递归的版本就需要开 $logN$ 层栈帧对于非递归的版本原理和递归类似也认为处理 $logN$ 次。

每次递归/处理中时间复杂度为 $O(N)$ 。所以快排的时间复杂度为 $O(N\times logN)$ 。

而对于时间复杂度也因为优化的原因几乎不会出现极端情况我们认为最佳情况就是像二叉树一样最多开辟 $logN$ 层栈帧根据递归版本根据空间复杂度的计算公式$递归深度\times 每次递归中额外空间消耗$每次递归消耗空间为 $O(1)$ 一共 $logN$ 层所以空间复杂度为 $O(logN)$ 。对于非递归的也是一个道理推一下就明白了~

7、归并排序⭐️

7.1 算法思想

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

如果说快排是前序那么归并恰巧就是它的对立面归并排序相当于是二叉树的后序遍历我们看一张图

归并排序是逐个分解为一个个小区间直到不能分割为止然后一步步 归并起来 逐层返回。

而这一过程需要借助一个辅助数组 tmp 来完成归并过程。

对于归并的详细过程可以参考下图

7.2 归并递归版本

学习过之前我们算法笔记的同学们相信已经对归并有一些了解了兼顾没怎么了解过的同学我在这边简单梳理一下思路

对于归并排序来说首先开辟一个辅助数组 $tmp$ 。我们每一次取一个中间点 $mid$ 。

然后按照后序遍历的方式分别递归左右区间$[begin,mid]$ $[mid+1,end]$ 一直递归到底部递归的返回条件为 $begin>=end$ 。

然后开始归并设定相关变量然后将两区间内对应元素由小到大放置到 $tmp$ 数组对应位置处。

如果放置过程结束一个数组没有放置完则需要在循环结束后将数组的数据全部倒入 tmp 数组中。

在上面的过程完毕之后再把 $tmp$ 数组中的数据拷贝回原数组。

最终递归逐层返回后就完成了归并过程。

过程不难注意点我也都在注释部分标注了

void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin >= end)
	{
		return;
	}
	
	int mid = (begin + end) >> 1;
	
    // 递归到底部
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);

	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	
	/*
	* 第一种拷贝回原数组的方式 - memset
	* 此种做法 cnt 从 begin 开始
	* memset 从 begin 位置开始一共拷贝 end - begin + 1 个元素
	* 和下面做法道理相同
	*/
	// int cnt = begin;
	
	/*
	* 第二种拷贝回原数组的方式 - 循环拷贝
	* 此种做法 cnt 从 0 开始
	* 开始拷贝的位置从 begin 开始
	* cnt 最终的长度就是 [begin, end] 之间的长度
	* 没问题
	*/
	int cnt = 0; 

	while (begin1 <= end1 && begin2 <= end2)
	{
		// 保持稳定性
		if (a[begin1] <= a[begin2])
		{
			tmp[cnt++] = a[begin1++];
		}
		else
		{
			tmp[cnt++] = a[begin2++];
		}
	}

	while (begin1 <= end1) tmp[cnt++] = a[begin1++];
	while (begin2 <= end2) tmp[cnt++] = a[begin2++];
	// 方法1
	// memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
	
    // 方法2
    for (int i = begin, j = 0; i <= end; i++, j++)
	{
		a[i] = tmp[j];
	}
}

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("mallol fail");
		return;
	}

	_MergeSort(a, 0, n - 1, tmp);
}

7.3 归并排序非递归版本

归并排序的非递归版本在这一块是一个难点因为这个本身就不容易想到。

我们先想一下对于归并排序来说能不能借助辅助数据结构实现

如果用栈那是不太行的。因为归并是一种类似二叉树后序遍历的排序当将区间入栈后把区间拿出来处理之后要继续分割时一段区间可能就不见了所以借助辅助数据结构时不太行的。

所以我们可以不借助数据结构用一种相对简单的方法完成。

我们可以设定一个 $rangeN$ 控制我们的区间大小$rangeN$ 就是归并时每组的数据个数。由于我们是类似二叉树后序遍历的方式所以我们一开始的归并实际上就是 $rangeN$ 为 $1$ 情况。

如下图

通过每次改变 $rangeN$ 实际上也就是改变了区间大小就模拟除了归并递归到底从小区间合并逐渐到大区间合并的过程。所以我们就让 $rangeN$ 每次 $\times 2$ 这样子就是归并每次扩大区间的过程。

但是上面的方法只能解决数组长度恰巧被整除的情况对于无法被整除的情况可能就会造成越界。

比如 $n=13$ 。在 $rangeN=4$ 时最后一段区间 $[13,16]$ 越界所以这里是需要做出一下调整的。

我们设置四个点 $begin1=i,end1=i+rangeN-1,begin2=i+rangeN,end2=i+2\ast rangeN-1$ 四个点来规定两段区间。

列举一下这四个点的越界情况我们可以分为三种情况

1. $end1,begin2,end2$ 越界

2. $begin2,end2$ 越界

3. $end2$ 越界

以上就是三种越界情况我们需要分别处理

处理方式分为 修正区间 和 不修正区间

修正区间

第一种越界情况实际上就是 $end1\ge n$ 那么这种情况修正区间的话这时将 $end1=n-1$ 之后将没有越界的部分拷贝到 $tmp$ 数组中然后将 $[begin2,end2]$ 修正为一个不存在的区间。

第二种越界情况就是 $begin2\ge n$ 这种情况下直接将 $[begin2,end2]$ 修正为不存在的区间即可。

第三种越界情况就是 $end2\ge n$这种情况将 $end2=n-1$ 让两端区间正常归并。

这种情况可以边归并边拷贝也可以一组归并完了拷贝。

不修正区间

第一种越界情况修正区间之后实际上就是拷贝的原数组的数据所以没必要修正 break 掉。

第二种越界情况实际上也是拷贝原数据也可以 break 。

但是第三种越界情况就需要修正一下否则这次归并无法完成之后的归并也都错误了让 $end2=n-1$ 。

这种情况只能边归并边拷贝因为有些区间是未处理的如果贸然进行拷贝会把随机值或者错误数据拷贝进来。

好了到这边归并非递归的思路我们就理完了接下来我把两个版本都写下来

修正区间

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	int rangeN = 1;
	while (rangeN < n)
	{
        // 一组归并的跨距为 2 * rangeN 
		for (int i = 0; i < n; i += 2 * rangeN)
		{
			int begin1 = i, end1 = i + rangeN - 1;
			int begin2 = i + rangeN, end2 = i + 2 * rangeN - 1;
			int j = i;
			// 修正区间
			if (end1 >= n)
			{
				end1 = n - 1;
				// begin2 和 end2 修正为不存在的区间
				begin2 = n;
				end2 = n - 1;
			}
			else if (begin2 >= n)
			{
				begin2 = n;
				end2 = n - 1;
			}		
			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 + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}
		memcpy(a, tmp, sizeof(int) * n);
		rangeN *= 2;
	}
	free(tmp);
	tmp = NULL;
}

不修正区间

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	int rangeN = 1;
	while (rangeN < n)
	{
		for (int i = 0; i < n; i += 2 * rangeN)
		{
			int begin1 = i, end1 = i + rangeN - 1;
			int begin2 = i + rangeN, end2 = i + 2 * rangeN - 1;
			int j = i;
			if (end1 >= n)
			{
				break;
			}
			else if (begin2 >= n)
			{
				break;
			}
			else if (end2 >= n)
			{
				end2 = n - 1;
				//break;
			}
			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));
		}
        // 这里不能外部拷贝因为有些情况是直接 break 出来的tmp 中不是正确数据
        // memcpy(a, tmp, sizeof(int) * n); // 会把错误数据拷入
		rangeN *= 2;
	}
	free(tmp);
	tmp = NULL;
}

7.4 时空复杂度

对于归并递归版本每次都是区间二分然后开始递归的。所以递归层数是严格的 $logN$ 每次递归中时间复杂度为 $O(N)$ 所以总体时间复杂度为 $O(N\times logN)$ 对于非递归$rangeN$ 每次乘 $2$ 每次 $rangeN$ 处理的时间复杂度为 $O(N)$ 时间复杂度也是 $O(N\times logN)$。

对于归并排序的空间复杂度递归和非递归有一些计算上的区别但是结果不影响。

归并排序首先需要一个 $tmp$ 数组空间复杂度为 $O(N)$ 。如果对于递归还会开 $logN$ 层栈帧所以递归版本消耗的总空间大月为 $N+logN$ 当 $N$ 足够大时$logN$ 省略所以为 $O(N)$对于非递归那么就仅仅只有 $tmp$ 的消耗。

所以综上所述归并的空间复杂度为 $O(N)$。

8、计数排序

8.1 算法思想

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

我们先看一下计数排序的动图

计数排序实际上就是将数组中对应数据出现的次数将数据出现次数映射到一个新数组中。在与数据相等值的下标处将这个下标位置的元素自增。每出现一个数字就自增一次。

而平常的映射就是直接在其相等下标位置处理叫做 绝对映射 还有一种映射方式叫 相对映射 。我们先看绝对映射。

绝对映射

所谓绝对映射就是开辟一个辅助数组 $c$ 数组大小为待排序数组的最大元素的大小 $max$ 。

然后遍历数组将数据映射到辅助数组 $c$ 中。

然后根据 $count$ 数组中的元素根据元素对应的下标将下标的值填入 $a$ 数组中如果 $count$ 数组中该位置为 $0$ 则不需要填。

最后 $a$ 数组中的元素就已经被排序好了。

其实讲到这里大家也大约可以看出来 绝对映射 的缺点当最大元素很大或者是出现负数时就无法映射了。因为空间开大了浪费空间并且无法在负数下标自增。所以这就引出了 相对映射 。

相对映射

相对映射就是根据数据之间的相对情况来开辟数组大小并在转换后的相对位置执行映射。

比如有这样一组数据 { 5000 , 5001 , 5500 , 5501 } \{5000, 5001, 5500, 5501\} {5000,5001,5500,5501} 对于这组数据我们开 $5501$ 个空间肯定是浪费的。

我们相对映射的思路就是遍历序列找到序列最大值 $max$ 和最小值 $min$ 然后开辟 $max-min+1$ 个空间让空间尽可能充分利用。

之后映射自增时也使用相对位置这个相对位置就是数组元素减去数组元素的最小值$a[i]-min$ 。

在最后将元素放到原数组中时也需要将数组下标加上最小值$i+min$ 放回去就可以。

通过相对映射对于元素有负数和空间浪费的情况都可以解决。ps元素有负数的情况无需特殊处理因为相对映射的原因这些步骤都可以正确进行不信可以试验一下)。

8.2 代码实现

接下来就使用相对映射的思路写出代码

// 计数排序 正负数都可以排
void CountSort(int* a, int n)
{
	// 1. 找最小值和最大值
	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];
		}
	}

	// 2. 根据差值构建 count 数组
	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int) * range);
	if (count == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
    // 初始化
	memset(count, 0, sizeof(int) * range);

	// 3. 将值映射到count数组中
	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++; // 映射到相对位置
	}

	int cnt = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			a[cnt++] = i + min;
		}
	}
}

8.3 时空复杂度

计数排序的时间复杂度其实是由 $range$ 和 $N$ 的关系来衡量的当我们不确定 $range$ 和 $N$ 的大小时我们可以认为 计数排序的时间复杂度为 $O(max(N,range))$ 。取较大的一个。

而空间复杂度则是 $O(range)$。

实际上通过时空复杂度上看我们发现计数排序在数据集中的情况下是非常厉害的能达到几乎 $O(N)$ 的时间复杂度并且空间复杂度也不会太大。但是对于范围分散跨度大的序列就不适合不仅时间没啥优势空间占比也是个大问题。所以计数排序的适用范围是有限的。

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

这里我们就用两张图概括

这里提一下排序的稳定性

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

稳定性是排序算法一种额外的优点。如果一种排序可以通过某种措施达到数据相对次序不变的效果则称该排序是稳定的。

五、排序性能测试框架

void TestOP()
{
	srand(time(0));
	const int N = 10000000;

	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	int* a7 = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
		a7[i] = a1[i];
	}

	// clock 获取程序运行到这块的时间
	// end1 - begin1 = 排序时间
	// 获取的是毫秒
	// 时间过小时计算不出来
	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();

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

	int begin3 = clock();
	SelectSort(a3, N);
	int end3 = clock();

	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();

	int begin5 = clock();
	QuickSortT(a5, 0, N - 1);
	int end5 = clock();

	int begin6 = clock();
	BubbleSort(a6, N);
	int end6 = clock();

	int begin7 = clock();
	MergeSort(a7, N);
	MergeSortNonR(a7, N);
	int end7 = clock();

	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("SelectSort:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
	printf("QuickSort:%d\n", end5 - begin5);
	printf("BubbleSort:%d\n", end6 - begin6);
	printf("MergeSort:%d\n", end7 - begin7);

	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
	free(a7);
}

六、结语

到这里本篇博客就到此结束了对于数据结构的学习我们也就暂时告一段落了。

接下来 $anduin$ 更新的内容大多就是 $C++$ 和算法笔记了。

对于这篇文章博主个人觉得还是不错的希望你们阅读完之后可以有所收获

如果小伙伴们需要源码的话可以到我的 $gitee$ 打包下载源码八大排序

我们下期见~