【手撕数据结构】八大排序神功（上）

冒泡排序【有点拉胯】

动图演示:

思路解析

• 所谓冒泡，就是像泡泡一样从水底冒泡到水面，这个冒泡过程就是比较，已经冒泡到水面的数据就不用再进行比较.，也就是说把第一个元素与后面的元素比较，如果说排升序，第一个元素比后面的元素大就交换位置，然后再与后面的元素进行比较，比较完后，此时我们就冒泡到了水面，所需冒泡的元素就少了一个，下一次冒泡的时候，就应该少排序一个。.

单趟算法图解

代码详解+性能优化

• 先看内部循环.

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

• 这里n - i 就是我们每一趟循环冒泡都会排好一个最大的数据(升序)，那么那个数据就不需要再进行下一次的循环冒泡中
• -1则是为了防止数组下标越界，设 n = 10,第一次 j < 9, 那么j最大下标是8,此时 j + 1最大就是9 了。

我们再来看外部循环:

for (int i = 0; i < n - 1 ; i++)

• i < n - 1是因为，设n = 10, i < 9,最大取到8,此时内部循环 j < n - i -1最后一趟就是 j < 1,也就是最后第一个元素0(j)与第二个元素(j+1)的比较冒泡。
• 下面第i趟冒泡排序可以参考

• 那这样的情况我们能不能优化一下呢？
  
• 可以看到，我们或许不需要一定把n趟排序循环完，数组才有序，可能是n/2趟，n/4趟,n-2,n-3趟等数组就有序了。
• 这种我们可以使用一个标志变量，如果单趟冒泡排序的过程中发生了交换，也就是进了if条件说明数组还没有序需要交换，那么把标志变量改变，如果进行单趟冒泡排序后，标志变量没有改变，说明数组已经有序，这时候就可以直接跳出外层循环。

/*冒泡排序*/
void BubbleSort(int* a, int n)
{//[0,n - 1)for (int i = 0; i < n - 1; ++i){int changed = 0;for (int j = 0; j < n - 1 - i; ++j){if (a[j] > a[j + 1]){swap(&a[j], &a[j + 1]);changed = 1;}}if (changed == 0)break;PrintArray(a, n);}	//[1,n)//for (int i = 1; i < n; ++i)//{//	for (int j = 0; j < n - i; ++j)//	{//		if (a[j] > a[j + 1])//			swap(&a[j], &a[j + 1]);//	}//}
}

复杂度分析

【时间复杂度】：O(N2)
【空间复杂度】：O(1)

• 我们通过上面的讲解了其运行过程，就是每一个数与其后的n - i个数进行比较，若是符合条件则进行交换，不算我们优化之后的，算法运行的次数就是 (N - 1) + (N - 2) + (N - 3) + … + 2 + 1，结合起来运算就是一个等差数列，那么其时间复杂度显而易见就是O(N2)
• 对于最后的情况就是o(n),也就是数组已经有序的情况下，我们做了标志变量，如果第一次冒泡排序没有交换，就可以直接结束循环，此时我们只执行了n次。

直接插入排序【还阔以】

动图演示

思路解析

• 可以看到，直接插入排序就是把有序区间的后的第一个数据与有序区间的数据进行依次比较，这里设升序，如果说比有序区间中的某个数据小，就让这个数据之后的有序区间的数据整体往后面移动，然后最后把这个数据插入到有序区间中比他大的那个数据的位置。
  
• 实际中我们玩扑克牌时，就用了使用到了插入排序的思想。设想你发到一张牌为7，现在想将其放入你刚才已经整理好了牌堆中，这个牌堆就是有序序列，这张牌就是待插入的数据。通过生活中的场景来看，是不是更加形象一点呢😄
  

代码分析与讲解

• 理解算法后，也不一定会写程序。也就是脑子会了，手还不会。但是我们应该知道，写程序不是一下把整个算法就写出来了，我们应该从简单到复杂，我们先不写整趟排序，就考虑单趟排序的问题。
• 首先单趟的逻辑，就是我们需要把有序区间后的一个数据插入到有序区间中，不妨设有序区间最后一个数据为end，之后的数据是end + 1，然后我们开始比较end和end+1，如果说end+1小于end，那么end这个数据往后移动到end + 1这个位置，然后end - - 开始有序区间中的另一个数据和end + 1进行比较
• 但是注意的是，随着有序区间的扩大，我们end + 1需要比较的数据就越多，此时我们需要把这段逻辑放在一个循环里面，结束条件是什么呢？end >= 0, 等于0,是因为我们最坏可能比较到第一个元素也比end + 1小.
• 若是在中途比较的过程中发现有比待插入数据还要小或者相等的数，就停止比较，跳出这个循环。因为随着有序区间中数的后移，end后一定会空出一个位置，此时呢执行a[end + 1] = tmp;就可以将这个待插入数据完整地放入有序区中并且使这个有序区依旧保持有序

