快速排序

发表于 | 分类于

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

算法描述

快速排序使用分治法来把一个list，分成两个sub-list,其中一个都比基准小，一个都比基准大。具体描述如下：

  • 任意取一个元素为“基准”
  • 所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表；
  • 对各子表重新选择中心元素并以此规则调整，直到每个子表的元素只剩一个。

代码实现

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
48
49
50
51
52
53
public class QuickStart{
    public static int[] sort(int[] array,int start,int end){
        if(start>end){
            return array;
        }
        else{
            int partition = divide(array,start,end);
            sort(array,start,partition-1);
            sort(array,partition+1,end);
        }
        return array;
    }
    public static int divide(int[] array,int atart,int end){
                //基准选取最右边的元素
                int base =array[end];
                //start一旦等于end，就说明左右两个指针合并到了同一位置，可以结束此轮循环。
                while (start<end){
                    while (start<end&&array[start]<=base){
                        //从左边开始遍历，如果比基准值小，就继续向右走
                        start++;
                    }
                    //上面的while循环结束时，就说明当前的a[start]的值比基准值大，应与基准值进行交换
                    if (start<end){
                        //交换
                        int temp = array[start];
                        array[start]=array[end];
                        array[end] = temp;
                        //交换后，此时的那个被调换的值也同时调到了正确的位置(基准值右边)，因此右边也要同时向前移动一位
                        end--;
                    }
                    while (start<end&&array[end]>=base){
                        //从右边开始遍历，如果比基准值大，就继续向左走
                        end--;
                    }
                    //上面的while循环结束时，就说明当前的a[end]的值比基准值小，应与基准值进行交换
                    if (start<end){
                        //交换
                        int temp = array[start];
                        array[start] = array[end];
                        array[end] = temp;
                        //交换后，此时的那个被调换的值也同时调到了正确的位置(基准值左边)，因此左边也要同时向后移动一位
                        start++;
                    }
        
                }
                //这里返回start或者end皆可，此时的start和end都为基准值所在的位置
                return end;
    }
    public static void main(String[] args) {
            int[] array = new int[]{6,3,8,2,9,1};
            System.out.println(Arrays.toString(sort(array,0,5)));
        }
}

算法分析

  • 时间效率：O(nlogn)
  • 空间效率：O(logn)
  • 稳定性： 不稳定