快速排序以及第k小元素的线性选择算法

时间：2022-11-25 08:55:56

简要介绍下快速排序的思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。时间复杂度为O(nlogn)

一.《data structure and algorithm analysis in c》中的实现，测试过，觉得该说明的已经注释

 C++ Code 
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
71
72
73
74
75
76
77
78
79
80
81
82
83
 
#include<stdio.h>
#define LEN 15
#define CUTOFF 3
//用c++则可以写成引用
void swap(int *const p1, int *const p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}
//插入排序
void insertion_sort(int a[], int n)
{
    int i, j;
    int tmp;
    for (i = 1; i < n; i++)
    {
        tmp = a[i];
        for (j = i; j > 0 && a[j - 1] > tmp; j--)
            a[j] = a[j - 1];
        a[j] = tmp;
    }
}

// return median of left, center, and right
// order these and hide the pivot
int median3(int a[], int left, int right)
{
    int center = (left + right) / 2;
    if (a[left] > a[center])
        swap(&a[left], &a[center]);
    if (a[left] > a[right])
        swap(&a[left], &a[right]);
    if (a[center] > a[right])
        swap(&a[center], &a[right]);
    //  invariant: a[left] <= a[center] <= a[right]
    swap(&a[center], &a[right - 1]);   //将中位数作为pivot且放置在right-1处
    return a[right - 1];                        //返回pivot
}

void qsort(int a[], int left, int right)
{
    int i, j, pivot;
    if (left + CUTOFF <= right)
    {
        //因为要递归调用，如果不截断判断则会导致数组访问越界进而出现段错误
        // left, left+1, ..., right-2, right-1, right 最极限的情况就是保证
        // left与right中间至少有一个值，即CUTOFF最小要等于2,否则出现段错误
        // CUTOFF=2保证可以取中位数
        // 当CUTOFF=1时不出现段错误，但运行结果是错误的
        pivot = median3(a, left, right);
        i = left;
        j = right - 1;
        for (; ;)
        {
            while (a[++i] < pivot) {} //median函数已经比较了left和right，pivot当前位置为right-1
            while (a[--j] > pivot) {} //故从left+1和right-2开始比较
            if (i < j)
                swap(&a[i], &a[j]);
            else
                break;
        }
        swap(&a[i], &a[right - 1]); //now i is the pivot index in the array
        qsort(a, left, i - 1);
        qsort(a, i + 1, right);
    }
    else   // do an insertion sort on the subarray
        insertion_sort(a + left, right - left + 1);
}

