• 排序算法<No.2>【快速排序】


    最近因为项目需要,研究AI相关的东西,主要是算法相关的。

    有感触,所以决定,来一个系列的博文,可能会耗时很久,那就是要完成算法系列。起点,从最常用最基本的排序开始。后续会跟进其他类型的,比如树,图等领域的。希望各位博友读者监督

    今天,将开启排序算法中的快速排序。

    先来一点小历史插曲:

    快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。

    快速排序的思想:

    将输入的待排序的数字序列(数组),找到一个基准值(往往是待排数组的第一个元素),在这个数组中,将其他数与这个基准数进行比较,将待排序数组的所有元素分成两部分,一部分的元素都比基准数小(比如左边),一部分都比基准数大(比如右边)。

    上述思想,转化为编程实现的步骤,可以概述为下面的几步:

    1. 从给定的待排序数组中找一个基准数(通常取数组的第一个元素)

    2. 数组划界,将待排序的数组的元素与1中找到的基准数进行比较,将比这个基准数大的划分到右边,比这个基准数小的划分左边

    3. 重复上述1,2的操作(例如递归),直到待排序的子数组中的元素不需要排序(只有一个元素)

    思路和步骤都阐述清楚了,若还是没有完全理解,就可以结合代码实现过程来帮助理解了。在看代码之前,我想强调一点的是,快速排序算法中,重点是步骤2的数组划界,将待排序输入数组分成两部分,找到这个划界的分界点,或者说是数组的分隔下标。这个过程,有点像数学理论中的夹逼理论,两边向中间某个位置逼近,可能会出现小幅度的震荡,但是最终会收敛(找到划界线)。

    下面上算法实现代码(JAVA)

      1 /**
      2  * @author "shihuc"
      3  * @date   2017年1月17日
      4  */
      5 package quickSort;
      6 
      7 import java.io.File;
      8 import java.io.FileNotFoundException;
      9 import java.util.Scanner;
     10 
     11 /**
     12  * @author chengsh05
     13  *
     14  */
     15 public class QuickSortDemo {
     16 
     17     /**
     18      * @param args
     19      */
     20     public static void main(String[] args) {
     21         File file = new File("./src/quickSort/sample.txt");
     22         Scanner sc = null;
     23         try {
     24             sc = new Scanner(file);
     25             //获取测试例的个数
     26             int T = sc.nextInt();
     27             for(int i=0; i<T; i++){
     28                 //获取每个测试例的元素个数
     29                 int N = sc.nextInt();
     30         
     31                 int A[] = new int[N];
     32                 for(int j=0; j<N; j++){
     33                     A[j] = sc.nextInt();
     34                 }
     35                 quickSort(A, 0, A.length - 1);
     36                 printResult(i, A);
     37             }
     38         } catch (FileNotFoundException e) {            
     39             e.printStackTrace();
     40         } finally {
     41             if(sc != null){
     42                 sc.close();
     43             }
     44         }
     45     }
     46     
     47     /**
     48      * 采用类似两边夹逼的方式,向输入数组的中间某个位置夹逼,将原输入数组进行分割成两部分,左边的部分全都小于某个值,
     49      * 右边的部分全都大于某个值。
     50      * 
     51      * 快排算法的核心部分。
     52      * 
     53      * @param src 待排序数组
     54      * @param start 数组的起点索引
     55      * @param end 数组的终点索引
     56      * @return 中值索引
     57      */
     58     private static int middle(int src[], int start, int end){
     59         int middleValue = src[start];
     60         while(start < end){
     61             //找到右半部分都比middleValue大的分界点
     62             while(src[end] >= middleValue && start < end){
     63                 end--;
     64             }
     65             //当遇到比middleValue小的时候或者start不再小于end,将比较的起点值替换为新的最小值起点
     66             src[start] = src[end];
     67             //找到左半部分都比middleValue小的分界点
     68             while(src[start] <= middleValue && start < end){
     69                 start++;
     70             }
     71             //当遇到比middleValue大的时候或者start不再小于end,将比较的起点值替换为新的终值起点
     72             src[end] = src[start];
     73         }
     74         //当找到了分界点后,将比较的中值进行交换,将中值放在start与end之间的分界点上,完成一次对原数组分解,左边都小于middleValue,右边都大于middleValue
     75         src[start] = middleValue;
     76         return start;
     77     }
     78     
     79     /**
     80      * 通过递归的方式,对原始输入数组,进行快速排序。
     81      * 
     82      * @param src 待排序的数组
     83      * @param st 数组的起点索引
     84      * @param nd 数组的终点索引
     85      */
     86     public static void quickSort(int src[], int st, int nd){
     87         
     88         if(st > nd){
     89             return;
     90         }
     91         int middleIdx = middle(src, st, nd);
     92         //将分隔后的数组左边部分进行快排
     93         quickSort(src, st, middleIdx - 1);
     94         //将分隔后的数组右半部分进行快排
     95         quickSort(src, middleIdx + 1, nd);
     96     }
     97 
     98     /**
     99      * 打印最终的输出结果
    100      * 
    101      * @param idx 测试例的编号
    102      * @param B 待输出数组
    103      */
    104     private static void printResult(int idx, int B[]){
    105         System.out.print(idx + "--> ");
    106         for(int i=0; i<B.length; i++){
    107             System.out.print(B[i] + "  ");
    108         }
    109         System.out.println();
    110     }
    111 }

    下面附上程序中用于测试的案例:

     1 5
     2 7
     3 2 6 3 4 5 10 9
     4 5
     5 2 3 1 4 6
     6 11
     7 99 21 10 38 22 1 19 36 11 18 20
     8 9
     9 -11 8 19 -2 -1 16 2 199 2
    10 20
    11 1 9 8 22 991 38 71 20 0 99 21 10 38 22 1 19 36 11 18 20 

    最后附上测试结果:

    1 0--> 2  3  4  5  6  9  10  
    2 1--> 1  2  3  4  6  
    3 2--> 1  10  11  18  19  20  21  22  36  38  99  
    4 3--> -11  -2  -1  2  2  8  16  19  199  
    5 4--> 0  1  1  8  9  10  11  18  19  20  20  21  22  22  36  38  38  71  99  991  

    另外,要说一点的是,这里的快速排序算法实现,其实还有可以优化的空间,主要是middle函数的实现。 

    快速排序,多数情况下的时间复杂度都是O(N*logN)。

    下面,附上我从网络上找来的辅助理解快速排序的演示动画图片。

  • 相关阅读:
    linux基础知识-17
    linux基础知识-16
    linux基础知识-15
    linux基础知识-14
    linux基础知识-13
    phone 调试三种工具
    ANT_HOME is set incorrectly or ant could not be located .Please set ANT_HOME.
    如何解决google ping不通的问题。
    weinre targets none 的问题
    phonegap3.5了结
  • 原文地址:https://www.cnblogs.com/shihuc/p/6296576.html
一二三 - 开发者的网上家园