快速排序

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
int Partition(int a[], int low, int high) {
	int i = low; //为了保证后面操作统一 所以各自留一位
	int j = high + 1;
	while (true) {
		while (a[++i] < a[low])
			if (i == high) break;
		while (a[--j] > a[low])
			if (j == low) break;

		if (i >= j) break;
		Swap(a[i], a[j]);
	}

	Swap(a[j], a[low]);
	return j;
}

void QuickSort(int a[], int low, int high) {
	if (low >= high) return;

	int mid = Partition(a, low, high);
	QuickSort(a, low, mid - 1);
	QuickSort(a, mid + 1, high);
}

快速排序的应用

选择第k个小的元素

平均复杂度为O(n)

1
2
3
4
5
6
7
8
9
10
11
void ComparableSelect(int a[],int k,int n){
	int low = 0;
	int high = n-1;
	while(high>low){
		int mid = Partition(a,low,high);
		if(mid>k) high = mid-1;
		else if(mid<k) low = mid+1;
		else return a[k];
	}
	return a[k]; //为什么有这句，什么情况会出现high<=low
}