快速排序

    快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

    快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

    1. 从数列中挑出一个元素，称为 “基准”（pivot）;

    3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

    递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

    2. 动图演示

    4. Python 代码实现

    2.     left = 0 if not isinstance(left,(int, float)) else left
    3.     right = len(arr)-1 if not isinstance(right,(int, float)) else right
    4.     if left < right:
    5.         partitionIndex = partition(arr, left, right)
    6.         quickSort(arr, left, partitionIndex-1)
    7.         quickSort(arr, partitionIndex+1, right)
    8.     return arr
    10. def partition(arr, left, right):
    11.     pivot = left
    12.     index = pivot+1
    13.     i = index
    14.     while  i <= right:
    15.             swap(arr, i, index)
    16.             index+=1
    17.         i+=1
    18.     swap(arr,pivot,index-1)
    19.     return index-1
    21. def swap(arr, i, j):

    6. C++版

    1.  //严蔚敏《数据结构》标准分割函数
    2.  Paritition1(int A[], int low, int high) {
    3.    int pivot = A[low];
    4.    while (low < high) {
    5.      while (low < high && A[high] >= pivot) {
    6.        --high;
    7.      }
    8.      A[low] = A[high];
    9.      while (low < high && A[low] <= pivot) {
    10.        ++low;
    11.      }
    12.      A[high] = A[low];
    13.    }
    14.    A[low] = pivot;
    15.    return low;
    16.  }
    18.  {
    19.    if (low < high) {
    20.      int pivot = Paritition1(A, low, high);
    22.      QuickSort(A, pivot + 1, high);
    23.    }
    24.  }

    8. PHP 代码实现

    1. function quickSort($arr)
    2. {
    3.     if (count($arr) <= 1)
    4.         return $arr;
    5.     $middle = $arr[0];
    6.     $leftArray = array();
    7.     $rightArray = array();
    9.     for ($i = 1; $i < count($arr); $i++) {
    10.         if ($arr[$i] > $middle)
    11.             $rightArray[] = $arr[$i];
    12.         else
    13.             $leftArray[] = $arr[$i];
    14.     }
    15.     $leftArray = quickSort($leftArray);
    16.     $leftArray[] = $middle;
    18.     $rightArray = quickSort($rightArray);
    19. }