首先,快速排序是一个不稳定的排序,平均时间复杂度为O(nlogn),最好情况为O(nlogn),最差为O(n^2)

那为什么快速排序能被称为快排,而不是其他同样复杂度的别的算法呢?因为快排复杂度的隐藏常数因子比较小

主要思想:找一个基准点,让该点左边的元素都比他小(大), 右边的元素都比他大(小)。接着递归执行。

排序函数:

void quiksort(int *a, int l, int r)
{
    if(l < r)
    {
        int partitionIndex = partition(a, l, r);
        quiksort(a, l, partitionIndex-1);
        quiksort(a, partitionIndex+1, r);
    }
}

划分方法:3种

1.挖坑法

思路:找一个关键字x(通常为第一或最后一位)作为初始的坑位,两个变量l = 0, r = N-1

第一步:从右往左找小于x的位置,放入坑中,然后该点为坑

第二步:从左往右找大于x的位置,放入坑中,然后该点为坑(注:这里用的第一个值为坑,如果用的最后一个为坑,则应该先左到右找,在右到左找)

一直执行到l >= r的时候退出循环

第三步:最后剩的的那个坑放入x

执行示例:

4 1 7 6 9 2 8 0 3 5 ----初始

3 1 7 6 9 2 8 0 _ 5

3 1 _ 6 9 2 8 0 7 5

3 1 0 6 9 2 8 _ 7 5

3 1 0 _ 9 2 8 6 7 5

3 1 0 2 9 _ 8 6 7 5

3 1 0 2 _ 9 8 6 7 5

3 1 0 2 4 9 8 6 7 5

代码:

int partition(int *a, int l, int r)
{
    int i = l, j = r, x = a[l];
    while(i < j)
    {
        while(i < j && a[j] >= x) j--;
        if(i < j) a[i] = a[j];
        while(i < j && a[i] <= x) i++;
        if(i < j) a[j] = a[i];
    }
    a[i] = x;
    return i;
}

2.左右指针法

思路:先找一个关键字x(通常为第一或最后一位),l=0,r=N-1,

第一步:先右往左找小于x的数

第二步:在左往右找大于x的数

第三步:交换该两个数

上述,当l<r时,一直循环

第四步:将最后剩的位置填上x

执行示例:

4 1 7 6 9 2 8 0 3 5

4 1 7 6 9 2 8 0 3 5

4 1 3 6 9 2 8 0 7 5

4 1 3 6 9 2 8 0 7 5

4 1 3 0 9 2 8 6 7 5

4 1 3 0 9 2 8 6 7 5

4 1 3 0 2 9 8 6 7 5

2 1 3 0 4 9 8 6 7 5

代码:

void swap(int *a, int i, int j){int t;t=a[i];a[i]=a[j];a[j]=t;}
int partition(int *a, int l, int r)
{
    int i = l, j = r, x = a[l];
    while(i < j)
    {
        // 顺序非常重要,因为j往前走后,i就不能往后走了
        while(i < j && a[j] >= x) j--;
        while(i < j && a[i] <= x) i++;
        if(i < j) swap(a, i, j);
    }
    swap(a, l, j);
    return j;
}

3.前后指针法

思路:定义cur,pre,初始关键字x(第一或最后)

当a[cur]<x,同时往后走

当a[cur]>x,cur往后走,pre不动

当a[cur]再次<x时,交换a[cur],a[pre]的值

执行示例:

4 1 7 6 9 2 8 0 3 5

4 1 2 6 9 7 8 0 3 5

4 1 2 0 9 7 8 6 3 5

4 1 2 0 3 7 8 6 9 5

3 1 2 0 4 7 8 6 9 5

代码:

void swap(int *a, int i, int j){int t;t=a[i];a[i]=a[j];a[j]=t;}
int partition(int *a, int l, int r)
{
    int pre = l, cur = l, x = a[l];
    while(cur <= r)
    {
        if(a[cur] < x && ++pre < cur)
            swap(a, cur, pre);
        cur++;
    }
    swap(a, l, pre);
    return pre;
}


最后总的可执行的代码示例:

#include <iostream>
using namespace std;
/*
// 挖坑法
int partition(int *a, int l, int r)
{
    int i = l, j = r, x = a[l];
    while(i < j)
    {
        while(i < j && a[j] >= x) j--;
        if(i < j) a[i] = a[j];
        while(i < j && a[i] <= x) i++;
        if(i < j) a[j] = a[i];
    }
    a[i] = x;
    return i;
}
*/
/*
// 左右指针法
void swap(int *a, int i, int j){int t;t=a[i];a[i]=a[j];a[j]=t;}
int partition(int *a, int l, int r)
{
    int i = l, j = r, x = a[l];
    while(i < j)
    {
        // 顺序非常重要,因为j往前走后,i就不能往后走了
        while(i < j && a[j] >= x) j--;
        while(i < j && a[i] <= x) i++;
        if(i < j) swap(a, i, j);
    }
    swap(a, l, j);
    return j;
}
*/

// 前后指针法
void swap(int *a, int i, int j){int t;t=a[i];a[i]=a[j];a[j]=t;}
int partition(int *a, int l, int r)
{
    int pre = l, cur = l, x = a[l];
    while(cur <= r)
    {
        if(a[cur] < x && ++pre < cur)
            swap(a, cur, pre);
        cur++;
    }
    swap(a, l, pre);
    return pre;
}

void quiksort(int *a, int l, int r)
{
    if(l < r)
    {
        int partitionIndex = partition(a, l, r);
        quiksort(a, l, partitionIndex-1);
        quiksort(a, partitionIndex+1, r);
    }
}

int main()
{
    int n, *a;
    while(cin >> n)
    {
        a = new int[n];
        for(int i = 0; i < n; i++)
            cin >> a[i];
        quiksort(a, 0, n-1);
        for(int i = 0; i < n; i++)
            cout << a[i] << " ";
        cout << endl;
    }
    return 0;
}


你可能感兴趣的文章

评论区

发表评论

必填

选填

选填

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

您好,欢迎到访网站!
  查看权限

«   2019年1月   »
123456
78910111213
14151617181920
21222324252627
28293031

最新留言