Java教程

快速排序

本文主要是介绍快速排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

快速排序

快速排序是由冒泡排序改进而得的,它的基本思想是在待排序的n个元素中人去一个元素(通常取第一个元素)作为基准数,经过第一次排序后,数据序列被分为两个部分。所有比基准数小的元素放在前面的部分,所有比基准数大的放在后面部分,这个过程称为一趟快速排序。

之后对产生的两个部分分别重复上述过程,直至每部分内只有一个元素或空为止。

  • 以一个数组作为示例,取区间第一个数为基准数。

  • 0123456789
    72 6 57 88 60 42 83 73 48 85
  • 初始时,i = 0; j = 9; X = a[i] = 72

  • 由于已经将 a[0] 中的数保存到 X 中,可以理解成在数组 a[0] 上挖了个坑,可以将其它数据填充到这来。

  • 从j开始向前找一个比X小或等于X的数。当j=8,符合条件,将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++; 这样一个坑a[0]就被搞定了,但又形成了一个新坑a[8],这怎么办了?简单,再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数,当i=3,符合条件,将a[3]挖出再填到上一个坑中a[8]=a[3]; j--;

  • 数组变为:

  • 0123456789
    48 6 57 88 60 42 83 73 88 85
  • i = 3; j = 7; X=72

  • 再重复上面的步骤,先从后向前找,再从前向后找。

  • 从j开始向前找,当j=5,符合条件,将a[5]挖出填到上一个坑中,a[3] = a[5]; i++;

  • 从i开始向后找,当i=5时,由于i==j退出。

  • 此时,i = j = 5,而a[5]刚好又是上次挖的坑,因此将X填入a[5]。

  • 数组变为:

  • 0123456789
    48 6 57 42 60 72 83 73 88 85
  • 可以看出a[5]前面的数字都小于它,a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。

  • 对挖坑填数进行总结:

    • 1.i =begin; j = end; 将基准数挖出形成第一个坑a[i]。

    • 2.j--由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。

    • 3.i++由前向后找比它大的数,找到后也挖出此数填到后面的坑a[j]中。

    • 4.再重复执行2,3二步,直到i==j,将基准数填入a[i]中

 

 public class Quicksort {
     public void quicksort(int[] sc,int begin,int end){
         if(begin<end){         //区间内至少存在两个元素的情况
         int i=begin;          
         int j=end;
         int temp=sc[begin];     //以sc[begin]为基准数或者说以temp为基准数
         while(i<j)              //从两端交替向中间扫描,直到i=j为止
         {
             while(j>i&&sc[j]>=temp)   
                 j--;                  //从右向左扫描,找一个小于temp的数sc[j]
             sc[i]=sc[j];              //找到以后就将sc[j],放入sc[i]中
             while(i<j&&sc[i]<=temp)
                 i++;                 //从左向右扫描,找到一个大于temp的数sc[i]
             sc[j]=sc[i];              //找到以后就将sc[i],放入sc[j]中
         }
         sc[i]=temp;              //当i=j时将基准数放入sc[i]中
         quicksort(sc,begin,i-1);         //对左区间递归排序
         quicksort(sc,i+1,end);             //对右区间递归排序
         }
     }
 }

下面写一段测试上面快速排序算法的代码:

 public class Test {
     public static void main(String args[]){
         int[] array={22,3,1,44,22,55,21,14,52,62,96,43};
         
         System.out.print("数组排序前的顺序为:");
         for(int i=0;i<array.length;i++){          
             System.out.print(array[i]+" ");
             }
         
         Quicksort a=new Quicksort();
         a.quicksort(array,0,array.length-1);
         
         
         System.out.println();
         System.out.print("数组排序后的顺序为:");
         for(int i=0;i<array.length;i++){
             System.out.print(array[i]+" ");
         }
     }
 }

测试结果:

 

 

 

这篇关于快速排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!