【经典排序算法】快速排序法 (动图演示 + C 语言代码实现)

?‍? ? 【经典排序算法】十大经典排序算法汇总篇

1、动图演示

2、排序的思想

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

快速排序算法的基本原理为通过一次排序将要排序的数据分割成独立的两部分，将序列分为两部分的中间数作为基准(par)，基准左边的数都要比基准右边的数要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

换句话说,快速排序其实是在冒泡排序的基础上做出的一个改进。它利用的是一趟快速排序,基本内容是选择一个数作为基准，然后利用这个基准将遗传数据分为两个部分，第一部分比这个基准数小放其左侧，第二部分都比这个基准数大放其右侧。

将区间按照基准值划分为左右两半部分的常见方式有：1.hoare法 2.挖坑法 3.前后指针法

(1) hoare法

让begin从前往后找比基准值大的元素，找到之后停止；让end从后往前找比基准值小的元素，找到之后停止；如果begin和end没有相遇：将begin位置上的元素和end位置上的元素进行交换；循环结束后将基准值和begin位置上的元素进行交换。

(2) 挖坑法

让begin从前往后找比基准值大的元素，找到之后停止，将begin位置上的元素覆盖掉end位置上的元素（begin填end的坑，填完之后begin形成新的坑）；让end从后往前找比基准值小的元素，找到之后停止；将end位置上的元素覆盖掉begin位置上的元素,end形成新坑；最后用基准值填最后一个坑。

(3) 前后指针法

cur一直向前遍历，只有cur位置上的值比基准值小时，prev向前遍历。当cur和prev之间有差距，说明两者之间都为比基准值大的元素，交换cur和prev上的元素。最后将基准值和prev最后停下来位置上的元素进行交换。

3、时间复杂度和空间复杂度

• 时间复杂度：$O(n{\log }_{2}n)$
• 空间复杂度：$O(n{\log }_{2}n)$
• 稳定性：不稳定

4、代码实现（C 语言）

int Partition(int array[], int left, int right)
{
	int d = left,temp;
	for (int i = left; i < right; i++)
	{
		
		if (array[i] < array[right])
		{
			temp = array[i];
			array[i] = array[d];
			array[d] = temp;

			d++;
		}
	}
	temp = array[d];
	array[d] = array[right];
	array[right] = temp;
	return d;
}
void QuickSortInner(int array[], int left, int right)
{
	if (left == right)
	{   //相等则是size == 1的情况
		return;
	}
	if (left > right)
	{   //size == 0
		return;
	}
	int div = Partition(array, left, right);

	QuickSortInner(array, left, div - 1);
	QuickSortInner(array, div + 1, right);
}
void QuickSort(int array[], int size)
{
	QuickSortInner(array, 0, size - 1);
}