常用快排模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void quick_sort(int q[], int l, int r)
{
    if(l>=r)return;
    int x=q[(l+r)/2],i=l-1,j=r+1;
    while(i<j)
    {
        do i++;while(q[i]<x);
        do j--;while(q[j]>x);
        if(i<j)
        {
            swap(q[i],q[j]);
        }
    }
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}

完整代码

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<iostream>
#include<vector>
#include<cstring>
#include<cstdio>

using namespace std;
template<typename Comp>
void quicksort(vector<Comp>& a, int left, int right);
template<typename Comp>
void quicksort(vector<Comp>& a);
template<typename Comp>
void quicksort(vector<Comp>& a, int left, int right);
template<typename Comparable>
void insertionSort(vector<Comparable>& a, int left, int right);
int main()
{
	vector<int> a = { 8,9,7,6,5,4,3,2,1 };
	int n = a.size();
	quicksort<int>(a);

	for (int i = 0; i < n; i++)
	{
		cout << a[i] << ' ';
	}
	return 0;
};
//快速排序（驱动程序）
template<typename Comp>
void quicksort(vector<Comp>& a)
{
	quicksort(a, 0, a.size() - 1);
}
//返回left、center和right的三项的中值
//将它们排序并隐匿枢纽元
template<typename Comp>
const Comp& median3(vector<Comp>& a, int left, int right)
{
	int center = (left + right) / 2;

	if (a[center] < a[left])
		swap(a[left], a[center]);
	if (a[right] < a[left])
		swap(a[right], a[left]);
	if (a[right] < a[center])
		swap(a[right], a[center]);
	//将枢纽元置于right-1处
	swap(a[center], a[right-1]);
	return a[right - 1];
}
//插入排序
template<typename Comparable>
void insertionSort(vector<Comparable>& a,int left,int right)
{
	for (int p = left; p <= right; p++)//a的下标从0开始
	{
		Comparable temp = move(a[p]);
		int j;
		for (j = p; j > 0 && a[j - 1] > temp; j--)
		{
			a[j] = move(a[j - 1]);
		}
		a[j] = move(temp);
	}
}
/*进行递归调用的内部快速排序方法
* 使用三数中值分割法，以及截至范围是10的截止技术
* 使用截至技术来降低时间复杂度
* left和right分别是数组最左和最右元素的下标
*/
template<typename Comp>
void quicksort(vector<Comp>& a, int left, int right)
{
	if (left + 10 <= right)
	{
		const Comp& pivot = median3(a, left, right);

		//开始分割
		int i = left, j = right - 1;
		for (;;)
		{
			while (a[++i] < pivot) {}
			while (pivot < a[--j]) {}
			if (i < j)
				swap(a[i], a[j]);
			else
				break;
		}
		swap(a[i], a[right - 1]);//恢复枢纽元
		quicksort(a, left, i - 1);//将小于等于枢纽元的元素排序
		quicksort(a, i + 1, right);//将大于等于枢纽元的元素排序
	}
	else//将子数组进行一次插入排序
		insertionSort(a, left, right);
}

快速排序函数

median3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//返回left、center和right的三项的中值
//将它们排序并隐匿枢纽元
template<typename Comp>
const Comp& median3(vector<Comp>& a, int left, int right)
{
	int center = (left + right) / 2;

	if (a[center] < a[left])
		swap(a[left], a[center]);
	if (a[right] < a[left])
		swap(a[right], a[left]);
	if (a[right] < a[center])
		swap(a[right], a[center]);
	//将枢纽元置于right-1处
	swap(a[center], a[right-1]);
	return a[right - 1];
}

insertionSort

当数组长度较短时使用插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//插入排序
template<typename Comparable>
void insertionSort(vector<Comparable>& a,int left,int right)
{
	for (int p = left; p <= right; p++)//a的下标从0开始
	{
		Comparable temp = move(a[p]);
		int j;
		for (j = p; j > 0 && a[j - 1] > temp; j--)
		{
			a[j] = move(a[j - 1]);
		}
		a[j] = move(temp);
	}
}

quicksort

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
/*进行递归调用的内部快速排序方法
* 使用三数中值分割法，以及截至范围是10的截止技术
* 使用截至技术来降低时间复杂度
* left和right分别是数组最左和最右元素的下标
*/
template<typename Comp>
void quicksort(vector<Comp>& a, int left, int right)
{
	if (left + 10 <= right)
	{
		const Comp& pivot = median3(a, left, right);

		//开始分割
		int i = left, j = right - 1;
		for (;;)
		{
			while (a[++i] < pivot) {}
			while (pivot < a[--j]) {}
			if (i < j)
				swap(a[i], a[j]);
			else
				break;
		}
		swap(a[i], a[right - 1]);//恢复枢纽元
		quicksort(a, left, i - 1);//将小于等于枢纽元的元素排序
		quicksort(a, i + 1, right);//将大于等于枢纽元的元素排序
	}
	else//将子数组进行一次插入排序
		insertionSort(a, left, right);
}
1
2
3
4
5
6
//快速排序（驱动程序）
template<typename Comp>
void quicksort(vector<Comp>& a)
{
	quicksort(a, 0, a.size() - 1);
}

时间复杂度分析

细节注意

需要在while循环的判断条件里作自增自减操作，否则若a[i]=a[j]=pivot时会出现无限循环不断地交换a[i]和a[j]而无法跳出for循环