快速排序优化详解编程语言

基本思想

快速排序使用分治的思想，通过一趟排序将待排序列分隔成两部分，其中一部分的关键字比另一部分的关键字小。分别对这两部分记录继续进行排序，以达到整体有序的目的

快速排序的三个步骤

1. 选择基准。在待排序列中选择一个元素，作为’基准’(pirot)
2. 分割操作。以该基准在序列中的实际位置，把序列分成两个子序列，在基准左边的数都比该基准小，在基准右边的数都比该基准大
3. 递归地对两个序列进行排序，直到序列为空或者只有一个元素

代码

   function qSort(list){ 
      //递归到最后还是返回数组 
      if(list.length == 0){ 
          return []; 
      } 
      var lesser = []; 
      var greater = []; 
      //这里使用序列的第一个的方法 
      var pirot = list[0]; 
      //从1开始，因为已经抽出了一个值 
      for(var i = 1; i < list.length; i++){ 
          if(list[i] < pirot) { 
             lesser.push(list[i]); 
          } else { 
             greater.push(list[i]); 
          } 
      } 
      return qSort(lesser).concat(pirot, qSort(greater)); 
   }

如果每次都分成等长的子序列，那么需要分割log(n)次，然后乘以循环的n次，最佳情况是nlog(n)

选择基准的方式

对于分治算法，当每次划分时，算法若都能分成两个等长的子序列时，那么分治算法效率会达到最大。也就是说，基准的选择是很重要的。选择基准的方式决定了两个分割后两个子序列的长度，进而对整个算法的效率产生决定性影响。
最理想的方法是，选择的基准恰好能把待排序序列分成两个等长的子序列。
我们介绍三种选择基准的方法
方法(1)：固定位置
思想：取序列的第一个或最后一个元素作为基准
如果输入序列是随机的，处理时间可以接受的。如果数组已经有序时，此时的分割就是一个非常不好的分割。因为每次划分只能使待排序序列减一，此时为最坏情况，快速排序沦为冒泡排序，时间复杂度为O(n^2)。而且，输入的数据是有序或部分有序的情况是相当常见的。所以如果取固定位置且输入数据有序的时候，时间复杂度最差
方法(2)：随机选取基准
引入的原因：在待排序列是部分有序时，固定选取枢轴使快排效率底下，要缓解这种情况，就引入了随机选取枢轴
思想：取待排序列中任意一个元素作为基准
方法(3)：三数取中（median-of-three)
分析：最佳的划分是将待排序的序列分成等长的子序列，最佳的状态我们可以使用序列的中间的值，也就是第N/2个数。可是，这很难算出来，并且会明显减慢快速排序的速度。这样的中值的估计可以通过随机选取三个元素并用它们的中值作为枢纽元而得到。事实上，随机性并没有多大的帮助，因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为枢纽元。显然使用三数中值分割法消除了预排序输入的不好情形，并且减少快排大约14%的比较次数
举例：待排序序列为：8 1 4 9 6 3 5 2 7 0

左边为：8，右边为0，中间为6.
我们这里取三个数排序后，中间那个数作为枢轴，则枢轴为6

是时候停止快排

当待排序序列的长度分割到一定大小后，使用插入排序。

原因：对于很小和部分有序的数组，快排不如插排好。当待排序序列的长度分割到一定大小后，继续分割的效率比插入排序要差(插入排序的交换次数会更少)，此时可以使用插排而不是快排

   function insertSort(list){ 
       var temp, inner; 
       //从第2个元素开始循环 
       for(var outer = 1; outer < list.length; outer++){ 
           var temp = list[outer]; 
           inner = outer; 
           while(inner > 0 && list[inner - 1] > temp){ 
               list[inner] = list[inner - 1]; 
               inner--; 
           } 
           list[inner] = temp; 
       } 
   }