前言：我将持续输出对你有用文章，欢迎关注！

查尔斯·安东尼·理查德·霍尔爵士，昵称东尼·霍尔

快速排序（Quick Sort）是由图灵奖得主东尼·霍尔（Tony Hoare）所提出的一种排序算法。在平均状况下，排序 n 个元素要次比较。在最坏状况下则需要 次比较，但这种状况并不常见。

快速排序使用分治法（Divide and conquer）策略来把一个列表（list）分为两个子列表（sub-lists），然后递归地排序两个子列表。

“快速排序”只是一个名字而已，以后会有人取“最快排序”吗？不过，目前快速排序算法通常比其他 算法更快，原因请看 开发人员网 - 编程入门教程 《哪种排序算法最快》。

JavaScript 语言实例

Python 语言实例

Go 语言实例

Java 语言实例

PHP 语言实例

C 语言实例

C++ 语言实例

C# 语言实例

Ruby 语言实例

Swift 语言实例

Objective-C 语言实例

Shell 语言实例

1. 算法步骤挑选基准值：从数列中挑出一个元素（一般会挑选最左边的元素），称为 “基准”（pivot）;分区：对该数列每个元素，比基准值小的放在基准前面，比基准值大的摆在基准的后面（相等的可以到任一边）。遍历完所有元素时，将基准（pivot）移至两个子数列之间。这个过程称为分区（partition）操作；递归排序子数列：递归地（recursive）对第2步得到的两个子数列进行分区操作；

递归到最后，子数列元素为0个或1个，即这个子数列已经被排序好了，此时退出递归。

2. 动图演示

快速排序动图演示

先看下面的颜色说明会更容易理解上面的动图：

黄色为当前的基准值

橙色为已排序好的元素

绿色为比基准值小的元素

紫色为比基准值大的元素

红色表示当前正比较的元素

蓝色表示待比较的元素

各语言实例JavaScript

