算法记忆：（小白垂死挣扎版）
1、冒泡排序（改进版）：利用sorted布尔标志，先置0进入循环判断，再置1，i从第一个元素lo开始到hi的前一个元素，比较i和i+1的元素，若逆序，发生交换，sorted标志置假；
2、快速排序：通过partition得到轴点，再分别以轴点为界递归调用；partition算法着重于挖坑，和设置哨兵i和j，j要先从hi的位置开始走；while while if和while if，出了外层while循环后两哨兵相遇，并形成坑，将pivot放入；并得到i；
3、归并排序：重点在归，用空间换取了时间效率，在merge的子函数中，申请B存放以mi为界的前部分数据，C直接指向mi+1位置的元素就行；在保证j，k并未越界的情况下，if（j<lb && !(k<lc) || B<C）a[i++]=B[j++];
4、插入排序：手上拿的元素key=a[i]，i从lo+1开始，记录已排序最后一个元素的下标j=i-1；当手上拿的元素比前面的元素小时，前面的元素一个一个往后挪一个位置，直至找到key该有的位置；因为在前面的while循环中i递减，出循环后应把key放在a[i+1]的位置；
5、选择排序：先声明index；外循环i从lo开始，到lo+n-1结束（因为j在i的基础上+1），把i给index；外循环j从i+1开始，到lo+n结束，依次与i后的元素进行比较，逆序则index得到当前的j；出了内循环，交换index和i对应的元素；
6、希尔排序：定gap声明insertnum；while(gap)；外循环for，i从lo+gap开始，insert保存a[i]值，j=i；内循环while，判断j>=gap+lo以及insertnum是否小于a[j-gap]，真则j与j-gap对应的元素发生交换，j-=gap；出了内循环insertnum给a[j]；出了外循环gap递减；
7、堆排序：建堆调整堆（从最后一个非叶节点开始，下标为(size-1)/2，调整堆时需要注意maxIndex若有子节点，则仍需调整）；堆顶和最后一个元素交换，之后需调整剩下的0-size-2个元素的堆序性；
七大排序.jpg
稳定性上：只有冒泡，归并、插入是稳定的；
适用场合总结：
平均性能上：堆排序、归并排序、快速排序>希尔排序>>冒泡排序、插入排序、选择排序
最好情况：冒泡排序和插入排序更好
最坏情况：堆排序和归并排序
快速排序性能不稳定
网友评论