快速排序的由来
快速排序是由英国计算机科学家 Tony Hoare 在1960年提出的。当时，Hoare是一名在英国皇家空军的研究员，他发表了一篇名为《Algorithm 64: Quicksort》的论文，详细介绍了这种排序算法。
在那篇论文中，Hoare描述了一种高效的排序算法，他称之为“快速排序”。这个算法的思想相对简单，但却非常高效。Hoare提出的快速排序在当时引起了广泛的关注，并且被证明是一种非常有效的排序算法，因为它的平均时间复杂度为 O(n log n)，并且在实际应用中表现出色。
快速排序的成功，使得它成为了计算机科学领域中最经典、最常用的排序算法之一。它被广泛应用于各种编程语言的标准库中，同时也是计算机科学课程中的一个重要主题。
快速排序的思想
假设我们排升序 快速排序需要选定一个基准作为key然后将左边区间的数调为比key小，将右边区间的数调为比key大，然后对左右区间进行递归分治，具体是怎么做到的呢？ 动图展示：
这里最后key移到了L和R相遇的位置，从动图中可以看到，如果我选择首元素作为基准的话，那么我们就得让R先移动，这样才能保证R和L相遇的位置比key小，这里我们来证明一下： 假设有两种情况： 1.L遇R:首先R先移动的话，当R遇到比key小的就停止，意思就是L遇R的话，R必须先停止才能让L遇R，又因为R停下来的数比key要小，所以当L遇到R的时候一定能保证相遇的位置比key小。 1.R遇L: 分两种情况： 第一种也是最容易想到的一种：当R向右移动一直没有找到比key小的最后R和key重合，这也是一种情况。 第二种情况：当R移到一个比key小的元素的时候停下来了，然后L遇到了比key大的元素也停下来了，然后两个元素进行交换，交换了之后R又移动，R移动，假设与L相遇了，那么相遇的地方也是上一轮交换过去比key小的数。 所以基于这两种情况的讨论，我们可以简单的得出：R和L相遇的位置肯定比Key小
注意：以上分析是建立在排升序的基础上讨论的
快速排序的实现
注意：我们上面实现的是单趟排序 接下来我们将对剩下的两个区间进行讨论：
由于L和R移动了，所以我们提前需要把L和R的初始位置保存起来，这样方便后面进行递归，可以用变量begin来保存L，用变量end来保存R的初始位置。
用变量保存了L和R的初始位置之后，就分成了两个区间，[begin,key-1]和[key 1,end],接下来递归的思路就清晰了，我们可以不断进行分治直到区间的长度为0就是L==R还有就是L>R也是也是停止的情况
准备工作完了，接下来完成代码：
void QuickSort(int* a, int left, int right)
{
int key = left;
while (left < right)
{
while (a[right] >= a[key])
{
right--;
}
while (a[left] <= a[key])
{
left ;
}
Swap(&a[left], &a[right]);
}
Swap(&a[key], &a[right]);
}基本框架就是如上代码，接下来来完善递归部分：
代码语言：javascript复制void QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int begin = left;
int end = right;
int key = left;
while (left < right)
{
while (a[right] >= a[key])
{
right--;
}
while (a[left] <= a[key])
{
left ;
}
Swap(&a[left], &a[right]);
}
Swap(&a[key], &a[right]);
key = left;
QuickSort(a, begin, key);
QuickSOrt(a, key, end);
}上面代码就是一个完整的快速排序。
总结
总的来说快速排序是一个非常经典的排序算法，在实用性方面有很大的价值，C语言的库函数qsort也是利用的快速排序，快速排序具有很重要的学习价值
