【面试：基础题05：快速排序】

01.简介

快速排序是一种高级的排序算法，平均时间复杂度可以达到O(n$log_2n$)，它的主要思想是找一个基准点大于基准点的放在基准点的一端 小于基准点的放在基准点一端 每一端重复这个过程 用递归实现。

总思想：每趟的基准点不变 最后交换基准点

实现快速排序有两个主流的方法：

1.单边循环法：选取最右端作为基准点，有两个变量i j，i用于维护小于基准点元素的边界，也就是每次交换的目标索引， j负责找到比基准点小的元素，一旦找到与i进行交换，最后i在与基准点进行交换 完成一趟排序。

2.双边循环法：选取最左端作为基准点，有两个变量i j，i负责从左向右找到比基准点大的元素， j负责找到比基准点小的元素，一旦找到j与i进行交换，最后基准点再与i j重合点进行交换 一趟排序完成。

02.算法步骤

对数列{5,3,7,2,9,8,1,4}进行升序快速排序。

单边循环法(最右端为基准点):

i=0与j=1进行交换 i=1与j=3进行交换 i=2与j=6进行交换 i=3与r=7进行交换
3 2 1 4 9 8 7 5
i=0与r=2进行交换
1 2 3 4 9 8 7 5
i=1与j=1进行交换 i=2与r=2进行交换
1 2 3 4 9 8 7 5
i=4与r=7进行交换
1 2 3 4 5 8 7 9
i=5与j=5进行交换 i=6与j=6进行交换 i=7与r=7进行交换
1 2 3 4 5 8 7 9
i=5与r=6进行交换
1 2 3 4 5 7 8 9

双边循环法(最左端为基准点):

基准点下标0 基准点值5
i=2与j=7进行交换 i=4与j=6进行交换 i=4与j=4进行交换 l=0与j=4进行交换
1 3 4 2 5 8 9 7
基准点下标0 基准点值1
i=0与j=0进行交换 l=0与j=0进行交换
1 3 4 2 5 8 9 7
基准点下标1 基准点值3
i=2与j=3进行交换 i=2与j=2进行交换 l=1与j=2进行交换
1 2 3 4 5 8 9 7
基准点下标5 基准点值8
i=6与j=7进行交换 i=6与j=6进行交换 l=5与j=6进行交换
1 2 3 4 5 7 8 9

双边循环法需要注意的几个问题

1.基准点在左边 且先j-- 再i++

2.while(i<j)一定要加 否则排序好的值会再次被打乱

3.while(i<j&&a[i]<=x) = 一定要加 为了防止基准点被移动

代码实现

单边循环法:

public static void sort1(int[] a,int l,int r){
    if (l>=r)
        return;
    int i=l;
    int x = a[r];
    for (int j=l;j<r;j++){
        if (a[j]<x){
            int t=a[j];
            a[j]=a[i];
            a[i]=t;
            i++;
        }
    }
    int t=a[r];
    a[r]=a[i];
    a[i]=t;
    for (int k=0;k<a.length;k++)
        System.out.printf("%d ",a[k]);
    System.out.println();
    sort2(a,l,i-1);
    sort2(a,i+1,r);
}
public static void main(String[] args) {
    int[] a = {5,3,7,2,9,8,1,4};
    sort1(a,0,a.length-1);
}

结果

3 2 1 4 9 8 7 5
1 2 3 4 9 8 7 5
1 2 3 4 9 8 7 5
1 2 3 4 5 8 7 9
1 2 3 4 5 8 7 9
1 2 3 4 5 7 8 9

双边循环法

public static void sort2(int[] a,int l,int r){
    if (l>=r)
        return;
    int x = a[l];
    int i = l;
    int j = r;
    while (i<j){
        while (i<j&&a[j]>x)// 顺序要固定,如果不固定会导致 i找到最后大于基准点的值停止 j会因为
            // 想要找到小的 然后最终与i重合 退出循环 但是现在j还没有找到小于基准点的值 所以最后
            // 会因为最后和基准点进行交换导致错误
            j--;
        while (i<j&&a[i]<=x)// =为了防止 基准点被移动，i<j是为了防止排序好的值再次被打乱
            i++;
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
    int t=a[l];
    a[l]=a[j];
    a[j]=t;
    for (int k=0;k<a.length;k++)
        System.out.printf("%d ",a[k]);
    System.out.println();
    sort1(a,l,j-1);
    sort1(a,j+1,r);
}
public static void main(String[] args) {
    int[] a = {5,3,7,2,9,8,1,4};
    sort2(a,0,a.length-1);
}

结果

1 3 4 2 5 8 9 7
1 3 4 2 5 8 9 7
1 2 3 4 5 8 9 7
1 2 3 4 5 7 8 9