大家知道，快速排序的效率相对较高，谁能写出快速排序的流程和源码，帮助大家回忆学过的知识。

要求：
1、有流程简单分析。
2、有注释。
3、变量名通俗易懂。

1. /**
   
2. * 设计一个快速排序的算法：对"12,34,16,24,8,21,26,11,29,16"排序。
   
3. * 思路分析：
   
4. * 1、首先选定一个元素作为参数，保证该参数位于数组的中间，比该参数大的位于该参数所在
   
5. * 数组位置的右边，比该参数小的位于该参数所在数组位置的左边。
   
6. *                
   
7. * 2、位于该参数左边的数组递归调用上述方法，直至数组有序。该参数右边的数组同理。
   
8. *
   
9. * @author admin
   
10. *
    
11. */
    
12. public class Quicksor{
    
13. 
    
14.         /**
    
15.          * @param args
    
16.          */
    
17.         public static void main(String[] args) {
    
18.                 //arr表示我们要排序的数组了
    
19.                 int[] arr={12,34,16,24,8,21,26,11,29,16};
    
20.                 //输出未排序前的数组，与排序后的数组作比较
    
21.                 for (int i = 0; i < arr.length; i++) {
    
22.                         System.out.print(arr[i]+" ");
    
23.                 }
    
24.                 System.out.println();
    
25.                 //设置连个变量当作指针分别指向数组arr[0]元素的下标和arr[arr.length-1]元素的下标
    
26.                 int left=0,right=arr.length-1;
    
27.                 //调用quickSor()函数使数组有序
    
28.                 quickSor(arr,left,right);
    
29.                 //输出排序后的数组，检测我们的成果
    
30.                 for (int i = 0; i < arr.length; i++) {
    
31.                         System.out.print(arr[i]+" ");
    
32.                 }
    
33.         }
    
34. 
    
35.         private static void quickSor(int[] arr, int left, int right) {
    
36.                 //递归调用应满足数组下标left的值小于right
    
37.                 if(left<right){
    
38.                         //获取参数数组元素在有序数组中的位置
    
39.                         int q=sorNum(arr,left,right);
    
40.                         //递归调用quickSor()函数保证数组有序
    
41.                         quickSor(arr,left,q-1);
    
42.                         quickSor(arr,q+1,right);
    
43.                 }
    
44.         }
    
45.         //获取参数数组元素在有序数组中的位置的函数
    
46.         public static int sorNum(int[] arr,int left,int right){
    
47.                 //定义canshu变量并赋值位arr[left]
    
48.                 int  canshu=arr[left];
    
49.                 //循环调用的条件：左指针对应元素的下标应小于右指针对应元素的下标
    
50.                 while(left<right){
    
51.                         /**
    
52.                          * 在满足函数条件的情况下，如果参数大于右指针所对应的元素，右指针对应元素的下标减一
    
53.                          * 并将右指针对应的元素赋值给左指针
    
54.                          */
    
55.                         while(left<right&&canshu<=arr[right])   --right;
    
56.                                 arr[left]=arr[right];
    
57.                         /**
    
58.                          * 在满足函数条件的情况下，如果参数大于左指针所对应的元素，左指针对应元素的下标加一
    
59.                          * 并将左指针对应的元素赋值给右指针
    
60.                          */
    
61.                         while(left<right&&canshu>=arr[left])   ++left;
    
62.                                 arr[right]=arr[left];
    
63.                 }
    
64.                 //当跳出while循环时，此时左右指针同时指向同一元素。并把参数赋值给此元素
    
65.                 arr[left]=canshu;
    
66.                 return  left;
    
67.         }
    
68. 
    
69. }
    

复制代码

快速排序法博大精深啊，八百万个数字，四秒钟就排出来啦！！！把实现方法全部注释出来，大家共同学习吧！


import java.util.Calendar;
public class QuickSort1 {

       
        public static void main(String[] args) {
               
                int len=800000;
                int [] n=new int[len];
                for(int i=0;i<n.length;i++)
                {
                        n[i]=(int)(Math.random()*100);
                }
                Calendar cal=Calendar.getInstance();
                System.out.println("排序前时间："+cal.getTime());
                QSort(n,0,n.length-1);
                long stop=System.currentTimeMillis();
                cal=Calendar.getInstance();
                System.out.println("排序后时间："+cal.getTime());
                //for(int i=0; i<n.length; i++){
                       
                //        System.out.print(n[i]+" ");
                       
                //}

        }
       
        public static void QSort(int arr[],int low,int high){
                if(low < high){
                        //获取第一个数的从小到大排序后的位置，通过函数调用实现其功能
                        int pivot = getMiddle(arr,low,high);
                        //获取第一个数的位置后，分为两部分，左边一部分，右边一部分然后开始递归再次寻找左边与右边第一个数的对因位置
                        QSort(arr,low,pivot-1);
                        QSort(arr,pivot+1,high);
                }
        }
        //返回中轴的位置，寻找第一次排序第一个元素的位置
        public static int getMiddle(int[] list, int low, int high) {
                int tmp = list[low];    //数组的第一个作为中轴，保存起来
                while (low < high) {
                        //当最后一个数比第一个数大的时候，最后一个位置向前移动一位，因为排序是从小到大
                        while (low < high && list[high] > tmp) {
                                high--;
                        }
                        //当最后一个元素比第一个元素小的时候，则把最后一个元素赋值给第一个元素
                        list[low] = list[high];   //比中轴小的记录移到低端
                        //当左边元素比第一个元素小的时候，则移动左边一个下标
                        while (low < high && list[low] <= tmp) {
                                low++;
                        }
                        //当左边元素比第一个元素大的时候，则将当前元素赋值给右边下标的那个元素
                        list[high] = list[low];   //比中轴大的记录移到高端
                }
                //当左边下标与右边下标相等的时候，此时的位置就是第一次排序完成后第一个元素的位置，也就是中轴位置
                list[low] = tmp;              //中轴记录到尾
                return low;                   //返回中轴的位置
        }

}

都是大神,学习了,

感谢分享！！！