排序集合

插入排序

朴素

是一个稳定的排序算法

需要反复移动数组中数的位置，时间复杂度最好为$O(n)$，最坏为$O(n^2)$。

折半查找

折半查找主要集中在查找被插入位置上，即在已经排好序的序列中二分查找位置。

时间复杂度仍为$O(n^2)$

希尔排序

两两比较，进行交换。

不断缩小比较的步长，最后进行微调

时间复杂度$O(n^{1.3})$，最坏情况下为$O(n^2)$

交换排序

冒泡排序

即比较前后两项，如果逆序就交换。一直到最后一项，完成一次冒泡。

进行n次，直到没有发生交换，表明有序。

快速排序

分治算法，先一个pivot（比如中点），所有比它小的都到pivot前面，比它大的都交换到pivot后面。

然后以pivot为分界点，前后递归进行

选择排序

简单选择排序

每一趟选择后面序列的最小值，放在最前面

堆排序

取出堆顶->将最后一个元素放最前面，然后进行更新

插入新数->将新数放在最后，然后进行更新

归并排序

和快排相反，从2个长度开始比较，然后扩大，~~

基数排序