快速排序之——Hoare方法一实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{
 if(right - left <= 1)
 return;
 
 // 按照基准值对array数组的 [left, right)区间中的元素进行划分
 int div = partion(array, left, right);
 
 // 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
 // 递归排[left, div)
 QuickSort(array, left, div);
 
 // 递归排[div+1, right)
 QuickSort(array, div+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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
int HoareSort(int* arr, int left, int right) {
	int keyi = left;
	while (left < right) {
		//注：在外层while中，left与right是不断变化的，
        //必须保证里层的while中的每一次循环都要符合
		// left<right,因为left可能有与right相遇或者错过的情况，
        //不允许有这种情况发生，否则会出错！！！
	
		//right先走
		while (left < right && arr[right] >= arr[keyi]) {
			--right;
		}
		//left再走
		while (left < right && arr[left] <= arr[keyi]) {
			++left;
		}

		//这时，left与right都找到了比Key...，跳出了循环，然后就开始互换
		if (left < right) {
			Swap(&arr[left], &arr[right]);
		}
		//互换完后再找，直到left>=right跳出大循环，
        //然后把left与right相遇点的位置与keyi互换即可
	}
	int meeti = left;
	Swap(&arr[meeti], &arr[keyi]);
	return meeti;
}

void QuickSort(int* arr, int left,int right) {
	if (left >= right) {
		return;
	}
	int keyi = HoareSort(arr, left, right);
	//递归，通过确定keyi的最终位置，将整个数组从中间分开，
    //keyi左边的为一组,keyi右边的为另一组
	//左边一组继续通过HoareSort进行寻找，排序。。。
    //右边也是如此，最后形成完整的有序数组
	QuickSort(arr, left, keyi - 1);
	QuickSort(arr, keyi + 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
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
59
60
61
//算法优化法1.三数取中
int GetMidIndex(int* a, int left, int right) {
	int mid = (right - left) / 2;
	if (a[left] < a[mid]) {

		if (a[mid] < a[right])
			return mid;
		else if (a[left] > a[right])
			return left;
		else {
			return right;
		}
	}

	else {		                //a[left]>=a[mid]
		if (a[mid] > a[right])
			return mid;
		else if (a[left] < a[right])
			return left;
		else {
			return right;
		}
	}
}

int HoareSort(int* arr, int left, int right) {
	int mid = GetMidIndex(arr, left, right);
	Swap(&arr[left], &arr[mid]);
	int keyi = left;
	while (left < right) {
		

		//right先走
		while (left < right && arr[right] >= arr[keyi]) {
			--right;
		}
		//left再走
		while (left < right && arr[left] <= arr[keyi]) {
			++left;
		}

		//这时，left与right都找到了比Key...，跳出了循环，然后就开始互换
		if (left < right) {
			Swap(&arr[left], &arr[right]);
		}
		
	}
	int meeti = left;
	Swap(&arr[meeti], &arr[keyi]);
	return meeti;
}

void QuickSort(int* arr, int left, int right) {
	if (left >= right) {
		return;
	}

	int keyi = HoareSort(arr, left, right);
	QuickSort(arr, left, keyi - 1);
	QuickSort(arr, keyi + 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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//算法优化法2：小区间优化法

int HoareSort(int* arr, int left, int right) {
	int keyi = left;
	while (left < right) {
		//注：在外层while中，left与right是不断变化的，必须保证里层的while中的每一次循环都要符合
		// left<right,因为left可能有与right相遇或者错过的情况，不允许有这种情况发生，否则会出错！！！
	
		//right先走
		while (left < right && arr[right] >= arr[keyi]) {
			--right;
		}
		//left再走
		while (left < right && arr[left] <= arr[keyi]) {
			++left;
		}

		//这时，left与right都找到了比Key...，跳出了循环，然后就开始互换
		if (left < right) {
			Swap(&arr[left], &arr[right]);
		}
		//互换完后再找，直到left>=right跳出大循环，然后把left与right相遇点的位置与keyi互换即可
	}
	int meeti = left;
	Swap(&arr[meeti], &arr[keyi]);
	return meeti;
}

void QuickSort(int* arr, int left,int right) {
	if (left >= right) {
		return;
	}
	//当区间的长度小于等于某一长度时，使用直接插入算法进行排序，若还是使用递归快排，有些小题大做，杀鸡焉用牛刀了
	//因为小区间的的递归快排次数很少，递归又是那种浪费栈区空间，若是递归的多了，会栈溢出，所以能得话，就少递归
	if (right - left <= 8) {
		InsertSort(arr, right - left + 1);
	}

	//对于大于某一长度的区间长度，则还是使用递归快排
	else {
		int keyi = HoareSort(arr, left, right);
		//递归，通过确定keyi的最终位置，将整个数组从中间分开，keyi左边的为一组,keyi右边的为另一组
		//左边一组继续通过HoareSort进行寻找，排序。。。右边也是如此，最后形成完整的有序数组
		QuickSort(arr, left, keyi - 1);
		QuickSort(arr, keyi + 1, right);
	}
}