数组快速排序再解

我们以前是写过数组快速排序的例子的，当时因为时间问题并没有详细记录快速排序的过程是怎么样的。本文在此对数组快速排序做一个详解，希望对学习者有所帮助。

快速排序的思想是抽取一个基准数（一般用数组的第一个元素），抽取的这个元素位置空出，用来交换数据。然后声明两个变量 i 和 j 分别指向数组的头和尾的下标。然后优先从数组的右侧一个元素一个元素的与基准数做对比，如果找到比基准数小的数据就放到数组左侧（抽取基准数后空出的位置），放到数组左侧后，这个数据的位置被空出，此时右侧停止对比。开始从左侧对比，左侧 i 指向下标的数据依次和基准数做对比，如果找到了比基准数大的数据，那么就放到后面刚才空出的位置，然后把自己之前的位置再次空出并停止左侧的对比。再次对比右侧，一次重复执行（在一个while循环中就可以做到），最后得到的数据后，i 和 j 记录的下标一定是相等的，并且这个下标的位置上空出的，我们把基准数放到这个空出的位置，这个数组中基准数左侧的都比基准数小，右侧的都比基准数大。此时重点就是再次将基准数坐标的小数组和右边的小数组根据上面的逻辑排序（递归），最终得出排序后的数据。如果你看文字非常繁琐，可以尝试看一下下面的图更容易理解。

【代码实现】

#include <iostream>

using namespace std;

void quick_sort(int arr[], int low, int high)
{
	// 左侧下标不能越过右侧下标
	if (low < high)
	{
		// 定义两个变量分别记录数组的开头和结尾
		int i = low, j = high;
		// 取第一个数据，作为基准数，然后第一个位置空出，用来交换变量
		int temp = arr[low];
		// 左侧下标不能越过右侧下标
		while (i < j)
		{
			// 先从右向左找比基准数小的数据
			// 判断右侧下标的数是否大于基准数，如果大于则持续循环，否则跳出循环
			while (i < j && arr[j] >= temp)
			{
				// 下标左移，左移的过程可能超过左侧下标 i 的位置，所以循环时要判断
				j--;	
			}
			// 判断如果 i 还是 小于 j，那么此时 j 下标的数一定比基准数大
			// 因为如果没有找到比基准数小的数据，那么此时 i 一定等于 j
			if (i < j)
			{
				// 将右侧找到小于基准数的元素放入左侧空出的位置中
				arr[i] = arr[j];
				// 让左侧元素索引后移，因为此时左侧第一个元素已经被排序过了
				i++;
			}

			// 此时该轮到判断左侧的数据是否大于基准数了，过程同上
			while (i < j && arr[i] <= temp)
			{
				// 左侧下标后移
				i++;
			}
			if (i < j)
			{
				arr[j] = arr[i];
				j--;
			}
		}

		// 上面循环走完后，以基准数被准被分割了两半。此时i和j同时指向最终的空位
		// 把基准数放到这个空位中
		arr[i] = temp;
		// 递归，把基准数左侧和右侧的数据再次按上面的方法排序。直到low大于或者等于high
		quick_sort(arr, low, i - 1);
		quick_sort(arr, i + 1, high);
	}
}

int main(int argc, char* argb[])
{
	int arr[] = { 49, 58, 65, 97, 26, 13, 27, 49, 5, 5 };
	quick_sort(arr, 0, sizeof(arr) / sizeof(int) - 1);

	for (int i = 0; i < sizeof(arr) / sizeof(int) - 1; i++)
	{
		cout << arr[i] << " ";
	}

	return 0;
}