Go语言视频零基础入门到精通

五菱

快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

public class QuickSoft {
      
       private void swap(int a[],int i,int j)
       {
        int tmp=a;
        a=a[j];
        a[j]=tmp;
       }
      
       private int partition(int a[],int p,int r)
       {
        int point = a[r];
        //将小于等于point的元素移到左边区域
        //将大于point的元素移到右边区域
        int index=p;
        for (int i = index; i < r; ++ i) {
               if (a-point <= 0) {
                   swap(a, index++, i);
               }
           }
           swap(a,index,r);
           return index;
       }
      
       public void qsort(int a[],int p,int r)
       {
        if(p< r)
        {
         //确定拆分点，并对数组元素进行移动
         //这是快速排序算法的关键步骤
         int q=partition(a,p,r);
         //对左半段排序
         qsort(a,p,q-1);
         //对右半段排序
         qsort(a,q+1,r);
        }
       }
      
     public static void main(String[] args) {
  //声明一个类
  QuickSoft ms=new QuickSoft();
  int len=10;
  int a[]=new int[len];
  //初始化a数组
  
  System.out.println("原始数组如下：");
  for(int i=0;i< a.length;i++)
  {
      //产生a.length个随机数
   a = (int)(Math.random()*100000);  
   System.out.println(a);
  }
  System.out.println("---------------------");
  System.out.println("第一次分组后");
  ms.partition(a,0,len-1);
   for(int i=0;i< a.length;i++)
  {
   System.out.println(a);
  }
System.out.println("---------------------");
  //快速排序
  ms.qsort(a, 0, len-1);
  
  
  
  System.out.println("排序后的数组如下：");
  for(int i=0;i< a.length;i++)
  {
   System.out.println(a);
  }
  
  
}
}


运行：
C:\work>java   QuickSoft
原始数组如下：
32054
89211
55927
97591
45554
75152
44392
94214
4932
68341
---------------------
第一次分组后
32054
55927
45554
44392
4932
68341
97591
94214
89211
75152
---------------------
排序后的数组如下：
4932
32054
44392
45554
55927
68341
75152
89211
94214
97591[/pre]