int end;
int tmp = a[end + 1];		//将end后的位置先行保存起来
while (end >= 0)
{if (tmp < a[end]){a[end + 1] = a[end];		//比待插值来得大的均往后移动end--;		//end前移}else{break;		//若是发现有相同的或者小于带插值的元素，则停下，跳出循环}
}
a[end + 1] = tmp;		//将end + 1的位置放入保存的tmp值

• 接下来我们看外层循环

for (int i = 0; i < n - 1; ++i)
{int end = i;//单趟插入逻辑...
}

• 或许有人疑问为什么i < n - 1 ，而不是 i < n，这里主要是防止数组下标越界，设n = 10 , 如果 i < n
  n最大为9，下面的end + 1就会访问到a[10],此时会越界，所以是 i < n - 1

下面是整体代码:

/*直接插入排序*/
void InsertSort(int* a, int n)
{//不可以< n，否则最后的位置落在n-1，tmp访问end[n]会造成越界for (int i = 0; i < n - 1; ++i){int end = i;int tmp = a[end + 1];		//将end后的位置先行保存起来while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];		//比待插值来得大的均往后移动end--;		//end前移}else{break;		//若是发现有相同的或者小于带插值的元素，则停下，跳出循环}}a[end + 1] = tmp;		//将end + 1的位置放入保存的tmp值}}

复杂度分析

【时间复杂度】：O(N^2)
【空间复杂度】：O(1)

• 最好的情况就是o(n)，也就是数组本身就有序的情况:1 2 3 4 5 6 7 8 9 10,此时只需要遍历一次数组而已。
• 最坏的情况就是o(n^2),这里设要排升序，数组为降序:10 9 8 7 6 5 4 3 2 1,此时就需要全部都往后面移动一位。

希尔排序【有点强】

动图演示

思路讲解

• 希尔排序就是直接插入排序的优化，我们在上面分析直接插入排序的时间复杂度时，最差的时候就是降序的时候，那么现在对降序的数组进行分组，对每组进行直接插入排序，那么每组的数据就是比原先没分组的数据少，这时候我们直接插入排序的时候，交换的次数变少了，而且保证了整个数组基本有序。
• 对原本的数据进行一个分组，对每组使用直接插入排序排序。增量【gap】随着排序次数的增加而减少
• 当gap==1时，整个序列恰好被分为一组，就对预排序后的数组最后一次进行直接插入排序。

排序过程总览

• 我们看到这里有10个数, gap = 10 / 2 , gap = 5,也就是每个数字之间的间隔为5。然后把他们分组，每组的元素间隔5个元素，若是前者比后者大，则交换。
  
  
• 以上就是三次排序的过程，当gap == 1的时候，也就是全部数据为一组，即间隔为一，对他们进行直接插入排序

代码分析讲解

• 还是一样，我们从简单到复杂，先分析单趟排序的过程。
• 对于希尔排序，我上面说过其实他就是直接插入排序的优化，只不过多了一个分组来排的逻辑。而这个分组有那些元素，就是通过gap 间隔增量，来控制。我们开始设 n = 10, gap = n / 3 ,也就是间隔3个元素的数据为一组
• 分了组就简单了，我们就对每个分组的元素进行直接插入排序，那么怎么获得每个分组的元素了，因为他们是间隔gap 个元素为一组，现在设end为分组第一个元素，所以就是end + gap 个元素
• 注意:在实现后移的过程中也是移动gap步，对于end也是同理
• 注意:那在跳出循环之后的tmp也是要放在a[end + gap]的地方

int gap = 3;
int end;
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;

• 说完了单趟，我们就要用循环来控制每一趟排序了。
• way1:第一种方法就是我们把每个分组的元素以组为单位，把每一组的数据排好，再排下一组，此时我们需要排gap组.
  
• 这种方法不推荐，都有4层循环了。
• way2:把每一组的第一个元素排完，然后排下一组
• 
• 这种就只有3层循环，i++控制每一组的第一个元素，和第2个元素的排序

下面为2中方法图解:

• 再说说，为什么gap = gap / 3,gap = gap / 5行不行，gap / 5当然可以，但是他们每组元素的间隔太远了，我们进行预排序的目的是把数组接近有序，这样在最后一次直接插入排序的时候，我们需要往后移动的次数就少了。

如图这样的预排序之后：

• 那有人说，那我直接gap / 2,2个间隔为一组，这样是缩短了距离，但是组数变多了也不好，所以我们这种选择gap / 3.
• 但是在gap / 3之后可能在最后无法使【gap = 1】，比如gap = 6的时候，那此时的话就需要在最后加上一个1使得最后一次缩小gap增量的时候可以使其到达1
• gap > 1就是因为，设 gap = 10, 最后会除到1，此时1/3 + 1会永远等于1，所以gap > 1.
• i < n - gap ,也是为了防止数组越界，因为我们是分组进行排序，每次都是与end + gap 下班班元素进行比较

整体代码演示:

/*希尔排序*/
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1)			{/** gap > 1 —— 预排序* gap == 1 —— 直接插入排序*///gap /= 2;gap = gap / 3 + 1;		//保证最后的gap值为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];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

复杂度分析

【时间复杂度】：O(NlogN)
【空间复杂度】：O(1)

• 但这也仅仅似乎根据我们写的代码来看，实际上希尔排序的时间复杂度不是O(NlogN)，而是O(N1.3)
• 大家只能要能够计算出O(NlogN)就行了，如果有读者数学很好的当然也是可以做到😄，然后对于希尔排序时间复杂度最坏是O(N2)，这一点上面也已经写出了，最坏情况就是等差数列的时候，例如5个数要挪动4下，3个数要挪动2下。。。N个数要挪动N - 1下
• 希尔排序比直接插入排序快的原因，就是因为分组预排序让数组接近有序并且比较的数据变少，然后最后一次排序的时候由于数组已经接近有序，那么比较的次数就变少了。
  
• 然后是有关希尔排序的空间复杂度，这一块还是和插入排序一样，只是在内部定义了一些变量，并没有去申请一些额外的空间，因此空间复杂度为O(1)

堆排序【太有石粒啦】

动图演示

堆的概念与结构

如果有一个关键码的集合K = { k0， k1， k2，…，kn-1 }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中。并满足：Ki <= K2i+1 且 Ki <= K2i+2 ( Ki >= K2i+1 且 Ki >= K2i+2 ) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆
【堆的性质】

• 堆中的左右孩子节点总是大于(小根堆)根节点，或者小于(大根堆)根节点
• 堆总是一颗完全二叉树

基本了解堆的概念后，我们来看看琢磨一下什么是大根堆和小根堆

• 从上图可以看出，对于【堆】而言，其实就是一种完全二叉树，但是呢，它又在完全二叉树的基础上再进一步形成一个区分，也就是分为【大根堆】和【小根堆】
• 但是这只是我们自己想象出来的逻辑结构，但是在内存中的物理结构实际上就是数组存储的，既然是数组我们就一定可以通过下标来访问其中的各个元素。
• 这其实也得出了一个结论，在逻辑结构中我们可以看出其实每个根节点都要左右孩子节点，那么在物理结构中我们想要访问这些节点也可以吗？在二叉树和堆中已经讲过。

【lchild = parent * 2 + 1】 左孩子
【rchild = parent * 2 + 2】 右孩子
【parent = (child - 1) / 2】

向下调整算法【核心所在】

算法图解：(这里假设我们建的大堆)

• 对于向下调整算法，必须满足的前提就是需要调整的根节点的左右子树是大根堆，这样保证调整后整棵树也是一个大根堆。
• 对于上面的原理就是，如果我们需要保证调整完后整颗二叉树是一个大堆，根节点18需要找他的左右孩子节点谁更大与其交换，保证交换后对于18,49,34这颗二叉树是一个大根堆，然后从把交换的孩子节点作为新的子树根节点依次循环以上步骤。直到这个【18】的孩子结点到达【n - 1】就不作交换了，因为【n - 1】就相当于是位于数组下标的最后一个值

代码考究精析

• 首先对于向下调整算法我们需要调整堆，那么前面堆的结构说了，其实物理结构是一个数组(也就是顺序二叉树)，那么我们第一个参数就传数组名，然后我们要调整他的根节点，根节点与左右孩子节点比较交换，所以我们把父节点传过去通过，【lchild = parent * 2 + 1】 左孩子
  【rchild = parent * 2 + 2】 右孩子求其左右孩子节点。还有就是传数组的长度，这在循环的结束条件要用到。

void Adjust_Down(int* a, int n, int parent)

• 你可以通过每次计算 左右孩子节点来比较谁大。但是有点冗余
• 我们这里假设左孩子为最大节点，如果他比右孩子节点小，那么左孩子节点下标+1，因为数组数连续存储的，+1就是右孩子节点。if判断里还加了一个【child + 1 < n】，这个的话其实就是进行一个右孩子的越界访问判断，因为我们是在进行一个不断向下调整的过程，因此肯定会到达倒数第二层，此时它的左孩子可能是存在的，但若是它的右孩子不存在了，那么在后面去访问这个【child + 1】就会变成越界访问⚠，是一个非法操作

		//判断是否存在右孩子，防止越界访问
if (child + 1 < n && a[child + 1] > a[child])
{++child;		//若右孩子来的大，则转化为右孩子
}

• 然后是循环内部的逻辑，和【向上调整算法】一样，就是一个比较和迭代更新的过程

if (a[child] > a[parent])
{swap(&a[child], &a[parent]);parent = child;					//更新父亲child = parent * 2 + 1;			//更新孩子
}
else {break;
}

整体代码演示：

/*向下调整算法*/
void Adjust_Down(int* a, int n, int parent)
{int child = parent * 2 + 1;		//默认左孩子来得大while (child < n){		//判断是否存在右孩子，防止越界访问if (child + 1 < n && a[child + 1] > a[child]){++child;		//若右孩子来的大，则转化为右孩子}if (a[child] > a[parent]){swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else {break;}}
}

升序建大堆 or 小堆?

• 给个答案就是升序我们应该建大堆，降序我们应该建小堆。
• 为什么升序建大堆？

我们建堆就是为了排序数组，既然是升序，就是小的在前面，大的在后面。我们建大堆可以保证，堆顶一是最大的，这时候我们只需要把堆顶与数组最后一个元素交换，就可以保证数组最后一个元素是最大的。

• 有人说了，那我用建小堆也能保证数组第一个元素是最小的。
  看图：
  
• 那有n个数排序，我们就要建n个堆，建堆一次时间复杂度为o(n),建n个堆就是o(n^2)
• 而建大堆，我们只需要把堆顶和数组最后一个元素进行交换，然后对堆进行向下调整即可
• 可能有人疑问，那建小堆的时候为什么不直接向下调整，我前面说过向下调整前提是需要保证其左右子树是小堆的，但是上图父亲孩子节点打乱后就不是小堆了。

//建立大根堆（倒数第一个非叶子结点）
for (int i = ((n - 1) - 1) / 2 ; i >= 0; --i)
{Adjust_Down(a, n, i);
}

如何进一步实现排序

其实在前面讲向下调整算法的过程中已经透露出排序的过程了

• 就是建大堆后，把堆顶元素和数组最后一个元素进行交换，达到数组最后一个元素是最大的目的。然后进行向下调整恢复大堆的性质(堆顶为最大元素)，再进行交换，知道交换到堆顶结束。
• 注意：每次交换后，被交换到后面的数据不参与下次堆的向下调整。

代码如下:

/*堆排序*/
void HeapSort(int* a, int n)
{//建立大根堆（倒数第一个非叶子结点）for (int i = ((n - 1) - 1) / 2 ; i >= 0; --i){Adjust_Down(a, n, i);}int end = n - 1;while (end > 0){swap(&a[0], &a[end]);		//首先交换堆顶结点和堆底末梢结点Adjust_Down(a, end, 0);		//一一向前调整end--;}
}

整体代码：

/*交换*/
void swap(int* x, int* y)
{int t = *x;*x = *y;*y = t;
}

/*向下调整算法*/
void Adjust_Down(int* a, int n, int parent)
{int child = parent * 2 + 1;		//默认左孩子来得大while (child < n){		//判断是否存在右孩子，防止越界访问if (child + 1 < n && a[child + 1] > a[child]){++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){Adjust_Down(a, n, i);}int end = n - 1;while (end > 0){swap(&a[0], &a[end]);		//首先交换堆顶结点和堆底末梢结点Adjust_Down(a, end, 0);		//一一向前调整end--;}
}

复杂度分析

【时间复杂度】：O(NlogN)
【空间复杂度】：O(1)

• 在建堆这块的时间复杂度是o(N),在排序一个数据的时候是logn，n个数据就是nlongn ,n+nlogn为nlogn
• 空间复杂度就是o(1),并没有在堆排序里面重新申请空间。