让你难过的事情，有一天，你一定会笑着说出来。

一.前言

  交换排序总思想：数据两两比较，发生逆序则交换，直到整个数据有序。交换排序又分为冒泡排序和快速排序。本文讲述有关快速排序的知识。

二.快速排序思想

基本思想：
  如果要将一组数据从小到大进行排序，通过一趟排序，将待排序记录分割成独立的两部分，前部分数据都比后部分的数据小，再分别对这两部分进行排序（分治法的思想），以达到整个序列有序。
  举个例子：

  假设有如上的一组数据，蓝色代表中间数据，绿色代表比蓝色小的数据，红色代表比蓝色大的数据。通过一趟快速排序，绿色将会全部在蓝色的左边，红色将会全部在蓝色的右边，如下：

  蓝色就将这组数据分成独立的两部分，其左边的数据（绿色）都比其又变的数据（红色）小。
  那是如何达到上诉效果的呢？就是依次将其它数据和我们选择的中间数据比较，小的就放到它的前面，大的就放到它后面。

三.过程分析

操作过程：
 1. 任取一元素（如：第一个）为中心（pivot）轴
 2. 所有比中心轴小的元素一律前放，比中心轴大的元素一律后放，这样就会形成左右两个子序列
 3. 对各子序列重新选择中心元素并依上述规则调整（递归思想）
 4. 直到每个子序列的元素只剩一个

快速排序图解：
  有如下的一组数据（图形下面的数字代表数组下标），现在需要将其按从小到大进行排序。

  任取一个数据为中心轴。这里选取第一个数据为中心轴，将该位置的数据进行拷贝（拷贝后假设该位置没有数据，方便分析），外加两个指示位置的指示指针low与high，low初始指向被拷贝数据的位置，即中心轴数据的位置，high指向这组数据的最后一个数据，如下：

  此时low所指示的位置没有数据，需要从low与high之间选取一个比中心轴数据（19）小的数据放到该位置。high所指的5号位置25比中心轴数据大，high移动到4号位置，如下：

  所指的四号位置数据比中心轴数据（19）小，则将high所指的4号位置的数据拷贝到low所指的0号位置，如下：

  现在high所指的位置没有数据，需要从low与high两者之间选取一个比中心轴数据（19）大的数据放到high所指的位置。low所指的0号位置8比中心轴数据小，不满足则将low往前移动一个位置，如下：

  再比较low所指的当前位置，满足进行交换，如下：

  接下来还是按照上面的操作进行，从两者之间选取比中心轴数据小的放到low所指的位置，30比19大,不满足，high往往后移动一个位置，如下：

  再与high所指的当前位置进行比较，满足进行交换，如下：

  此时high的位置为空，从两者之间选取比中心轴数据（19）大的放到high的位置，13<19，不满足，low往前移动一个位置，如下：

  再与low所指的当前位置进行比较，满足进行交换，如下：

  此时low的位置又为空，从两者之间选取比中心轴数据（19）小的放到low的位置，49>19，不满足，high往后移动一个位置，如下：

  当low与high重合即相等的时候，本趟排序结束。此时它们所指的位置，即为中心轴数据的插入位置，用红色标记如下：

  这样就形成了以中心轴为分界线的左右两个子序列，对各子序列调用上述同样的操作，包括重新选取中心轴元素等，就不重复演示了，步骤都是一样的。

总结：
 ·对于快速排序都是递归调用同样的操作，则可以用递归算法；
 ·当high于low重合时所指位置即为中心轴数据的位置；
 ·当各子序列只有一个元素的时候，即排序完成。

四.代码实现

  对于快速排序的算法用递归思想来实现。
递归开始结束的条件是： 只有一个元素的时候递归开始结束；
本级递归要为上一级递归返回什么： 返回完成本趟排序后中心轴数据的位置；
递归要完成的任务是： 将比中心轴数据小的移动到其前面，大的移动到其后面。

FastSort函数：

typedef int ElementType;
void FastSort(ElementType array[], int low, int high)
{
	int pivotPos;//中心轴位置
	if (low < high)//子序列元素大于一个，则进行递归调用
	{
		pivotPos = FindPivotPosition(array, low, high);//对数据进行交换并返回中心轴数据位置的功能函数
		FastSort(array, low, pivotPos - 1);//递归左子序列
		FastSort(array, pivotPos + 1, high);//递归右子序列
	}
}

FindPivotPosition函数：

typedef int ElementType;
int FindPivotPosition(ElementType array[], int low, int high)//对数据进行交换，并返回中心轴数据
{
	ElementType pivotKey;//中心轴关键字的值
	pivotKey = array[low];//选取第一个数据作为中心轴关键字的值
	while (low < high)//当low于high重合时，本轮结束
	{
		while (low < high&&array[high]>=pivotKey)//起初low所指位置没有有效数据，要从后面选取一个比中心轴数据小的数据放到low所指位置
		{   
			high--;//不满足则high要往后移动一个位置
		}
		array[low] = array[high];//满足则进行交换
		while (low < high&&array[low]<=pivotKey)//此时high所指位置没有有效数据，要从前面选取一个比中心轴数据大的数据放到high所指的位置
		{
			low++;//不满足则让low往前移动一个位置
		}
		array[high] = array[low];//满足则进行交换
	}
	array[low] = pivotKey;//将中心轴数据插入到high与low重合的位置
	return low;//返回交换完成后中心轴数据的位置
}

//补充：利用递归方式，实现快排
void FastSort(int* nums, int low, int high)
{
	//两个哨兵
	int i = low;
	int j = high;
	int temp;//临时变量用于交换数据
	int pivortKey = nums[low];//中心轴数据
	if (low > high)return;//递归结束的条件
	while (i < j)
	{
		while (i<j && nums[j]>=pivortKey)j--;//在右边寻找一个比中心轴数据小的元素
		while (i < j && nums[i] <= pivortKey)i++;//在左边寻找一个比中心轴数据大的元素
		if (i < j)//当寻找到了满足元素的两个哨兵位置
		{
			temp = nums[i];
			nums[i] = nums[j];
			nums[j] = temp;
		}
	}
	//当两个哨兵相遇时
	nums[low] = nums[i];
	nums[i] = pivortKey;
	//递归遍历
	FastSort(nums, low, i - 1);
	FastSort(nums, i + 1, high);
	return;
}

五.总结

 1.快速排序时间复杂度为O(nlogn),FastSort为O（logn），FindPivotPosition为O（n）；
 2.就平均效率而言快速排序是内部排序方法中效率最好的一个；
 3.快速排序不是原地排序，由于程序中使用了递归，需要递归调用栈的支持，而栈的长度取决于递归调用的深度。（即使不用递归，也需要使用用户栈）；
 4.快速排序是一种不稳定的排序方法；
 5.快速排序不适于对原本有序或基本有序的记录序列进行排序，这样会退化为冒泡排序。

  希望对大家有帮助，我是老胡，感谢阅读！！❤️ ❤️