随机快速排序算法(C语言)_c语言随机排序

随机快速排序（C语言）

分治法基本思想

将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归的解决这些子问题，然后将各个子问题的解合并得到原问题的解。

快速排序

原链接：https://blog.csdn.net/haelang/article/details/44496387

快速排序用到了分治思想，同样的还有归并排序。乍看起来快速排序和归并排序非常相似，都是将问题变小，先排序子串，最后合并。不同的是快速排序在划分子问题的时候经过多一步处理，将划分的两组数据划分为一大一小，这样在最后合并的时候就不必像归并排序那样再进行比较。但也正因为如此，划分的不定性使得快速排序的时间复杂度并不稳定。

快速排序的期望复杂度是O(nlogn)，但最坏情况下可能就会变成O(n^2)，最坏情况就是每次将一组数据划分为两组的时候，分界线都选在了边界上，使得划分了和没划分一样，最后就变成了普通的选择排序了。

快速排序分为三步分治过程，分解，解决，合并。

分解是将输入数组A[l…r]划分成两个子数组的过程。选择一个p，使得a被划分成三部分，分别是a[l…p-1]，a[p]和a[p+1…r]。并且使得a[l…p-1]中的元素都小于等于（或大于等于）a[p]，同时a[p]小于等于（或大于等于）a[p+1…r]中的所有元素。

解决是调用递归程序，解决分解中划分生成的两个子序列。

合并是递归到最深层，已经不能再划分成更小的子序列了，便开始合并。因为在分解的时候已经比较过大小，每一个父序列分解而来的两个子序列不仅是有序的，而且合并成一个序列之后还是有序的。因为快排可以在输入数组上进行操作，所以合并这一步不需要编写代码。

代码

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10

//p,r为边界,先处理左边再处理右边
void QuickSort(int a[],int p,int r)
{
    if(p<r)
    {
        int q = Partition(a,p,r);
        QuickSort(a,p,q-1);
        QuickSort(a,q+1,r);
    }
}

void Swap(int a[],int left,int right)
{
    int tmp;
    tmp = a[left];
    a[left] = a[right];
    a[right] = tmp;
}

int Partition(int a[],int p,int r)
{
    int i=p,j=r+1;
    //本代码的主元选择的是p到r范围内的最左边的即p下标的数
    int x = a[p];
    while(1)
    {
        //将i和j一个从左，一个从右开始相向而行，使得在相遇之前，i部分都是小于x的数，j部分都是大于x的数。左右找到不匹配的数就互换值。
        while(a[++i]<x && i<r) ;
        while(a[--j]>x) ;
        if(i>=j) break;
        Swap(a,i,j);
    }
    //最后把p和j的下标互换一下就可以保证p到r范围内的数，a[j]左边都是小于a[j]，右边都是大于a[j],但不代表左边有序或者右边有序，只是单纯的比a[j]小或大在一边而已
    a[p]=a[j];
    a[j]=x;
    return j;
}
int main()
{
    int a[] = {7,1,5,6,3,8,2,10,9,4};
    int i;
    QuickSort(a,0,MAXSIZE-1);
    for(i=0;i<MAXSIZE;i++)
    {
        printf("%5d",a[i]);
    }
    return 0;
}
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

随机快速排序

上面版本的快排在选取主元的时候，每次都选取最左边的元素。当序列为有序时，会发现划分出来的两个子序列一个里面没有元素，而另一个则只比原来少一个元素。为了避免这种情况，引入一个随机化量来破坏这种有序状态。

在随机化的快排里面，选取a[left…right]中的随机一个元素作为主元，然后再进行划分，就可以得到一个平衡的划分。

代码

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXSIZE 10
//从范围p到r内找一个下标i，把这个数换到最左边，再进行快速排序Partition。
int RandomizedPartition(int a[],int p,int r)
{
    srand(time(NULL));
    int i = rand()%(r-p)+p;
    Swap(a,i,p);
    return Partition(a,p,r);
}
//和QuickSort差不多
void RandomizedQuickSort(int a[],int p,int r)
{
    if(p<r)
    {
        int q = RandomizedPartition(a,p,r);
        RandomizedQuickSort(a,p,q-1);
        RandomizedQuickSort(a,q+1,r);
    }
}




void Swap(int a[],int left,int right)
{
    int tmp;
    tmp = a[left];
    a[left] = a[right];
    a[right] = tmp;
}

int Partition(int a[],int p,int r)
{
    int i=p,j=r+1;
    int x = a[p];
    while(1)
    {
        while(a[++i]<x && i<r) ;
        while(a[--j]>x) ;
        if(i>=j) break;
        Swap(a,i,j);
    }
    a[p]=a[j];
    a[j]=x;
    return j;
}
void QuickSort(int a[],int p,int r)
{
    if(p<r)
    {
        int q = Partition(a,p,r);
        QuickSort(a,p,q-1);
        QuickSort(a,q+1,r);
    }
}
int main()
{
    int a[] = {7,1,5,6,3,8,2,10,9,4};
    int i;
    //QuickSort(a,0,MAXSIZE-1);
    RandomizedQuickSort(a,0,MAXSIZE-1);
    for(i=0;i<MAXSIZE;i++)
    {
        printf("%5d",a[i]);
    }
    return 0;
}
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

两者性能分析

原文链接：https://blog.csdn.net/haelang/article/details/44496387

随机序列

10w：

100w：

1000w：

随机化快排因为要生成随机数，所以有一些性能损失，所以数据规模较小，数据分布均匀时普通快排还是比随机化快排要快些的，不过随着数据规模的上升，随机化快排的性能优势就展现出来了。

有序序列

假设当输入数组已经是排好序的，这两个算法的性能差距又有多少？

之前的数组生成代码不变，只是在调用两个算法之前，先调用一下快排将数组排序，然后将两个有序的数组作为参数传进去。

10w：

1w：

1000w：

看下1000w下随机化快排是否有影响