快速排序QuickSqrt

以下是我对快排的理解：

一.概念

  快速排序采用分治法，每一次函数的递归都规定左右界限，并且以一个哨兵为基础，然后想办法让这个哨兵左边的值都小于哨兵，右边的值大于哨兵。

二.实现方法

  其实就是不断挖坑的场景，在新的函数开始时，将取最左侧界限的值为哨兵，将它暂存起来，之后我们先从右到左寻找一个比哨兵小的值（每一次寻找，左侧界限不动，右侧界限向左收缩），然后将符合条件的值填入左侧界限。然后将左侧界限向后移动，形成新的左侧界限。
  然后我们开始从左到右寻找一个比哨兵大的值（每一次寻找右侧界限不动，左侧界限向右收缩），然后存放到右侧界限当中去（放心存，因为右侧界限没有动，并且右侧界限的值已经被存放到了之前的左侧界限中）。之后我们将右侧界限向左移动，构成新的右侧界限。
  然后进行循环收缩，直至i == j（左右界限相等）。
  在函数的最后，我们的左右界限到达了同一位置，此时已经满足了左侧界限前的值小于哨兵，右侧界限的值大于哨兵，并且当前
左右侧界限相等到了一块，然后将一开始暂存的哨兵值填入当前所在位置。
  At the end of this function 我们递归调用快排函数，将当前区间一分为二，先递归左侧部分，也就是区间[left，i-1]。
之后再处理右侧部分,也就是区间[i+1，right]。

三.概念图片

四.代码实现

点击查看代码

void QuickSort(int arr[], int left, int right)
{
	int i, j, temp;

	if (left < right) {
		i = left, j = right;
		//temp做哨兵
		temp = arr[left];

		//每一次循环保证左侧界限小于右侧
		while (i < j) {
			//从右向左寻找第一个小于哨兵的值
			while (i < j && arr[j] >= temp) {
				j--;
			}
			//找到了后将值填入左侧界限的位置，并且更新左界限
			if (i < j) {
				arr[i++] = arr[j];
			}
			//从左向右寻找第一个大于哨兵的值
			while (i < j && arr[i] < temp) {
				i++;
			}
			//将值填入右侧界限的位置，并且更新右界限
			if (i < j) {
				arr[j--] = arr[i];
			}
		}

		//i==j了，其左侧和右侧都满足了快排的条件，我们将原来的哨兵的值给当前的位置
		arr[i] = temp;
		//此时我们将当前区间的数组一分为二，先处理左侧，再处理右侧
		QuickSort(arr, left, i - 1);
		QuickSort(arr, i + 1, right);
	}
}

来源链接：https://www.cnblogs.com/xiaobai1523/p/18926248