快速排序

发表于 分类于 ， ， 本文字数： 1.6k

##快速排序（Quick Sort）

快速排序，又称划分交换排序（partition-exchange sort）

1.基本思想

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

2. 实现逻辑

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。

① 从数列中挑出一个元素，称为 “基准”（pivot），
② 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
③ 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置

###3. 动图演示

动图去。

4. 复杂度

平均时间复杂度：O(NlogN)
最佳时间复杂度：O(NlogN)
最差时间复杂度：O(N^2)
空间复杂度：根据实现方式的不同而不同

代码实现

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
public class QuickSort {

    int[] data;
    QuickSort(int[] data){
        this.data=data;
    }

    private void swap(int i,int j){
        if(i==j) return;
        int mid = data[i];
        data[i]=data[j];
        data[j]=mid;
    }
    public void sort(){
        sort0(0,data.length-1);
    }
    public void sort0(int l,int r){
        if(l<r){
            int mid = part(l,r);
            sort0(l,mid-1);
            sort0(mid+1,r);
        }
    }
    
    private int part(int l, int r) {
        int pValue = data[r];
        int lp=l,rp=r-1;
        while (rp>lp){
            while (lp<rp&&data[lp]<pValue){
                lp++;
            }
            while (rp>lp&&data[rp]>=pValue){
                rp--;
            }
            swap(rp,lp);
        }
        if(data[lp]>=pValue){
            swap(r,lp);
        }
        System.out.println(l+"  "+r+"  "+lp+"  "+rp+"  "+pValue+"  "+Arrays.toString(data));
        return lp;
    }

    public static void main(String[] args) {
        int[] data = new int[]{8,6,9,2,5,1,7,10,3,4};
        QuickSort qs = new QuickSort(data);
        System.out.println(Arrays.toString(data));
        qs.sort();
        System.out.println(Arrays.toString(data));
    }

非递归实现

使用栈或队列

------ 本文结束感谢您的阅读 ------
请我一杯咖啡吧！
itingyu 微信打赏 微信打赏