排序算法三之谈一谈快排优化和二分查找

Posted on | In

快速排序

与归并排序一样， 快排也是用了分治的思想。

特别注意 : 快排的核心模块是Partition, 而Partition的复杂度为O(N).

你可以想象一个两副牌然后随意取出一张牌pivot，其他的所有牌都跟这张pivot牌比较，

大的放右边那一摞A，小的放左边B。
接着再从左边这一摞B再随意取出一张牌pivot，其他的所有牌都跟这张pivot牌比较，

大的放右边那一摞，小的放左边，递归下去。
A也重复上述步骤递归。

递归结束之后， 左边的都比右边的小， 而且是有序的。

效率很差的情况

对于分治算法，当每次划分时，算法若都能分成两个等长的子序列时，那么分治算法效率会达到最大。也就是说，基准的选择是很重要的。选择基准的方式决定了两个分割后两个子序列的长度，进而对整个算法的效率产生决定性影响
所以当如果一个有序递增序列, 每次选基准都选最后一个, 那肯定效率很差了啊

算法导论的快排C++实现版本

. . .

这个c++实现版本主要用于说明算法思想, 而对于代码鲁棒性有太多关注,
下面有个我自己手写的命名清晰版本会比较多的关注鲁棒性以及易读性

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
void swap(int *a, int *b)
{
    int temp = 0;
    temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int *array, int p, int r)
{
    int i = 0, j = 0, pivot = 0;
    pivot = array[r];
    i = p-1;
    for(j=p; j<=r-1; j++)
    {
        if(array[j] <= pivot)
        {
	        i++;
            swap(&array[i], &array[j]);
        }
    }
    swap(&array[i+1], &array[r]);
    return i+1;
}

/*
通常，我们可以向一个算法中加入随机化成分，以便对于所有输入，
它均能获得较好的平均情况性能。将这种方法用于快速排序时，
不是始终采用A[r]作为主元，而是从子数组A[p..r]中随机选择一个元素，
即将A[r]与从A[p..r]中随机选出的一个元素交换。
*/
 int rand_patition(int  test_arr[], int p, int r)
 {
	srand(static_cast<unsigned>(time(nullptr)));
	int rand_index = (rand() % (r - p) ) + p + 1;
	swap(&test_arr[rand_index], &test_arr[r]);
	return partition(test_arr, p, r);
 }

void quick_sort(int *array, int p, int r)
{
    int q = 0;
    /*if(p < r)
    {
        q = rand_patition(array, p, r);
        quick_sort(array, p, q-1);
        quick_sort(array, q+1, r);
    }*/

    // 以上的注释部分可以写成尾递归的方式来优化
    while (p < r)
    {
        q = rand_patition(array, p, r);
        quick_sort(array, p, q-1);
        p = q + 1;
    }
}