黑马程序员技术交流社区

标题: 快速排序 [打印本页]
作者: 放课后小朋友    时间: 2014-2-13 10:35
标题: 快速排序
大家知道，快速排序的效率相对较高，谁能写出快速排序的流程和源码，帮助大家回忆学过的知识。

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


作者: pifuhanshu    时间: 2014-3-18 22:11
  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{

  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.         }

  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.         }

  69. }
复制代码


作者: 向日葵的曙光    时间: 2014-4-10 18:07
快速排序法博大精深啊，八百万个数字，四秒钟就排出来啦！！！把实现方法全部注释出来，大家共同学习吧！


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;                   //返回中轴的位置
        }

}
作者: 贾俊锋    时间: 2014-5-21 01:39
都是大神,学习了,
作者: 王飞163    时间: 2014-6-25 00:24
感谢分享！！！



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2