【数据结构初阶】九、五种比较排序的讲解和实现（直接插入 \ 希尔 \ 直接选择 \ 堆 \ 冒泡 -- C语言）
=========================================================================
相关代码gitee自取：
C语言学习日记: 加油努力 (gitee.com)
=========================================================================
接上期：
【数据结构初阶】八、非线性表里的二叉树（二叉树的实现 -- C语言链式结构）-CSDN博客
=========================================================================
排序
排序的概念
所谓排序，就是使一串记录，
按照其中的某个或某些关键字的大小，递增或递减排列起来的操作
稳定性
假定在待排序的记录序列中，存在多个具有相同关键字的记录，
若经过排序，这些记录的相对次序保持不变，
即在原序列中 r [ i ] = r [ j ] , 且 r [ i ] 在 r [ j ] 之前，
而在排序后的序列中，r [ i ] 仍在 r [ j ] 之前，
则称这种排序算法是稳定的；否则称为不稳定的
内部排序（内排序）
数据元素全部放在内存中的排序（在内存中进行排序）
属于内排序的排序算法：
- 插入排序：
直接插入排序 、希尔排序 - 选择排序：
直接选择排序 、堆排序 - 交换排序：
冒泡排序 、快速排序 - 并归排序（即属于内排序又属于外排序）
外部排序（外排序）
数据元素太多，不能同时放在内存中，
根据排序过程的要求不能在内外存之间移动数据的排序，
即在磁盘中（“顺序写顺序读”）进行排序
属于外排序的排序算法：
- 并归排序（即属于内排序又属于外排序）
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
常见排序算法的实现
（详细解释在图片的注释中，代码分文件放下一标题处）
一、插入排序
插入排序 -- 直接插入排序
直接插入排序是一种简单的插入排序法
该算法基本思想：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，
直到所有的记录插入完为止，得到一个新的有序序列
（想象我们玩扑克牌时，给扑克牌大小排序就用了插入排序的思想）实现思路：
当插入第 i(i>=1) 个元素时，
前面的 array[0]，array[1]，…，array[i-1] 已经排好序，此时用 array[i] 的排序码与 array[i-1]，array[i-2]，… 的排序码顺序进行比较，
找到插入位置后就将 array[i] 插入，原来位置上的元素顺序后移（覆盖）直接插入排序的特性总结：
- 元素越接近有序，直接插入排序算法的时间效率越高 -- 最高可达O(N)
- 该算法时间复杂度：O(N^2) -- 最坏的情况下(逆序)
- 该算法空间复杂度：O(1)
- 该算法稳定性：稳定
---------------------------------------------------------------------------------------------
InsertSort函数 -- 直接插入排序实现函数
- 使用for循环进行循环插入排序，
再设置 “前元素” 和 “后元素”
- for循环中：
使用while循环为“后元素”寻找合适位置，
找到后再将 “后元素” 插入，之后再次进行for循环让下个“后元素”插入合适位置
图示：
该函数执行逻辑图：
对应函数测试：
---------------------------------------------------------------------------------------------
插入排序 -- 希尔排序（缩小增量排序）
希尔排序又称缩小增量法。
该算法基本思想：
先选定一个整数gap值，把待排序文件中所有记录分成gap个组，
所有距离为gap的记录分在同一组内，并对每一组内的记录进行直接插入排序，
然后换个整数gap值再取gap组，重复上述分组和排序的工作，
当 gap=1 时，所有记录在同一组内时已经排好序了
希尔排序的特性总结：
- 希尔排序是对直接插入排序的优化
- 当 gap>1 时都是在进行预排序，目的是让数组更接近于有序，
当 gap==1 时，数组已经接近有序的了，这样再进行直接插入排序就会很快，这样整体而言，可以达到优化的效果
- 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，
因此在一些书中给出的希尔排序的时间复杂度也不固定，
该函数大概的时间复杂度为：O(N^1.3) - 该算法稳定性：不稳定
---------------------------------------------------------------------------------------------
ShellSort函数 -- 希尔排序实现函数
- 核心实现操作还是直接插入排序，
但是在对所有值进行直接插入排序前先进行多次预排序操作，
（预排序也是用直接插入排序完成）
让数组达到尽量有序的状态 - 定义gap值变量，使用while循环控制多次预排序
（当gap==1时，就相当于直接插入排序）
- while循环中内嵌for循环完成“当前gap组”的预排序
- 再内嵌for循环完成“当前gap组”其中一组的预排序
（通过直接插入排序的方式实现）
- 最后再内嵌while循环配合完成直接插入排序
图示：
该函数执行逻辑图：
对应函数测试：
二、选择排序
基本思想：
每一趟排序从待排序的数组元素中分别选择出最小和最大的一个元素，
再分别存放在数组的起始位置和尾部位置，
直到全部待排序的数组元素排序完成选择排序 -- 直接选择排序
该算法基本思想：
在元素集合 array[i] -- array[n-1] 中选择获取当前最小值元素和当前最大值元素，
将当前最小值元素交换后放到当前数组的起始位置，
将当前最大值元素交换后放到当前数组的尾部位置，在剩余的 array[i+1] -- array[n-2] 集合中，重复上述操作，直到集合剩余1个元素
直接选择排序的特性总结：
- 直接选择排序比较好理解，但是效率不高，实际很少使用
- 该算法时间复杂度：O(N^2)
- 该算法空间复杂度：O(1)
- 该算法稳定性：不稳定
---------------------------------------------------------------------------------------------
SelectSort函数 -- 直接选择排序实现函数
- 定义 数组开始(初始)位置下标begin 和 数组尾部(结束)位置下标end 变量，
使用while循环控制多趟直接选择排序
- （在while循环中：完成一趟直接选择排序）
定义 存放当前最小值下标mini 和 存放当前最大值下标maxi 变量，
内嵌for循环，遍历一次当前数组找到当前最大值和当前最小值 - （while循环中for循环外：）
将找到的当前数组最小值放入数组起始（左边）位置，
当前数组最大值放入数组尾部（右边）位置,
完成两值的排序后，调整 begin 和 end 变量，缩小数组范围准备下趟直接选择排序图示：
该函数执行逻辑图：
对应函数测试：
---------------------------------------------------------------------------------------------
选择排序 -- 堆排序
堆是一种完全二叉树，
可以使用堆中的向下调整操作对普通数组进行排序（升序或降序）
堆排序的特性总结：
- 堆排序使用堆进行选择排序，效率就高了很多
- 该算法时间复杂度：O(N*logN)
- 该算法空间复杂度：O(1)
- 该算法稳定性：不稳定
---------------------------------------------------------------------------------------------
堆排序的实现往期博客中已有详细描述：
【数据结构初阶】七、非线性表里的二叉树（堆的实现 -- C语言顺序结构）-CSDN博客
（包含堆排序的 实现函数、图示、对应函数执行逻辑图、函数测试、原代码）
三、交换排序
基本思想：
所谓交换，就是根据序列中两个记录键值的比较结果来交换这两个记录在序列中的位置
交换排序的特点：
将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动
交换排序 -- 冒泡排序
该算法基本思想：
数组中的元素1和元素2进行比较，如果元素1大于元素2，则交换两者位置；
再比较此时的元素2和元素3，如果元素2大于元素3，则交换两者位置；
再比较此时的元素3和元素4……
一趟冒泡排序完成后，就能完成当前数组中最大值的排序（排在尾部），
再进行下一趟冒泡排序前要缩小数组排序范围（排除已经排序好的最大值），这样多趟冒泡排序完成后就能完成数组的排序
冒泡排序的特性总结：
- 冒泡排序是一种非常容易理解的排序
- 该算法时间复杂度：O(N^2)
- 该算法空间复杂度：O(1)
- 该算法稳定性：稳定
---------------------------------------------------------------------------------------------
BubbleSort函数 -- 冒泡排序实现函数
- 定义嵌套for循环完成冒泡排序，
外层for循环控制当前数组范围，数组范围慢慢减小，
减到变成1时排序完成（至少有两个数才能比较） - 内层for循环循环一趟完成当前数组范围内的最值的排序
- 在当前冒泡排序过程中，
设置一个变量exchange记录当前一趟冒泡排序过程中是否有发生元素的交换，一趟冒泡排序后，如果没有任何元素发生交换，
说明目前已经排好序了，那就直接终止之后的冒泡排序
图示：
该函数执行逻辑图：
对应函数测试：
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
对应代码：
Sort.h -- 排序头文件
#pragma once //包含之后所需头文件： #include //打印数组函数： void PrintArray(int* a, int n); //直接插入排序函数： //第一个参数：接收要排序的数组首元素地址（a） //第二个参数：接收该数组的长度（n） void InsertSort(int* a, int n); //希尔排序函数： //第一个参数：接收要排序的数组首元素地址（a） //第二个参数：接收该数组的长度（n） void ShellSort(int* a, int n); //1、预排序：分组排，间隔为gap(间距间隔)分为一组 // 预排序意义： // 让大的数更快的到数组后面，小的数更快的到数组前面， // gap值越大“跳”得越快，但是越不接近有序 // gap值越小“跳”得越慢，但是越接近有序 // 当gap==1时，就相当于直接插入排序 //2、直接插入排序 //冒泡排序函数： //第一个参数：接收要排序的数组首元素地址（a） //第二个参数：接收该数组的长度（n） void BubbleSort(int* a, int n); //直接选择排序函数： //第一个参数：接收要排序的数组首元素地址（a） //第二个参数：接收该数组的长度（n） void SelectSort(int* a, int n);
---------------------------------------------------------------------------------------------
Sort.c -- 排序函数实现文件
#define _CRT_SECURE_NO_WARNINGS 1 //包含排序头文件： #include "Sort.h" //打印数组函数： void PrintArray(int* a, int n) { for (int i = 0; i = 0) //“前面所有元素”：下标 >=0 时就还有 “前元素”， //那“后元素”就需要继续进行比较： { if (tmp 1) { //变化gap值进行多次预排序， //让数组越来越接近有序： gap = gap / 2; //当 gap > 1 时就是预排序 //当 gap == 1 时就是插入排序 //这个for循环控制 “当前gap组” 的排序： //（一组“gap分”组排完再排另一组gap分组） for (int j = 0; j = 0) //“前面所有元素”：下标 >=0 时就还有 “前元素”， //那“后元素”就需要继续进行比较： { if (tmp
- 定义嵌套for循环完成冒泡排序，
- 冒泡排序是一种非常容易理解的排序
- 堆排序使用堆进行选择排序，效率就高了很多
- 定义 数组开始(初始)位置下标begin 和 数组尾部(结束)位置下标end 变量，
- 核心实现操作还是直接插入排序，
- 希尔排序是对直接插入排序的优化
- 使用for循环进行循环插入排序，
- 元素越接近有序，直接插入排序算法的时间效率越高 -- 最高可达O(N)
- 并归排序（即属于内排序又属于外排序）