function quickSort(arr, left, right) {    var len = arr.length,        partitionIndex,        left = typeof left != 'number' ? 0 : left,        right = typeof right != 'number' ? len - 1 : right;    if (left < right) {        partitionIndex = partition(arr, left, right);        quickSort(arr, left, partitionIndex-1);        quickSort(arr, partitionIndex+1, right);    }    return arr;}function partition(arr, left ,right) {     // 分区操作    var pivot = left,                      // 设定基准值（pivot）        index = pivot + 1;    for (var i = index; i <= right; i++) {        if (arr[i] < arr[pivot]) {            //虽然这里i可能会等于index，对自身没必要移动，但没必要加判断，因为加了判断，所有要移动的都要判断，从而带来更大的负担            swap(arr, i, index);            index++;        }    }    swap(arr, pivot, index - 1);    return index-1;}function swap(arr, i, j) {    var temp = arr[i];    arr[i] = arr[j];    arr[j] = temp;}//第二种方法function partition2(arr, low, high) {  let pivot = arr[low];  while (low < high) {    while (low < high && arr[high] > pivot) {      --high;    }    arr[low] = arr[high];    while (low < high && arr[low] <= pivot) {      ++low;    }    arr[high] = arr[low];  }  arr[low] = pivot;  return low;}function quickSort2(arr, low, high) {  if (low < high) {    let pivot = partition2(arr, low, high);    quickSort2(arr, low, pivot - 1);    quickSort2(arr, pivot + 1, high);  }  return arr;}

def quickSort(arr, left=None, right=None):    left = 0 if not isinstance(left,(int, float)) else left    right = len(arr)-1 if not isinstance(right,(int, float)) else right    if left < right:        partitionIndex = partition(arr, left, right)        quickSort(arr, left, partitionIndex-1)        quickSort(arr, partitionIndex+1, right)    return arrdef partition(arr, left, right):    pivot = left    index = pivot+1    i = index    while  i <= right:        if arr[i] < arr[pivot]:            swap(arr, i, index)            index+=1        i+=1    swap(arr,pivot,index-1)    return index-1def swap(arr, i, j):    arr[i], arr[j] = arr[j], arr[i]

func quickSort(arr []int) []int {    return _quickSort(arr, 0, len(arr)-1)}func _quickSort(arr []int, left, right int) []int {    if left < right {        partitionIndex := partition(arr, left, right)        _quickSort(arr, left, partitionIndex-1)        _quickSort(arr, partitionIndex+1, right)    }    return arr}func partition(arr []int, left, right int) int {    pivot := left    index := pivot + 1    for i := index; i <= right; i++ {        if arr[i] < arr[pivot] {            swap(arr, i, index)            index += 1        }    }    swap(arr, pivot, index-1)    return index - 1}func swap(arr []int, i, j int) {    arr[i], arr[j] = arr[j], arr[i]}

public class QuickSort implements IArraySort {    @Override    public int[] sort(int[] sourceArray) throws Exception {        // 对 arr 进行拷贝，不改变参数内容        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);        return quickSort(arr, 0, arr.length - 1);    }    private int[] quickSort(int[] arr, int left, int right) {        if (left < right) {            int partitionIndex = partition(arr, left, right);            quickSort(arr, left, partitionIndex - 1);            quickSort(arr, partitionIndex + 1, right);        }        return arr;    }    private int partition(int[] arr, int left, int right) {        // 设定基准值（pivot）        int pivot = left;        int index = pivot + 1;        for (int i = index; i <= right; i++) {            if (arr[i] < arr[pivot]) {                swap(arr, i, index);                index++;            }        }        swap(arr, pivot, index - 1);        return index - 1;    }    private void swap(int[] arr, int i, int j) {        int temp = arr[i];        arr[i] = arr[j];        arr[j] = temp;    }}

function quickSort($arr){    if (count($arr) <= 1)        return $arr;    $middle = $arr[0];    $leftArray = array();    $rightArray = array();    for ($i = 1; $i < count($arr); $i++) {        if ($arr[$i] > $middle)            $rightArray[] = $arr[$i];        else            $leftArray[] = $arr[$i];    }    $leftArray = quickSort($leftArray);    $leftArray[] = $middle;    $rightArray = quickSort($rightArray);    return array_merge($leftArray, $rightArray);}

// 基本双向快速排序void QuickSort(int *A, int start, int end){    if(start<end){                // 调试时少了这一步，一直报错        int i=start, j=end;        int pivot = A[i];    // 第0个元素作为基准数        while(i<j)        {            while(i<j && A[j]>pivot) j--;            A[i] = A[j];            while(i<j && A[i]<pivot) i++;            A[j] = A[i];        }        A[i] = pivot;          // 基准数归位，i左边为较小数，右边为较大数        QuickSort(A, start, i-1);  // 递归调用，将剩下两部分继续进行快排        QuickSort(A, i+1, end);    }}

 //严蔚敏《数据结构》标准分割函数 Paritition1(int A[], int low, int high) {   int pivot = A[low];   while (low < high) {     while (low < high && A[high] >= pivot) {       --high;     }     A[low] = A[high];     while (low < high && A[low] <= pivot) {       ++low;     }     A[high] = A[low];   }   A[low] = pivot;   return low; } void QuickSort(int A[], int low, int high) //快排母函数 {   if (low < high) {     int pivot = Paritition1(A, low, high);     QuickSort(A, low, pivot - 1);     QuickSort(A, pivot + 1, high);   } }

static void Main(string[] args) {     Console.WriteLine("请输入待排序数列(以\",\"分割):");     string _s = Console.ReadLine();     string[] _sArray = _s.Split(",".ToCharArray());     int _nLength = _sArray.Length;     int[] _nArray = new int[_nLength];     for (int i = 0; i < _nLength; i++)     {         _nArray[i] = Convert.ToInt32(_sArray[i]);     }     var list = _nArray.ToList();     QuickSort(list, 0, _nLength - 1);     foreach (var i in list)     {          Console.WriteLine(i.ToString());     }     while (true)     {         Thread.Sleep(10000);     }} //获取按枢轴值左右分流后枢轴的位置 private static int Division(List<int> list, int left, int right) {     while (left < right)     {         int num = list[left]; //将首元素作为枢轴         if (num > list[left + 1])         {             list[left] = list[left + 1];             list[left + 1] = num;             left++;         }         else         {             int temp = list[right];             list[right] = list[left + 1];             list[left + 1] = temp;             right--;         }         Console.WriteLine(string.Join(",", list));     }     Console.WriteLine("--------------\n");     return left; //指向的此时枢轴的位置 } private static void QuickSort(List<int> list, int left, int right) {     if (left < right)     {         int i = Division(list, left, right);         //对枢轴的左边部分进行排序         QuickSort(list, i + 1, right);         //对枢轴的右边部分进行排序         QuickSort(list, left, i - 1);     } }

class Array   def quick_sort      return self if self.length<=1      k = self[0]      head = 0      tail = self.length - 1      while head < tail         (tail-head).times do            if self[tail] < k               self[tail], self[head] = self[head], self[tail]               break            end            tail = tail - 1         end         (tail-head).times do            if self[head] > k               self[tail], self[head] = self[head], self[tail]               break            end            head = head + 1         end      end      [*(self.slice(0, head).quick_sort), self[head], *(self.slice(head+1, self.length-head-1).quick_sort)]   endend#testtest_len = 20random_array = []test_len.times do   random_array << rand(100)endputs "random_array            = [#{random_array.join(', ')}]"puts "random_array.quick_sort = [#{random_array.quick_sort.join(', ')}]"puts "random_array.sort       = [#{random_array.sort.join(', ')}]"puts "quick_sort #{(random_array.quick_sort == random_array.sort) ? "succeed" : 'failed'}."

    func quickSort(_ list : inout [Int], low : Int , high : Int){        if low >= high{            return        }        var i = low,j = high        let temp = list[low]        while i < j{            while i < j , list[j] >= temp{                j -= 1            }            list[i] = list[j]            while i < j , list[i] <= temp {                i += 1            }            list[j] = list[i]        }        let position = i        list[position] = temp        quickSort(&list, low: low, high: position - 1)        quickSort(&list, low: position + 1, high: high)    }

/** *  快速排序 * *  @param list array */+(void)quickSort:(NSMutableArray *)list{    if (list.count <= 1) {        return;    }    [self quickSort:list startIndex:0 endIndex:list.count-1];}/** *  快速排序 *  任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面 *  再分别对两边的数据进行快速排序 *  @param list  数组 *  @param start 低位索引 *  @param end   高位索引 */+(void)quickSort:(NSMutableArray *)list startIndex:(NSInteger)start endIndex:(NSInteger)end{    if (start >= end) { //低位大于高位，排序结束        return;    }    NSInteger low = start;    NSInteger high = end;    NSInteger key = [[list objectAtIndex:start] integerValue]; //取第一个数作为关键数据    while (low < high) {        //从后往前推，直到找到第一个比关键数据小的值        while ([[list objectAtIndex:high] integerValue] >= key && low < high) {            high--;        }        //将这个值与关键数据对调（关键数据处于low位置），对调完关键数据处于high位置        [list exchangeObjectAtIndex:low withObjectAtIndex:high];        //从前往后推，直到找到第一个比关键数据大的值        while ([[list objectAtIndex:low] integerValue] <= key && low < high) {            low++;        }        //将这个值与关键数据（关键数据已经处于high位置）对调，对调完关键数据处于low位置        [list exchangeObjectAtIndex:high withObjectAtIndex:low];    }    //对关键数据前面的数据进行快速排序    [self quickSort:list startIndex:start endIndex:low-1];    //对关键数据后面的数据进行快速排序    [self quickSort:list startIndex:low+1 endIndex:end];}

#!/bin/bashfunction array(){  local a=(`echo "$@"`)  local s=${a[${#a[@]}-2]}  local t=${a[${#a[@]}-1]}  if [ "$s" -lt "$t" ];  then    i=$s    j=$t    temp=${arr[s]}    while [ "$i" -ne "$j" ]    do       while [[ "$j" -gt "$i" && "${arr[j]}" -ge "$temp" ]]       do         j=$[j-1]       done       mid=${arr[j]}       arr[j]=${arr[i]}       arr[i]=$mid       while [[ "$i" -lt "$j" && "${arr[i]}" -le "$temp" ]]       do         i=$[i+1]       done       mid=${arr[j]}       arr[j]=${arr[i]}       arr[i]=$mid    done    arr[i]=$temp    array arr[*] $s $[i-1]    array arr[*] $[i+1] $t   fi}arr=(13 12 16 14 15 333 3 24 9 14)array arr[*] 0 9echo ${arr[*]}

作者简介：茂子，热爱编程的家伙，欢迎关注。