首页 > 算法 > 算法系列之 快速排序优化

算法系列之 快速排序优化

继上篇说了快速排序的实现原理:通过选择左边第一个数为轴值,分区让轴值左边的数都小于等于轴值并且右边都大于轴值,返回轴值并对左序列跟右序列进行递归处理

如果要排序的序列是基本有序的,这时选择左边第一个数为轴值,递归都只是对右边序列进行递归,会导致快速排序算法时间复杂度为N*N。
优化方法一是:
将中间的数跟第一个数交换,然后再选择左边第一个数为轴值。

另外,我们知道在一个序列基本达到有序的时候,采用插入排序可以达到近似于N的算法复杂度,远远要好于快速排序的N*logN时间复杂度。
优化方法二是:
当快速排序的子数组小于某个长度时,不继续递归,直接进行插入排序。经验表明,最好的组合方式是当n(子数组的长度)小于等于16时就使用插入排序

/*优化的快速排序*/

//选择轴值,分割,并返回轴值位置
int Partition(int a[], int l, int r)
{
     //优化1:取中间这一个数为轴值
     Swap(a[l], a[(r-l)/2]);
     //选择轴值
     int pivot = a[l];
     //分割
     int i = l, j = r;
     while (i < j)
     {
          while(i < j && a[j] > pivot) // 从右向左找第一个小于等于pivot的数
               j--;  
          if(i < j) 
               a[i++] = a[j];
          
          while(i < j && a[i] <= pivot) // 从左向右找第一个大于pivot的数
               i++;  
          if(i < j) 
               a[j--] = a[i];
     }
     a[i] = pivot;
     //返回轴值位置
     return i;
}


void QuickSort(int a[], int l, int r)
{
     // 如果子序列中只有0或1个记录,就不需排序
     if (r <= l)
     {
          return;
     }
     //优化2:如果序列长度小于等于阈值(16最佳),停止分割跳出递归
     if((r - l + 1) > 16)
     {
          //选择轴值,分割,并返回轴值
          int i = Partition(a,l,r);
          //对轴值左边的子序列进行递归快速排序
          QuickSort(a, l, i - 1);  
          //对轴值右边的子序列进行递归快速排序
          QuickSort(a, i + 1, r);
     }
}


void ImprovedQuickSort(int a[], int l, int r)
{
     QuickSort(a, l, r);
     //优化2收尾,进行一遍插入排序
     InsertSort(a,r - l + 1);
}

(转载本站文章请注明出处 www.helloitworks.com ,请勿用于任何商业用途)

分类: 算法 标签:
  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.