最近因为项目需要，研究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）。
下面，附上我从网络上找来的辅助理解快速排序的演示动画图片。
