排序算法

---

直接插入排序

基本思想:

将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。

要点：设立哨兵，作为临时存储和判断数组边界之用。

前i个排好，每次向后扩展一个

---

选择排序

在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

堆排序

以最大堆为例

以数组建堆

父节点必定比他的子节点小

父节点下标为i，则子节点下标为2i+1和2i+2

step1：建堆,假设长度为length

从最后一个有孩子节点(length-1)/2的节点开始，往下做堆调整操作;之后再-1往前一个节点重复该操作

如上图a，我们现在num[3]节点进行调整，即97，找出他的子节点较小的一个进行交换，49和97交换，继续从往下调整，直到数组结束或者该节点小于他的子节点，

重复操作直到建堆完毕。

step2：排序

每次将堆底元素和堆顶元素进行对换，然后对新的对顶元素重新进行渗透堆调整，数组长度-1；重复操作，直到排序完毕，此时数组呈倒序排列

代码：

---

冒泡排序

基本思想：

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

---

快速排序

用分治思想来解决问题

优化：可以对元素小于等8的可以采取选择排序