排序的分类
内部排序
- 插入排序
- 直接插入排序
- 折半插入排序
- 希尔排序
- 交换排序
- 冒泡排序
- 快速排序
- 选择排序
- 简单选择排序
- 堆排序⭐
- 归并排序
- 基数排序
- 外部排序
插入排序
直接插入排序
在待排序的元素序列基本有序的前提下，直接插入排序是效率最高的排序算法
利用直接插入排序的方法对某一个序列进行有序化时，首先选择一个对比值，假设其已经有序；紧接着再选择一个，和第一个进行对比，把它放到应该放的位置；再选择下一个，和前两个进行对比，把它放在应该放的位置。以此类推，直到所有的数字都出现完毕，此时直接插入排序结束。
将49 38 65 97 76 13 24 49
首先选择49为对比值，假设其已经有序。
第二个数 38， 38＜49。故将38放在49前 38 49
第三个数 65， 65＞49。故将65放在49后 38 49 65
第四个数 97， 97＞65。故将97放在65后 38 49 65 97
第五个数 76， 76＜97，76＞65。故将76放在65后，97前 38 49 65 76 97
以此类推......
最后一个数49，49＜65，49≥49。故排序：13 27 38 49 49 65 76 97
不难发现，在排序之前相同元素的相对位置并没有发生变化，所以直接插入排序是稳定的排序
时间复杂度：
最好情况：也就是每次比较过程中只需要比较一次且不需要移动元素，因此时间复杂度为O(n)
最坏情况：给出的序列是逆序，而要求我们把他变成顺序排列，此时需要比较的次数为等差数列1 2 3 4 5.....n-1的求和，也就是O(n²)
平均情况：O(n²)
空间复杂度：
由于我们需要一个空闲的位置来存放用来比较的数字，所以空间复杂度为O(1)
适用性：
顺序存储和链式存储的线性表
折半插入排序
在直接插入排序中，每次插入都需要依次对比前边已经排好的序列。这在无形之中增加了比较的次数。而折半插入排序则是在每次插入时，首先和最大的数值比较，如果比最大的数值小，则选择已经排序好序列的中间值进行比较。比他大则往右走，比他小则往左走。查找插入位置的思想与折半查找类似
时间复杂度：
O(n²)
适用度：
仅适用于顺序存储的线性表
因为在链式存储中，不可以很简便的找到mid位置的数值，所以他不适用于链式存储
希尔排序
希尔排序的思想是把待排序的长度为q序列变为以某个增量n为基础的q/n个子表进行直接插入排序，直到基本有序。
希尔排序的概念不容易理解，我们选择一个复杂的例题进行举例讲解：
根据题目d=5
| 13 | 24 | 7 | 1 | 8 |
| 9 | 11 | 56 | 34 | 51 |
| 2 | 77 | 5 |
对每一列的三个数字进行直接插入排序后的序列为
2 11 5 18 9 24 7 34 51 13 77 56
再根据题目d＝3
| 2 | 11 | 5 |
| 1 | 8 | 9 |
| 24 | 7 | 34 |
| 51 | 13 | 77 |
| 56 |
对每一列进行排序后 1 7 5 2 8 9 24 11 34 51 13 77 56
空间效率：
空间复杂度为O(1)
时间复杂度：
因为希尔排序的时间复杂度尚未解决，所以最坏情况下的时间复杂度为O(n²)
稳定性：
希尔排序是一种不稳定的算法
适用性
很明显，希尔排序的过程中要不断对中间的元素进行调整，所以他只适合于顺序存储的线性表，而不适用于链式存储。
交换排序
冒泡排序
冒泡排序，从后往前或从前往后两两比较相邻的元素，按照题目所要求的排序顺序调整，直到序列比较结束，我们称之为一次冒泡。每次冒泡都会使一个元素放到自己应该放在的位置上。这样，一共n个元素进行冒泡排序，那么一共需要n-1躺冒泡就可以完成排序。
同样，我们使用一个例子来讲述冒泡排序
从后往前依次进行排序
第一趟冒泡：27＜49 不变 13＜27 不变 76＞13 将两者位置互换 97，65，38，49＞13，所以每一次比较都互换位置，直到13到达最前边。
直到第五趟排序后发现位置不再互换代表排序结束
注意！冒泡排序本身无法确认什么时候结束排序，我们可以通过某些方法对其进行改善让其明白什么时候结束排序
空间效率：
O(1)
时间复杂度：
最好情况：当初始序列有序时，第一次冒泡就结束排序，此时比较了n-1次。时间复杂度为O(n)
最差情况：初始序列为逆序，需要进行n-1躺的排序，第i躺排序要进行n-i次比较，也就是一个等差数列的求和操作。结果为(n*(n+1)/2)。时间复杂度为O(n²)。又因为我每次交换元素位置都需要交换三次，所以我的移动次数时比较次数的三倍。
平均情况：O(n²)
稳定性：
冒泡排序是一个稳定的排序
适用性：
冒泡排序适用于顺序存储和链式存储
快速排序
快速排序是所有内部排序算法中平均性能最优的排序算法
快速排序的思想是首先确定一个基准元素，通常选择第一个元素。通过一趟排序使其分为独立的两部分，左边＜基准元素，右边＞基准元素。以此类推，同样我们还是使用一个例子来解释快排的思想。
将其49 38 65 97 76 13 27 49 进行快速排序
以49为基准进行第一趟排序，结果为：27 38 13 | 49 | 76 97 65 49
流程如下：
首先定义两个指针i和j，j指向末尾49，i指向基准元素的位置。基准元素进入pivot
比较pivot j指向的元素，j≥pivot，不移动元素，此时将j向前移动一格。此时i指向49，j指向27
比较pivot j指向的元素，j＜pivot，移动元素，此时将27放到i指向的位置,i向后移动直到找到大于pivot的元素，把它放到j指向的位置
此时j向前移动，直到找到＜pivot的位置，以此类推
直到i==j停止。
按照同样的方法对左右两个分块进行快排
第二趟后 13 27 38 49 49 65 76 97
......
时间复杂度：
O(n²)
稳定性：
快排是一种不稳定的排序算法
适用性：
快排仅仅适用于顺序存储的线性表
空间复杂度：
由于快速排序是递归的排序方式
最好情况下为O(logn),
最坏情况为O(n)
平均情况为O(nlogn)
考虑总结插入排序和交换排序课后题相关不熟悉知识点
- 选择排序在每趟结束后都可以最少确定一个元素的最终位置
- 快速排序如果第一躺选取的基准元素在中间位置，那么在第二趟排序后就可以确定三个元素的最终位置，但是如果他第一躺选取的基准元素在最左侧或者最右侧的位置，那么第二趟排序后他就可以确定两个元素的最终位置。
- 我们需要明白快排什么时候排序速度快一些，只有当快速排序把他两边的元素数量大致相等时他的速度才会快。所以说当元素基本有序时，那么她所产生的两边序列就不均匀，不利于发挥快速排序的优势。总结如下：
-
- 当元素基本有序时，快速排序慢。当每次排序两边序列数量接近时，快速排序快
- 当元素基本有序时，直接插入排序的效率最高