题目

click here

题解

传统快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void quickSort(int a[], int l, int r) {
   
	if(l >= r) return ;
	int bas = a[l];
	int i = l, j = r;
	while(i < j) {
   
		while(i < j && a[j] >= bas) j --;
		a[i] = a[j];
		while(i < j && a[i] <= bas) i ++;
		a[j] = a[i];
	}
	a[i] = bas;
	quickSort(a, l, i-1);
	quickSort(a, i+1, r);
}

Hack数据1

严格单调有序的数组 时间复杂度会退化为O(n2) 解决方案：随机化数组或者随机取基准值（而非第一个）

1
2
int id = l + rand() % (r - l + 1);
int bas = a[id];

Hack数据2

所有数据都相等的数组 时间复杂度会退化为O(n2) 解决方案： 三路排序（详解点击）

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
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void swap(int *a, int *b) {
   
    int temp = *a;
    *a = *b;
    *b = temp;
}
void quickSort(int a[], int l, int r) {
   
	if(l >= r) return ;
    int index = l + rand()%(r - l + 1);
    swap(&a[l], &a[index]);
	int bas = a[l];
	int i = l, j = r, k = l + 1;
	while(k <= j) {
   
        if(a[k] == bas) k ++;
        else if(a[k] < bas) {
   
            swap(&a[k], &a[i]);
            i ++;
            k ++;
        }
        else {
   
            swap(&a[k], &a[j]);
            j --;
        }
    }
	quickSort(a, l, i-1);
	quickSort(a, j + 1, r);
}
int* sortArray(int* nums, int numsSize, int* returnSize){
   
    int i;
    quickSort(nums, 0, numsSize-1);
    *returnSize = numsSize;
    return nums;
}