直接插入排序
基本思想:
将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增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的可以采取选择排序
网友评论