int main(void)
{
    int i;
    int arr[LEN] = {43, 423, 13, 6, 34, 64, 24, 69,
                    32, 28, 432, 641, 4365, 345, 624
                   };
    qsort(arr, 0, LEN - 1);
    for (i = 0; i < LEN; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

二.不对pivot进行中位数取值的简易版本

 C++ Code 
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
 
#include<stdio.h>
#define LEN 15

void swap(int *const p1, int *const p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

void qsort(int a[], int left, int right)
{
    int i, j, pivot;
    pivot = a[right];   //the last item as pivot
    i = left;
    j = right - 1;
    if (left < right)
    {
        for (; ;)
        {
            for (; a[i] < pivot; i++);
            for (; a[j] > pivot; j--);
            if (i < j)
                swap(&a[i], &a[j]);
            else
                break;
        }
        swap(&a[i], &a[right]);   //now i is the pivot index in the array
        qsort(a, left, i - 1);
        qsort(a, i + 1, right);
    }
}

int main(void)
{
    int i;
    int arr[LEN] = {43, 423, 13, 6, 34, 64, 24, 69,
                    32, 28, 432, 641, 4365, 345, 624
                   };
    qsort(arr, 0, LEN - 1);
    for (i = 0; i < LEN; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

三.根据简易快速排序得出的第k小选择算法

 C++ Code 
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
 
#include<stdio.h>
#define LEN 15
#define K 6

void swap(int *const p1, int *const p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

int  qsort(int k, int a[], int left, int right)
{
    int i, j, pivot;
    pivot = a[right];
    i = left;
    j = right - 1;
    for (; ;)
    {
        for (; a[i] < pivot; i++);
        for (; a[j] > pivot; j--);
        if (i < j)
            swap(&a[i], &a[j]);
        else
            break;
    }
    swap(&a[i], &a[right]);  //now i is the pivot index in the array
    //i.e. a[i] is the (i+1)th smallest item
    if (k == i - left + 1)
        return a[i];
    else if (k < i - left + 1)
        return qsort(k, a, left, i - 1); //target before pivot
    else                                           //target after  pivot
        return qsort((k - (i - left + 1)), a, i + 1, right);
}

int main(void)
{
    int arr[LEN] = {43, 423, 13, 6, 34, 64, 24, 69,
                    32, 28, 432, 641, 4365, 345, 624
                   };
    printf("%d\n", qsort(K, arr, 0, LEN - 1));
    return 0;
}

四.中位数之第k小的线性选择算法
实现该算法的步骤如下：
    1.如果n是一个比较小的数，比如n<6，那么只需要对此无序数组进行排序后，即可很容易的得到第K小元素。
此时约束时间T=7。
    2.如果n>5，那么我们将这个无序数组分成五组。此时约束时间T=n/5。
    3.找出每组的中位数，构成集合M。此时的约束时间T=7n/5.
    4.递归的调用selection(M,|M|/2)算法查找上一步中所有中位数的中位数，设为m。此时的约束时间
T=T（n/5）。
    5.用m来分割此时的数组，比较m与其他的（n-1）个数，小于m的数置于左集合L，大于m的数置于右集合R。当
然，中位数m的下标r=|L|+1(|L|是左集合L的个数)。此时的约束时间T=T（n）。

如果r=k,那么返回m。
    如果r<k,那么在小于m的左集合L中递归查找第K小数。

如果r>k,那么在大于m的右集合R中递归查找第K小数。

动态图示参见：http://ds.fzu.edu.cn/fine/resources/FlashContent.asp?id=82

-----------------------------------------------------------------------------------------------------------------------------------------

参考：http://bbs.chinaunix.net/thread-116218-1-1.html
          http://blog.csdn.net/fengchaokobe/article/details/6784721
          http://ds.fzu.edu.cn/fine/resources/FlashContent.asp?id=82

中位数之第K小的线性选择算法

1973年，Blum、Floyd等几位大仙合并一体，写了一篇题为 “Time bounds for selection” 的章，给出了一种在数组中选出第k小元素的算法，俗称"中位数之中位数算法"。该算法从理论上保证了最坏情形下的线性时间复杂度（O(n)）。而一个简单的排序算法像快速排序的时间复杂度是O(nlogn)，利用类似于快速排序的做法是：首先对该无序数组进行排序（O(nlogn)），然后进行一次遍历（O(k)）就可以找到第k小元素。下面我们来重点看看中位数排序法。

该算法使用分而治之的策略，查找到第K小元素在最坏情况下的时间复杂度为O(n)。

实现该算法的步骤如下：

1.如果n是一个比较小的数，比如n<6，那么只需要对此无序数组进行排序后，即可很容易的得到第K小元素。

此时约束时间T=7。

2.如果n>5，那么我们将这个无序数组分成五组。此时约束时间T=n/5。

3.找出每组的中位数，构成集合M。此时的约束时间T=7n/5.

4.递归的调用selection(M,|M|/2)算法查找上一步中所有中位数的中位数，设为m。此时的约束时间

T=T（n/5）。

5.用m来分割此时的数组，比较m与其他的（n-1）个数，小于m的数置于左集合L，大于m的数置于右集合R。当

然，中位数m的下标r=|L|+1(|L|是左集合L的个数)。此时的约束时间T=T（n）。

如果r=k,那么返回m。

如果r<k,那么在小于m的左集合L中递归查找第K小数。

如果r>k,那么在大于m的右集合R中递归查找第K小数。

递归方程：T(n)=O(n) + T(n/5) + T(7n/10) （证明过程略）

如果你想知道怎样得到次方程的，不妨找一本关于算法的书看一看或直接给我留言，谢谢！

另外，我想说的是：我为什么分为五组而不是分为其他的组。

假设我们将此数组分为三组，那么有：T(n) = O(n) + T(n/3) + T(2n/3) so T(n) > O(n)。如果我

们将此数组分成五组以上，那么就会显得有些麻烦了，所以分为五个组是最理性的选择。

由于鄙人的翻译水平所致，文中不妥之处还望各位指出来，谢谢！

相关文章