实现八大排序算法

八大常用排序实现地址：https://gitee.com/CCTVYI/Algorithm/tree/master/Sort

一、背景

1.稳定性
两个相等的数A和B，倘若在未排序前，A在B的前面，排序后，A排到了B的后面，那么称这个排序算法是不稳定的。

未排序：2，3，A，7，B，8（假设A=B=5）
排序后：2，3，B，A，7，8
//这个算法是不稳定的。

**稳定的：**相等的元素的顺序不会改变。
2.排序种类
内部排序：数据元素放在内存中排序。
外部排序：数据元素太多不能同时放在内存中，需要借助内/外存之间移动数据。以达到排序整个文件的目的。

3.表格

时间复杂度
**1）**冒泡、选择、直接 排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O（n2）O（n2）（一遍找元素O(n)O(n)，一遍找位置O(n)O(n)）
**2）**快速、归并、希尔、堆基于二分思想，log以2为底，平均时间复杂度为O(nlogn)O(nlogn)（一遍找元素O(n)O(n)，一遍找位置O(logn)O(logn)）

二、插入排序

1.直接插入排序
1）背景
类似于抓扑克牌，是最简单的一种排序，将一个记录插入到已排好序的有序表中，从而得到一个新的，记录数增一的有序表。其时间复杂度为O（n2）。空间复杂度O（1）。
2）应用场景
元素较少，一般低于8个，可以使用二分查找进行改进直接插入排序算法。
优点：插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
缺点：但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
3）算法思路
先将第一个数和第二个数（Key）比较，Key小，将第一个数搬到后面。然后在寻找位置将其插入。

2.希尔排序
1）背景
是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定的排序算法。其时间复杂度为O（n2）。空间复杂度O（1）。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。
2）应用场景
不需要大量的辅助空间，希尔排序没有快速排序算法快 O(n(logn))，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。但是比O( )复杂度的算法快得多。并且希尔排序非常容易实现，算法代码短而简单。

3）算法思路
①先将序列进行分组，单独分出的组进行直接插入排序，直到分组只剩一个为止。
②gap=gap/3-1，这种步长在实验中效率是最高的，每进行一次直接插入排序，小的基本在前，大的基本在后。
三、选择排序

1.选择排序
1）背景
选择排序是不稳定的算法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换）。
对于数据较多的数组，循环的次数将与数组中元素的个数一致，因此，在对于这种数组进行排序时，将十分的浪费时间。
2）算法思路
第一步：先将最后一个元素默认看成最大的元素。
第二步：从前向后全部遍历，使用变量max记录最大数的下标。
第三步：最大元素和最后一个元素进行交换。

2.堆排序
1）背景
堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值
2）算法思路
第一步：先找到倒数第一个非叶子结点，然后自顶向下进行调整。
第二步：非叶子节点–，在进行第一步，直到非叶子结点走到根结点。
第三步：开始进行堆排序，调整后，最大元素到了堆顶，然后交换首元素和最后一个元素。然后继续调整。
注：如何调整？
自顶向下调整，默认设置左孩子大于右孩子。如果右比左大，则认为右是大孩子，然后父亲与孩子进行比较，如果孩子比父母大，则交换。并更新父亲和孩子节点的下标。

四、交换排序

1.冒泡排序（Bubble_Sort）
第一个数和第二个数进行比较，将大的数放在后面，然后第二个数和第三个数进行比较，也将大的数放在后面，那么这样一趟下来，将最大的元素放在了最后面。
第二趟的比较比第一趟少了一次，因为最后的元素已经是最大的了，它没有必要再排序了。
第三趟的比较比第二趟少了二次…
注：
可以添加标志位，经历第一趟，如果交换了元素，就改变标志位，否则不改变。倘若标志位没有改变，那么可以直接退出。

2.快速排序
快排是冒泡排序的改进。是一种不稳定的算法。
1）应用场景
待排序的关键字是随机分布时，快速排序的平均时间最短；
2）快排算法思路
a.比较前的准备：i=第一个元素下标，j=最后一个数的下标，k=第一个元素值。
b.第一遍比较：比较右–>左–>右–>左–>右…，直到（i==j）停下来，此时比K大的和比K小的数分到K的两边。
c.后续比较，利用递归，对k两边的数据，再分组分别进行上述的过程，直到不能再分组为止

注：
如果i和j没有碰头的话，就递加i找大的，还没有，就再递减j找小的，如此反复，不断循环。注意判断和寻找是同时进行的。

五、归并排序

1.归并排序
1）算法是采用分治法。将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列段间有序。
2）若将两个有序表合并成一个有序表，称为二路归并。
3）是一种稳定的排序算法。速度仅此于快速排序。但比较占内存。
2.应用场景
一般用于对总体无序，但是各子项相对有序的数列。
用于多个有序的数据文件归并成一个有序的数据文件
3.归并算法思路
1）重新开辟空间。归并排序后进行释放。
2）递归划分成一个一个子列，递归跳出条件，子列元素小于等于一退出。先划分左，在划分右。
3）归并操作。对于两个有序子列，先将两个子列首元素最小的，放入新开辟的空间中,然后在向后寻找。当其中一个子列无元素后，检测另一个子列是否还有元素，直接追加到新空间后面。并将新空间里的数据移入原空间。