快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void quickSort(vector<int>& array, int left, int right) {
int i = left;
int j = right;
int temp = array[left];
while (i != j) {
while (i <j && temp <= array[j]) j --;
if (i < j) array[i] = array[j];
while (i < j && temp > array[i]) i ++;
if (i < j) array[j] = array[i];
}
array[i] = temp;
quickSort(array, left, i - 1);
quickSort(array, i + 1, right);
}

分治思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int partition(vector<int>& array, int left, int right) {
int i = left;
int j = right;
int temp = array[left];
while (i != j) {
while (i <j && temp <= array[j]) j --;
if (i < j) array[i] = array[j];
while (i < j && temp > array[i]) i ++;
if (i < j) array[j] = array[i];
}
array[i] = temp;
return i;
}
void quickSort(vector<int>& array, int left, int right) {
if (left < right) {
int dp = partition(array, left, right);
quickSort(array, left, dp - 1);
quickSort(array, dp + 1, right);
}
}