科技
排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是快速排序算法：
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n?)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好，可是这是为什么呢，我也不知道。好在我的强迫症又犯了，查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：
快速排序的最坏运行情况是 O(n?)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
1. 算法步骤从数列中挑出一个元素，称为 "基准"（pivot）;
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
2. 动图演示
递归法
实例 void swap(int *x, int *y) { int t = *x; *x = *y; *y = t;}void quick_sort_recursive(int arr[], int start, int end) { if (start >= end) return; int mid = arr[end]; int left = start, right = end - 1; while (left < right) { while (arr[left] < mid && left < right) left++; while (arr[right] >= mid && left < right) right--; swap(&arr[left], &arr[right]); } if (arr[left] >= arr[end]) swap(&arr[left], &arr[end]); else left++; if (left) quick_sort_recursive(arr, start, left - 1); quick_sort_recursive(arr, left + 1, end);}void quick_sort(int arr[], int len) { quick_sort_recursive(arr, 0, len - 1);}C++函数法
sort(a,a + n);// 排序a[0]-a[n-1]的所有数.
迭代法
实例 // 参考：http://www.dutor.net/index.php/2011/04/recursive-iterative-quick-sort/struct Range { int start, end; Range(int s = 0, int e = 0) { start = s, end = e; }};template递归法
实例 template参考地址:
https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/6.quickSort.md
https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F
以下是热心网友对快速排序算法的补充，仅供参考：
热心网友提供的补充1：
上方没有C#实现，我补充一下，如下所示：
//快速排序（目标数组，数组的起始位置，数组的终止位置）
static void QuickSort(int[] array, int left = 0, int right = -1)
{
if (right.Equals(-1)) right = array.Length - 1;
try
{
int keyValuePosition; //记录关键值的下标
//当传递的目标数组含有两个以上的元素时，进行递归调用。（即：当传递的目标数组只含有一个元素时，此趟排序结束）
if (left < right)
{
keyValuePosition = Partion(array, left, right); //获取关键值的下标（快排的核心）
QuickSort(array, left, keyValuePosition - 1); //递归调用，快排划分出来的左区间
QuickSort(array, keyValuePosition + 1, right); //递归调用，快排划分出来的右区间
}
}
catch (Exception ex)
{
Console.WriteLine("Exception: {0}", ex);
}
}
///快速排序的核心部分：确定关键值在数组中的位置，以此将数组划分成左右两区间，关键值游离在外。（返回关键值应在数组中的下标）
static int Partion(int[] array, int left, int right)
{
int leftIndex = left; //记录目标数组的起始位置（后续动态的左侧下标）
int rightIndex = right; //记录目标数组的结束位置（后续动态的右侧下标）
int keyValue = array[left]; //数组的第一个元素作为关键值
int temp;
//当 （左侧动态下标 == 右侧动态下标） 时跳出循环
while (leftIndex < rightIndex)
{
while (leftIndex < rightIndex && array[leftIndex] <= keyValue) //左侧动态下标逐渐增加，直至找到大于keyValue的下标
{
leftIndex++;
}
while (leftIndex < rightIndex && array[rightIndex] > keyValue) //右侧动态下标逐渐减小，直至找到小于或等于keyValue的下标
{
rightIndex--;
}
if (leftIndex < rightIndex) //如果leftIndex < rightIndex，则交换左右动态下标所指定的值；当leftIndex==rightIndex时，跳出整个循环
{
temp = array[leftIndex];
array[leftIndex] = array[rightIndex];
array[rightIndex] = temp;
}
}
//当左右两个动态下标相等时（即：左右下标指向同一个位置），此时便可以确定keyValue的准确位置
temp = keyValue;
if (temp < array[rightIndex]) //当keyValue < 左右下标同时指向的值，将keyValue与rightIndex - 1指向的值交换，并返回rightIndex - 1
{
array[left] = array[rightIndex - 1];
array[rightIndex - 1] = temp;
return rightIndex - 1;
}
else //当keyValue >= 左右下标同时指向的值，将keyValue与rightIndex指向的值交换，并返回rightIndex
{
array[left] = array[rightIndex];
array[rightIndex] = temp;
return rightIndex;
}
}热心网友提供的补充2：
补充 scala 实现版本：
/**
* @Auther: huowang
* @Date: 19:34:47 2020/12/10
* @DES: 分区交换算法（快速排序发）
* @Modified By:
*/
object PartitionExchange {
/**
* 分区内切割
* @param arr
* @param left
* @param right
* @return
*/
def partition(arr:Array[Int],left:Int,right: Int):Int={
// 获取基准元素 直接选取最右侧一个元素为基准元素
val pv=arr(right)
// 把最左边一个索引作为堆叠索引
var storeIndex=left
//操作数组 -1是因为 最右边一个元素是基准元素
for (i <- left to right-1 ){
if(arr(i)<=pv){
//把小于基准元素的元素 都堆到集合左端
swap(arr,storeIndex,i)
// 把用于堆叠索引往前移动一个
storeIndex=storeIndex+1
}
//如果出现了比基准元素大的元素,那么则不会移动堆叠索引
// 但是如果之后又出现了比基准元素小的元素,那边会与这个大的元素交换位置
// 进而使大的元素永远出现在堆叠索引右侧
}
// 这里最有右的元素,其实是基准元素,我们把基准元素和最后堆叠索引对应的元素调换位置
// 这样基准元素左边就都是大于它的元素了
swap(arr,right,storeIndex)
// 返回堆叠索引位置,目前堆叠索引指向的就是基准元素
storeIndex
}
def quicksort(arr:Array[Int],left: Int,right: Int):Array[Int]={
if(right>left){
// 左右索引不重合
// 随便选择一个元素作为基准 就选择最左边的吧
var pivotIndex=0
// 切割返回基准元素
pivotIndex= partition(arr,left,right)
// 递归对切割形成的两个子集进行排序
quicksort(arr,left,pivotIndex-1)
quicksort(arr,pivotIndex,right)
}
arr
}
/**
* 调换 a b 元素在数组中的位置
* @param arr
* @param a
* @param b
*/
def swap(arr:Array[Int],a:Int,b:Int)={
val tmp=arr(a)
arr(a)=arr(b)
arr(b)=tmp
}
def main(args: Array[String]): Unit = {
// 测试
val arr=Array(5, 2, 9,11,3,6,8,4,0,0)
val arrNew=quicksort(arr,0,arr.size-1)
println(arrNew.toList.mkString(","))
}
}热心网友提供的补充3：
补充一下迭代法的 python 实现：
def _partition(array:list, start:int, end:int) -> int:
"""
将数组指定片段进行左右划分，首先选择中位元素为中值。
比中位元素小的置于其左，与中位元素相等或比中位元素大的置于其右，
最后返回中位元素的下标位置。
"""
# 以中位元素为中值划分，尽量避免极端情况
mid = (start + end) >> 1
array[start], array[mid] = array[mid], array[start]
# 划分的实现
i, j = start, end
x = array[start]
while (i < j):
if (i < j and array[j] >= x): j -= 1
array[i] = array[j]
if (i < j and array[i] < x): i += 1
array[j] = array[i]
array[i] = x
return i
def quickSort(array:list) -> list:
"""
迭代法快速排序，队列结构辅助实现。
"""
sorted_array = array.copy()
length = len(sorted_array)
# 使用队列保存每次划分的二元组：(起始下标，终止下标)
queue = []
queue.append((0, length - 1))
# 队列为空，则所有划分操作执行完毕
while len(queue):
left, right = queue.pop(0)
pos = _partition(sorted_array, left, right)
# 默认长度为 1 的序列有序，那么区间长度 > 1 才需要划分，才需要保存到队列中
if (left < pos - 1): queue.append((left, pos - 1))
if (pos + 1 < right): queue.append((pos + 1, right))
return sorted_array
if __name__ == "__main__":
array = [21, -17, 1, -27, 41, 17, -5, -49]
sorted_array = quickSort(array)
print("排序前：{array1}
排序后：{array2}".format(array1=array, array2=sorted_array))以上为快速排序算法详细介绍，插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等排序算法各有优缺点，用一张图概括： 
关于时间复杂度
平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。
线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；
O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序
线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。
关于稳定性
稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。
不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。
名词解释：
n：数据规模
k："桶"的个数
In-place：占用常数内存，不占用额外内存
Out-place：占用额外内存
稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同
