写了下快速排序及其优化.前段时间本来我以为我弄懂了,结果今天重写的时候又出了好多问题....之前没有理解原版快速排序key归位的操作...只是看结果正确就没管了.....事实证明,学编程还是要多敲代码啊.....
快速排序思想是把待排序的数组切分成二分.首先选取一个key值,下标小的那份所有数都小于等于key,下标大的那部分所有数都大于等于key.
然而快速排序还有待优化空间.
第一种优化,避免了极端情况下只切割一个数字出来,使效率降低...而取3个数的中位数则是经过证明的最好的取key方法....
第二种优化,三项切分发,中间项把所有等于key的值聚集起来并且不再进入循环...在数组中有重复数字的情况下效率非常高.
第三种优化,则是在数组比较小的情况下切换到插入排序,因为数组较小的情况下再使用快速排序递归也要递归很多次....而且根据快速排序的特性,在数据切分至较小的情况下数组已经是近似有序了,而面对近似有序的数组,插入排序的速度最快.