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

javalearner

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

1. public class QuickSoft {
   
2.       
   
3.        private void swap(int a[],int i,int j)
   
4.        {
   
5.         int tmp=a[i];
   
6.         a[i]=a[j];
   
7.         a[j]=tmp;
   
8.        }
   
9.       
   
10.        private int partition(int a[],int p,int r)
    
11.        {
    
12.         int point = a[r];
    
13.         //将小于等于point的元素移到左边区域
    
14.         //将大于point的元素移到右边区域
    
15.         int index=p;
    
16.         for (int i = index; i < r; ++ i) {
    
17.                if (a[i]-point <= 0) {
    
18.                    swap(a, index++, i);
    
19.                }
    
20.            }
    
21.            swap(a,index,r);
    
22.            return index;
    
23.        }
    
24.       
    
25.        public void qsort(int a[],int p,int r)
    
26.        {
    
27.         if(p< r)
    
28.         {
    
29.          //确定拆分点，并对数组元素进行移动
    
30.          //这是快速排序算法的关键步骤
    
31.          int q=partition(a,p,r);
    
32.          //对左半段排序
    
33.          qsort(a,p,q-1);
    
34.          //对右半段排序
    
35.          qsort(a,q+1,r);
    
36.         }
    
37.        }
    
38.       
    
39.      public static void main(String[] args) {
    
40.   //声明一个类
    
41.   QuickSoft ms=new QuickSoft();
    
42.   int len=10;
    
43.   int a[]=new int[len];
    
44.   //初始化a数组
    
45.   
    
46.   System.out.println("原始数组如下：");
    
47.   for(int i=0;i< a.length;i++)
    
48.   {
    
49.       //产生a.length个随机数
    
50.    a[i] = (int)(Math.random()*100000);  
    
51.    System.out.println(a[i]);
    
52.   }
    
53.   System.out.println("---------------------");
    
54.   System.out.println("第一次分组后");
    
55.   ms.partition(a,0,len-1);
    
56.    for(int i=0;i< a.length;i++)
    
57.   {
    
58.    System.out.println(a[i]);
    
59.   }
    
60. System.out.println("---------------------");
    
61.   //快速排序
    
62.   ms.qsort(a, 0, len-1);
    
63.   
    
64.   
    
65.   
    
66.   System.out.println("排序后的数组如下：");
    
67.   for(int i=0;i< a.length;i++)
    
68.   {
    
69.    System.out.println(a[i]);
    
70.   }
    
71.   
    
72.   
    
73. }
    
74. }
    
76. 运行：
77. C:work>java   QuickSoft
78. 原始数组如下：
79. 32054
80. 89211
81. 55927
82. 97591
83. 45554
84. 75152
85. 44392
86. 94214
87. 4932
88. 68341
89. ---------------------
90. 第一次分组后
91. 32054
92. 55927
93. 45554
94. 44392
95. 4932
96. 68341
97. 97591
98. 94214
99. 89211
100. 75152
101. ---------------------
102. 排序后的数组如下：
103. 4932
104. 32054
105. 44392
106. 45554
107. 55927
108. 68341
109. 75152
110. 89211
111. 94214
112. 97591

复制代码

   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/11/30/000701000.zip