快速排序

in 数据结构 with 1 comment

快速排序(Quicksort)是对冒泡排序的一种改进,它使用了分治法(Divide and conquer)策略,把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。

排序思路

快速排序把一个序列(list)分为两个子序列(sub-lists)。

  1. 从数列中挑出一个元素,称为「基准」(pivot),
  2. 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任何一边)。在这个分割结束之后,该基准就处于数列的中间位置。这个称为分割(partition)操作。
  3. 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。
    递归到最底部时,数列的大小是零或一,也就是已经排序好了。这个演算法一定会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

递归模型如下:

$$ f(R,s,t) \begin{cases} nothing \qquad \text {R[s..t]中没有或者只有一个元素} \\ \\ do \begin{cases} i =partiton(R,s,t);\\f(R,s,i-1); \qquad \text {其他情况} \\f(R,i+1,t); \end{cases} \end{cases} $$

排序算法

以c为例,从小到大排序

#include<stdio.h>

int partition(int R[],int s,int t){
    int i=s,j=t;//这里取第一个元素为基准,你也可以取其他元素
    int tmp=R[i];
    while(i<j){
        while(i<j&&R[j]>=tmp)j--;//从右边取第一个比它小的元素,放到左边
        R[i]=R[j];
        while(i<j&&R[i]<=tmp)i++;//从左边取第一个比它大的元素,放到右边
        R[j]=R[i];
    }
    R[i]=tmp;//一次分割完成,右边的元素<=R[i]<=左边的元素,全局有序
    
    //打印结果
    int k;
    for (k = 0; k < 10;k++){
        printf("%d ",R[k]);
    }
    printf("\n");
    
    return i;
}
void quick_sort(int R[],int s,int t){
    int i;
    if(s<t){
        i=partition(R,s,t);
        quick_sort(R,s,i-1);
        quick_sort(R,i+1,t);
    }
}
int main(void){
    int a[] = {6,8,7,9,0,1,3,2,4,5};
    quick_sort(a,0,9);
}

输出结果:

5 4 2 3 0 1 6 9 7 8
1 4 2 3 0 5 6 9 7 8
0 1 2 3 4 5 6 9 7 8
0 1 2 3 4 5 6 9 7 8
0 1 2 3 4 5 6 9 7 8
0 1 2 3 4 5 6 8 7 9
0 1 2 3 4 5 6 7 8 9
过程分析

6 8 7 9 0 1 3 2 4 5 为例,

第一次划分 i=s=6 此时6已经被记录下来了,它的位置可以放置其他元素,我们用*表示。

原地分割版本:

#include<stdio.h>

int partition(int R[],int s,int t){
    int tmp=R[s];//这里选择s为基准,也可以选择其他元素
    R[s]=R[t];//这基准元素,放到最后一个位置
    R[t] = tmp;
    int i,index = s;//这里记录下分割位置
    for (i = s; i < t;i++){//从第一个遍历至倒数第二个,找到其位置
        if(R[i]<tmp){//tmp较大,tmp位置应该滞后
            int tmp2 = R[index];//交换index和当前元素
            R[index] = R[i];
            R[i] = tmp2;
           index++;//滞后
        }
    }
    int tmp2 = R[index];// 将基准元素放入
    R[index] = R[t];
    R[t] = tmp2;

    //打印结果
    int k;
    for (k = 0; k < 10;k++){
        printf("%d ",R[k]);
    }
    printf("\n");
    return index;
}
void quick_sort(int R[],int s,int t){
    int i;
    if(s<t){

        i=partition(R,s,t);
        quick_sort(R,s,i-1);
        quick_sort(R,i+1,t);
    }
}
int main(void){
    int a[] = {6,8,7,9,0,1,3,2,4,5};
    quick_sort(a,0,9);
}

动图示例:

ZM6G3D1Gjc.gif

图片来自https://visualgo.net,它采用的是第二种方法

算法分析

时间复杂度、空间复杂度:
  1. 平均情况:

设执行时间为T,得到递归关系式:

$$ 执行时间 \quad T(n) = cn+\frac{1}{n}\sum_{k=1}^{n}(T(k-1)+T(n-k)) \qquad其中一次分割为线性时间,不妨设为cn $$

故时间复杂度为O(nlog2n),空间复杂度为O(log~2~n)

  1. 最坏情况:递归树高度为n,每一层划分时间为n-1,所以时间复杂度为O(n^2^) ,空间复杂度为O(n)
  2. 最好情况:递归树高度为O(log~2~n),每一层划分时间为O(n),所以时间复杂度为O(nlog~2~n) ,空间复杂度为O(log~2~n)

初始数据正序或者反序时,呈现最坏情况;初始数据随机分布时呈现较好的情况

稳定性:

相同元素的相对位置可能发生改变,这是一种不稳定的排序方法。如{5,2,4,8,7,4}

复杂性:

较复杂

归位:

全局有序。

Responses
  1. study 一起学习 go

    Reply