数组快速排序

快速排序是在数据源中抽取一份数据作为样本，与所有需要排列的数据进行对比，根据需要把比样本小的数据放置到数据源的左侧位置，比样本大的数据放置到数据源的右侧位置。以此来对数据进行排序。具体实现如下：

// 抽取一个元素与所有元素对比，比样本小的置左，比样本大的置右
int findPos(int *arr, int low, int high)
{
	// 抽取第一个元素
	int nIndex = arr[low];
	// 判断low务必小于high才执行操作
	while (low < high)
	{
		// 从最后一个元素比较，如果大于样本数则向前移动，并且low一定要小于high
		// 当条件不成立时跳出while，证明这个元素小于样本数
		while (arr[high] >= nIndex && low < high)
			high--;
		// 跳出后将小于样本的元素赋给第一个元素空出来的位置
		arr[low] = arr[high];
		// 从第一个元素比较，如果小于样本数则向后移动，并且low一定要小于high
		// 当条件不成立时退出while，证明这个元素大于样本数
		while (arr[low] <= nIndex && low < high)
			low++;
		// 跳出后将大于样本的元素赋给之前赋值给第一个元素后空出来的高位位置
		arr[high] = arr[low];
	}
	// 如果以上循环结束，则low与high一定相等。
	// 此时low与high处于小数和大数中间，将数组第low个元素赋值为样本数即可
	arr[low] = nIndex;
	return low;
}
 
void quickSort(int *arr, int low, int high)
{
	// 判断low必须小于high
	if (low < high)
	{
		// 记录第一次抽取样本数后样本数的位置
		int pos = findPos(arr, low, high);
		// 将样本数左侧的数字再次比较，持续递归
		quickSort(arr, low, pos - 1);
		// 将样本数右侧的数组再次比较，持续递归
		quickSort(arr, pos + 1, high);
	}
}