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

算法系列之五 快速排序

快速排序的基本思想是:

1、选择轴值:pivot
2、分割,并返回轴值位置:将序列划分为两个子序列L和R,使得L中所有记录都小于或等于轴值,R中记录都大于轴值
3、递归处理:对子序列L和R递归进行快速排序

对于步骤1跟2,可以用下面的例子来理解:
Image
说明:
开始时,i=0, j=4,选择a[0]为轴值pivot=a[0]。这时候可以把a[0]当成是一个坑,这个坑可以放其它的数。接着处理j,从右向左找直到a[j]小于等于轴值,然后将a[j]填到a[i],i递增,这样可以把小于等于轴值的值放到左边来。这时j又变成一个坑,然后处理i,从左向右找直到a[i]大于轴值,然后将a[i]填到右边的a[j],j递减,这样可以把大于轴值的值放到右边去。这时i又变成坑,接着类似这样循环处理,直到i==j时,将pivot填到a[i]
代码如下:
//选择轴值,分割,并返回轴值位置
int Partition(int a[], int l, int r)
{
     //选择轴值
     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;
}
步骤1、2再加上步骤3,一个完整的快速排序代码如下
void QuickSort(int a[], int l, int r)
{
     // 如果子序列中只有0或1个记录,就不需排序
     if (r <= l)
     {
          return;
     }
     //选择轴值,分割,并返回轴值
     int i = Partition(a,l,r);
     //对轴值左边的子序列进行递归快速排序
     QuickSort(a, l, i - 1);  
     //对轴值右边的子序列进行递归快速排序
    QuickSort(a, i + 1, r);
}
       

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

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