快速排序的原理以及时间复杂度_快速排序时间复杂度

快速排序资料

    快速排序（Quicksort）是对冒泡排序的一种改进。 
    快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，
其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序
过程可以递归进行，以此达到整个数据变成有序序列。 
1
2
3
4

快速排序基本原理

*** 选择两个引用，选择一个基准，比当前基准小的数据要往前走，比当前基准大的数据***

快速排序递归代码实现

快速排序采用分治的思想，通过一趟排序将当前序列分为两部分， 在一趟排序中，选取基准，定义两个引用分别指向当前的序列的第一个元素和最后一个元素，从后往前找当前基准小的数字向前走，从前往后找比当前基准大的数字向后走，一趟排序之后在基准的左边小于当前的基准，在基准右边大于当前的基准，接下来对于基准左右两边的序列再次进行排序，最终达到整个序列有序。

    //一次划分过程 时间复杂度 O(N)
    public static int partition(int[] array, int low, int high){
        //low和high分别为指向待排序列第一个数据和最后一个数据的两个引用
        //选择基准
         int mar = array[low];

        while(low < high){
            //从后往前找比基准小的数据往前走
            while(low < high && array[high] >= mar){
                high--; //high有可能会越界，所以要控制边界
            }
            if(low == high){
                break;
            }

            if(array[high] < mar){
                array[low] = array[high];
            }
            //从前往后找比基准大的数据往后走
            while(low < high && array[low] <= mar){
                low++;
            }
            if(low == high){
                break;
            }

            if(array[low] > mar){
                array[high] = array[low];
            }
        }
        array[low] = mar;
        return low;
    }

 public static void quick(int[] array, int low, int high){
        int partition = partition(array, low, high);
        //partition左边都是比其小的数据， partition的右边都是比其大的数据
        //判断partition左边数据个数大于1个
        if(partition > low+1){
            quick(array, low, partition-1);
        }
        //判断partition右边数据个数大于1个
        if(partition < high-1){
            quick(array, partition+1, high);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

快速排序的非递归实现

采用栈来进行，时间复杂度： O(log2N * N) 空间复杂度 递归 ：O(log2 N)
稳定性 ：不稳定

    public static void quickSort(int[] array){
        //参数的合法性
        if(array == null || array.length == 0){
            return;
        }
        quick(array, 0, array.length-1);
    }

    public static void quickSortByWhile(int[] array){
          //参数合法性的判断
        if(array == null || array.length == 0){
            return;
        }
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        stack.push(array.length-1);
        while(!stack.isEmpty()){
            int high = stack.pop();
            int low = stack.pop();
            //mar左边都比他小，右边都比它大
            int mid = partition(array, low, high);
            //保证进行partition的序列大于1
            //判断左边序列的个数是否大于1
            if(mid > low+1){
                stack.push(low);
                stack.push(mid-1);
            }
            //判断右边序列的个数是否大于1
            if(mid < high-1){
                stack.push(mid+1);
                stack.push(high);
            }
        }
    }
    }
    public static void main(String[] args) {
        int[] array = {10,2,19,0,8,100,58,12,1,7,20,15};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

快速排序的优化

• 1）明确当待排序序列完全有序1 2 3 4 5 6，退化成选择排序，每次相当 将最小的数据排在待排序列的第一个位置
• 2）快速排序在选取基准的时候，有可能会偏大偏小，所以选择基准的时候可以采取以下方式：
• a.随机选择基准，随机一个索引，使用索引所对应的数据作为基准
• b.三点取中法 第一个值、中间值、最后一个值、选择三个数的中间值作为基准

3. 快速排序中待排序列的长度达到一定数值之后，可以使用直接插入排序（越有序越快、时间复杂度趋近于O(n)），当待排序列的长度为5-20之间，采用直接插入排序 （high-low+1）

• 4）使用多线程处理子序列

快速排序最坏情况以及最坏时间复杂度：O(n^2)

最坏情况为，每一轮分不成两组，每一轮都只能把基准值索引放到第一个或者最后一个，因此一共需要n轮。
因此，最坏时间复杂度为O(n^2)。