Sail


手在键盘敲很轻


剑指offer-Partition

Preface

《剑指offer》一书中的Partition函数在好些题目中都有出现,思路也是我以前没见过的,记录下。


Partition

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int Partition(int data[], int length, int start, int end) {
if (data == NULL || length <= 0 || start < 0 || end >= length) {
throw "invalid parameters";
}
int index = RandomInRange(start, end);
swap(data[index], data[end]);
int small = start - 1;
for (index = start; index < end; index++) {
if (data[index] < data[end]) {
small++;
if (small != index) {
swap(data[index], data[small]);
}
}
}
small++;
swap(data[small], data[end]);
return small;
}

Partition函数,所做的工作就是选择一个数字(记为x),将数组分为两部分,比x小的移到数组左边,大的移到右边。这里的x,对应small索引指向的元素,也叫做基准数。


以前我写过一篇快速排序的文章快速排序,利用partition又有了新的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
#include <iostream>
#include <exception>
using namespace std;

int RandomInRange(int start, int end)
{
if (end > start)
{
srand(time(NULL));
return start + rand() % (end - start);
}
return start;
}

int Partition(int data[], int length, int start, int end) {
if (data == NULL || length <= 0 || start < 0 || end >= length) {
throw "invalid parameters";
}
int index = RandomInRange(start, end);
swap(data[index], data[end]);
int small = start - 1;
for (index = start; index < end; index++) {
if (data[index] < data[end]) {
small++;
if (small != index) {
swap(data[index], data[small]);

}
}
}
small++;
swap(data[small], data[end]);
return small;
}

void quickSort(int data[], int length, int start, int end) {
if (start == end) {
return;
}
int index = Partition(data, length, start, end);
if (index > start) {
quickSort(data, length, start, index -1);
}
if (index < end) {
quickSort(data, length, index+1, end);
}
}

int main() {
int test[] = {9, 2, 11, 5, 99, 1};
int len = sizeof(test) / sizeof(*test);
quickSort(test, len, 0, len-1);
for(int i = 0; i < len; i++) {
cout<<test[i]<<" ";
}
cout<<endl;
return 0;
}
© 2016-2019. | 由Hexo强力驱动 | 主题Huno | 渝ICP备17002561号 | 不装弱了,我要做大佬