快排的实现及快排的排序效率测试

 排序之快速排序【未做优化的版本】

 　　1. 实现： 

　　　　①找基准点：第一个元素； 

　　　　②right：从数组的最后一个元素开始，从右往左，直到找到小于或等于基准点的元素；每次都要right比left先走； 

　　　　③left：从基准点的后一个元素开始，从左往右，直到找到大于或等于基准点的元素；

　　　　④交换left和right所在位置的元素；

　　　　⑥left继续往右走，right继续往左走，直到两个人相遇；

　　　　⑦将相遇点所在位置的元素和基准点所在位置的元素做交换，基准点到了中间位置；

　　　　⑧【递归】将基准点左边的所有元素当成一个数组，重复①~⑦步骤；基准点右边的所有元素也是如此；

　　2. 快排的效率为什么高：空间复杂度和时间复杂度；用概念来套冒泡和快排。

　　　　（1）一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示

　　　　（2）在计算算法复杂度时一般只用到大O符号　　

　　　　（3）在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1)

　　　　（4）一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)

　　　　（5）常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)

　　　　（6）表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。其中Ο(log2n)、Ο(n)、 Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者（即多项式时间复杂度的算法）是有效算

　　3. 快排的时间复杂度：O（n×log（n））

　　　　什么情况下，快排的时间复杂度会降低到”N的平方”：通过快排将一个从大到小的数组，排序为从小到大时，其效率为”N的平方”。

 1 public class A01QuickSort {
 2 　　public static void main(String[] args) {
 3 　　　　A01QuickSort quickSort = new A01QuickSort();
 4 
 5 
 6 　　　　// 测试快排的效率：
 7 　　　　//    int number = 1000000;
 8 　　　　//    int[] array = new int[number];
 9 　　　　//    for (int i = 0; i < array.length; i++) {
10 　　　　//    array[i] = new Random().nextInt(number);
11 　　　　//    }
12 
13 　　　　//配合后面的元素输出，测试快排是否排序准确：
14 　　　　int[] array = new int[] {181,181,187,181};
15 　　　　System.out.println("数组准备完毕~");
16 
17 　　　　long start = System.currentTimeMillis();
18 　　　　quickSort.quickSort(array, 0, array.length - 1);
19 　　　　long end = System.currentTimeMillis();
20 　　　　System.out.println("quickSort 用时：" + (end - start));// 测试结果： 元素为5万个时：11毫秒。50万：66毫秒。100万：136毫秒
21 
22 　　　　//遍历输出数组元素：
23 　　　　　　quickSort.traverseArray(array);
24 　　}
25 
26 　　/**
27 　　* 快排的实现
28 　　* @param target
29 　　* @param left
30 　　* @param right
31 　　*/
32 　　public void quickSort(int[] target, int left, int right) {
33 　　　　if (left >= right) {
34 　　　　　　return;
35 　　　　}
36 　　　　int pivot = target[left];// 基准点
37 　　　　int temp;
38 　　　　int i = left;
39 　　　　int j = right;//为什么要声明i和j，因为后面做迭代的时候还需要用到最初的left和right
40 　　　　while (i < j) {//验证array数组至少有2个元素，才要做排序
41 　　　　　　/**
42 　　　　　　* 提问：
43 　　　　　　* 为什么是 while里的判断，为什么是 “target[j] >= pivot”，而不是“target[j] > pivot”？？？
44 　　　　　　* 答: 数组[181,181,187,181]，分别用上面两种while去测试：
45 　　　　　　*    如果是">="时，因为 181 >= 181 成立，所以right就会从右往左移；
46 　　　　　　*    如果是">"时，因为 181 > 181 成立，所以right就不会左移。
47 　　　　　　* 重点！！！right或left，必须有一方得是移动的！！！否则程序就会进入死循环！！！
48 　　　　　　*/
49 　　　　　　// 如果right一直都大于或等于pivot，则继续走，直到找到比key小的：
50 　　　　　　while (target[j] >= pivot && i < j) {
51 　　　　　　　　j--;
52 　　　　　　}
53 　　　　　　// 如果left一直都小于等于pivot，则继续走，直到找到比key大的：
54 　　　　　　while (target[i] <= pivot && i < j) {
55 　　　　　　　　i++;
56 　　　　　　}
57 　　　　　　// 此时right < key, left > key，将i和j做交换：
58 　　　　　　if (i < j) {//这里做判断是为了right到了left位置时，不用再将执行下面这三行代码了：
59 　　　　　　　　temp = target[i];
60 　　　　　　　　target[i] = target[j];
61 　　　　　　　　target[j] = temp;
62 　　　　　　}
63 　　　　}
64 　　　　// left和right相遇了：
65 　　　　// ①将相遇点的元素和key做交换：
66 　　　　target[left] = target[j];
67 　　　　target[j] = pivot;
68 　　　　// ②基准点两边的元素的分别再做排序：
69 　　　　quickSort(target, left, j - 1);
70 　　　　quickSort(target, j + 1, right);
71 　　}
72 
73 　　//遍历数组
74 　　public void traverseArray(int[] array) {
75 　　　　for(int element : array) {
76 　　　　　　System.out.println(element);
77 　　　　}
78 　　}
79 }