欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

详解快速排序算法中的区间划分法及Java实现示例

程序员文章站 2024-03-11 14:33:37
快速排序是c.r.a.hoare于1962年提出的一种划分交换排序。该方法的基本思想是: 1.先从数列中取出一个数作为基准数。 2.分区过程,将比这个数大的数全放到它的...

快速排序是c.r.a.hoare于1962年提出的一种划分交换排序。该方法的基本思想是:
1.先从数列中取出一个数作为基准数。
2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
3.再对左右区间重复第二步,直到各区间只有一个数。
算法的思路很清晰,但是如果在区间划分过程中边界值没有处理好,也是很容易出现bug的。下面给出两种比较清晰的思维来指导区间划分代码的编写。
第一种思维即所谓的挖坑法思维,下面通过分析一个实例来分析一下挖坑法的过程:
以一个数组作为示例,取区间第一个数为基准数。
详解快速排序算法中的区间划分法及Java实现示例

初始时,left = 0; right= 9;   x = a[left] = 72
由于已经将a[0]中的数保存到x中,可以理解成在数组a[0]上挖了个坑,可以将其它数据填充到这来。
从right开始向前找一个<=x的数。显然,right=8时,符合条件,将a[8]挖出再填到上一个坑a[left]中。 这样一个坑a[0]就被搞定了,但又形成了一个新坑a[8],这怎么办了?简单,再找数字来填a[8]这个坑。这次从left开始向后找一个大于x的数,当left=3,符合条件,将a[3]挖出再填到上一个坑a[right] 中;
数组变为:

详解快速排序算法中的区间划分法及Java实现示例
再重复上面的步骤,最终数组将变成如下形式:
详解快速排序算法中的区间划分法及Java实现示例
可以看出a[5]前面的数字都小于它,a[5]后面的数字都大于它。将x填入a[5]的坑中,数据变为:
详解快速排序算法中的区间划分法及Java实现示例
因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。
对挖坑填数进行总结
1.i =l; j = r; 将基准数挖出形成第一个坑a[i]。
2.j--由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。
3.i++由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。
4.再重复执行2,3二步,直到i==j,将基准数填入a[i]中。
照此分区方法,快速排序java代码如下:

public class partition { 
 
 /** 
  * 基于base划分,小的在左,大的在右, 不要求整个序列有序 
  * 
  * @param ary 
  * @param base 
  */ 
 static void sort(int[] ary, int base) { 
  int left = 0; 
  int right = ary.length - 1; 
   
  int leftpoint = left, rightpoint = right; 
   
  while (true) { 
   // 分成左右两边同时进行比较,一边从左向右,一边从右向左, 
   while (leftpoint < right && ary[leftpoint++] < base); //leftpoint大于right或ary[leftpoint]>base停止循环 
    
   while (rightpoint >= left && ary[rightpoint--] > base); //反之 
   system.out.println("左边需要交换的索引:" + (leftpoint-1)); 
   system.out.println("右边需要交换的索引:"+ (rightpoint+1)); 
   //上面拿到了不符合条件的两个索引,即需要交换的两个索引 
   if (leftpoint - 1 < rightpoint + 1) {//需要交换 
    swap(ary, leftpoint - 1, rightpoint + 1); 
    util.printarray(ary); 
    leftpoint = left; 
    rightpoint = right; 
   } else { 
    break; 
   } 
  } 
 } 
  
 
 private static void swap(int[] ary, int a, int b) { 
  int temp = ary[a]; 
  ary[a] = ary[b]; 
  ary[b] = temp; 
 } 
 
 public static void main(string[] args) { 
  int[] ary = util.generateintarray(10); 
  system.out.println("原序列:"); 
  util.printarray(ary); 
  sort(ary, 5); 
  system.out.println("排序后:"); 
  util.printarray(ary); 
 } 
} 

结果:

原序列: 
[2, 8, 4, 3, 7, 5, 1, 9, 0, 6] 
左边需要交换的索引:1 
右边需要交换的索引:8 
[2, 0, 4, 3, 7, 5, 1, 9, 8, 6] 
左边需要交换的索引:4 
右边需要交换的索引:6 
[2, 0, 4, 3, 1, 5, 7, 9, 8, 6] 
左边需要交换的索引:5 
右边需要交换的索引:5 
排序后: 
[2, 0, 4, 3, 1, 5, 7, 9, 8, 6] 

区间划分的的另一种指导思维:
将数组的第一个元素作为区间划分值,从第二个元素开始分区,直到形成如图所示的结果,

详解快速排序算法中的区间划分法及Java实现示例

然后交换l<t区间的右边界值和t,形成如下的结果:

详解快速排序算法中的区间划分法及Java实现示例

如此,可以如下编写快速排序代码:

public void qsort(int array[],int left,int right) 
 { 
  if(left < right){ 
 
   int key = array[left]; 
 
   int high = right; 
    
   int low = left+1; 
    
   while(true){ 
     
    while(low <= high && array[low] <= key) low++; 
 
    while(low <= high && array[high] >= key) high--; 
        
    if(low > high) 
     break; 
 
    swap(array,low,high); 
   } 
   swap(array,left,high); 
    
   printarray(array); 
 
   qsort(array,left,high-1); 
 
   qsort(array,high+1,right); 
  } 
 }