1.选择排序---直接选择排序
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的 数据元素排完 。
找出序列中的最小关键字，然后将这个元素与序列首端元素交换位置。例如，序列前i个元素已经有序，从第i+1到第n个元素中选择关键字最小的元素，假设第j个元素为最小元素，则交换第j个元素与第i+1个元素的位置。依次执行此操作，直到第n-1个元素也被确定。
直接选择排序的特性总结：
直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：不稳定
2.选择排序---堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是 通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
堆的插入：
每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列，然后将这个新数据插入到这个有序数据中，在这个过程中要进行比较。
1.排大堆，就是最小的放在最上面，也就是升序
2.排小堆，就是最大的放在最上面，也就是降序
堆排序的特性总结：
堆排序使用堆来选数，效率就高了很多。
时间复杂度：O(N*logN)
空间复杂度：O(1)
稳定性：不稳定
应用：寻找M个数中的前K个最小的数并保持有序
3.插入排序---直接插入排序
插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移
直接插入排序的特性总结：
元素集合越接近有序，直接插入排序算法的时间效率越高
时间复杂度：O(N^2)
空间复杂度：O(1)，它是一种稳定的排序算法
稳定性：稳定
4.插入排序---希尔排序
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个 组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工 作。当到达=1时，所有记录在统一组内排好序。
适用场景
比较在希尔排序中是最主要的操作，而不是交换。用已知最好的步长序列的希尔排序比直接插入排序要快，甚至在小数组中比快速排序和堆排序还快，但在涉及大量数据时希尔排序还是不如快排；
适合小数组小数据。
希尔排序的特性总结：
希尔排序是对直接插入排序的优化。
当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就 会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
希尔排序的时间复杂度不好计算，需要进行推导，推导出来平均时间复杂度： O(N^1.3—N^2）
稳定性：不稳定
5.交换排序---冒泡排序
比较两个记录键值的大小，如果这两个记录键值的大小出现逆序，则交换这两个记录，这样将键值较小的记录向序列前部移动，键值较大的记录向序列后部移动
冒泡排序的特性总结：
冒泡排序是一种非常容易理解的排序
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定
缺点：慢，每次只能移动两个相邻的数据；
6.交换排序---快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右 子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
将区间按照基准值划分为左右两半部分的常见方式有：
hoare版本
挖坑法
前后指针版本
快速排序的特性总结：
快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
时间复杂度：O(N*logN)
空间复杂度：O(logN)
稳定性：不稳定
适用场景：在给大量数据排序的时候，快排的效率尤为明显
效率：此排序算法的效率在序列越乱的时候，效率越高。在数据有序时，会退化成冒泡排序；
7. 归并排序
基本思想：
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有 序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并排序的特性总结：
归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
时间复杂度：O(N*logN)
空间复杂度：O(N)
稳定性：稳定
适用场景：若n较大，并且要求排序稳定，则可以选择归并排序；
8.基数排序
基数排序的思想是按照组成关键字的各个数位进行排序，它是分配排序的一种。假如关键字是十进制数字，那么令r=10，d是所有关键字中的最大位数（位数小于d的数字，在前方补0）。基数排序可以从最低有效位开始，也可以从最高有效位开始。
基数排序的思想是：设立r个队列，编号分别为0,1,2,3…,r-1。首先按照最低有效位的值，将n个关键字放置到r个队列中，然后从小到大将元素收集起来，再按照次低位的值将元素放置到各个队列中，再进行收集，重复上述过程，直到收集完毕为止。
作者：九江董熙的原创文章
原文链接：https://blog.csdn.net/qq_45615577/article/details/115257685
