顾名思义，快速排序对于大多数数组的排序效率很高。 快速排序适合数据量比较大的数组的排序。 但是，在对一些基本序列结构（例如元素少于 25 个的序列结构）进行排序时效率较低。 数组排序的效率甚至低于插入排序。

对于快速排序，常见的有两种版本：1.传统方法——版本2.挖掘法。

两种方法思路相似，其中挖掘法效率稍高。

代码思路（先以版本为例）：

1. 数组的第一个元素标记为低，最后一个元素标记为高。 不妨将第一个元素作为关键位置key，找到该元素合适的位置。

2. 找到关键字key要插入的位置（即在该数组中排列元素6）。 假设理想的位置已经安排好了：按键左边小于6，右边大于6，我们已经安排好了。 6这个元素。

具体方法：

我们先从最右边看一下。 如果大于6，可以忽略，即high--可以使用； 如果小于6，则交换。

再从最左边看，如果小于6，可以忽略，即可以使用low++； 如果大于6，则进行交换。

然后如此往复循环，我们就会找到适合6的位置！

3、可以对元素6的左右两端进行排序，并安排好各个元素的位置，即可完成整个数组的排序：

显然，这需要对左右数组进行递归。

挖坑方式和版本的区别在于，不使用交换，而是保存低值，释放低位，以便将高值分配给它。 这时候高位就空闲了，方便分配高位值。 low的值被赋值，当low=high时，key被赋值。

代码：

void QuickSort(int arr[], int low, int high)
{
	if (low >= high)
		return;
	int key = partition(arr, low, high);//找位置，每次只能排一个位置，其余数组位置排位则需要递归
	QuickSort(arr, low, key-1);
	QuickSort(arr, key + 1, high);
}
//1.传统法--horare版本
int partition(int* arr, int low, int high)
{
	int key = arr[low];//此题中，key会在low和high直接反复横跳
	while (low < high)//大循环内先右后左，每次仅进行一次交换
	{
		while (low < high && arr[high] >= key)//满足要求则向左靠，注意：在下面high--的过程中，可能会在内循环中出现low>high的情况，违背外循环的条件，出现崩溃，所以要加先决条件：low<=high
			high--;
		swap(arr, low,high);//当跳出上述循环时，说明不符合while的条件，此时需要交换
		while (low < high && arr[low] <= key)
			low++;
		swap(arr,low,high);
	}
	return low;
}
//2.挖坑法
//int partition(int* arr, int low, int high)//本质上依然是交换low，high，比传统法效率更高
//{
//	int key = arr[low];//此题中，key的位置会空出来，low为初始坑位
//	while (low < high)//大循环内先右后左
//	{
//		while (low < high && arr[high] >= key)//满足要求则向左靠，注意：在下面high--的过程中，可能会在内循环中出现low>high的情况，违背外循环的条件，出现崩溃，所以要加先决条件：low<=high
//			high--;
//		arr[low]=arr[high];
//
//		while (low < high && arr[low] <= key)
//			low++;
//		arr[high]=arr[low];
//	}
//	arr[low] = key;//找到后再在key的位置进行赋值
//	return low;
//}
void swap(int* arr, int low, int high)
{
	int tmp = arr[low];
	arr[low] = arr[high];
	arr[high] = tmp;
}
void PrintArray(int arr[], int left, int right)
{
	for (int i = left; i < right; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

void main()
{
	int arr[] = { 49,38,65,97,76,13,27,49 };
	int n = sizeof(arr) / sizeof(arr[0]);
	QuickSort(arr, 0, n-1);
	PrintArray(arr, 0, n);
}