本文共 1758 字，大约阅读时间需要 5 分钟。

快速排序的复杂度为O(n*logn)，

1、挖坑法

我们使用两个指针，一个指针指向数组的第一个元素，另一个指针指向数组的最后一个元素。为了方便，选取第一个值作为基准值pivot，进行比较，具体过程如下图： 

代码如下：

/*快速排序，使用两个指针*/#include 
   
    using namespace std;int partition(int a[], int, int);void quickSort(int a[], int, int);int main(){	//待排序数组	int a[10] = { 1, 9, 0, 4, 10, 5, 2, 3, 6, 8 };	for (int i = 0; i < 10; ++i)	{		cout << a[i] << ' ';	}	cout << endl;	quickSort(a, 0, 9);	for (int i = 0; i < 10; ++i)	{		cout << a[i] << ' ';	}	cout << endl;	return 0;}int partition(int a[], int left, int right){	int i = left;	int j = right;	int temp = a[i];	while (i < j)	{		while (i < j && a[j] > temp)		{			j -= 1;		}		if (i < j)		{			a[i] = a[j];		}		while (i < j && a[i] < temp)		{			i += 1;		}		if (i < j)		{			a[j] = a[i];		}	}	a[i] = temp;	return i;}void quickSort(int a[], int left, int right){	if (left < right)	{		int pivot = partition(a, left, right);		quickSort(a, left, pivot);		quickSort(a, pivot + 1, right);	}	return;}
   

我们也可以使用一个指针对数组进行快速排序，如下图所示：

该种划分情况下的快速排序代码如下所示：

#include 
   
    using namespace std;int partition1(int b[], int, int);		//使用一个指针进行划分void quickSort1(int b[], int, int);int main(){	//待排序数组	int b[10] = { 4, 7, 2, 6, 0, 10, 5, 8, 3, 9 };	for (int i = 0; i < 10; ++i)	{		cout << b[i] << ' ';	}	cout << endl;	quickSort1(b, 0, 9);	for (int i = 0; i < 10; ++i)	{		cout << b[i] << ' ';	}	cout << endl;	return 0;}int partition1(int b[], int head, int tail){	int pivot = b[tail];	//选取分组中最后一个元素为基准值	int temp = head;	for (int i = head; i < tail - head; ++i)	{		if (b[i] <= pivot)		{			swap(b[temp], b[i]);			++temp;		}	}	swap(b[tail], b[temp]);	return temp;}void quickSort1(int b[], int head, int tail){	if (head < tail)	{		int pivot = partition1(b, head, tail);		quickSort1(b, head, pivot-1);		quickSort1(b, pivot + 1, tail);	}		return;}
   

转载地址：http://dttai.baihongyu.com/