1.6 快速排序

分类算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 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. 动图演示

代码实现

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]) {
            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;
}

Python

实例

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 arr

def 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-1

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

Go

实例

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]
}

C++

实例

//严蔚敏《数据结构》标准分割函数
 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);
  }
 }

Java

实例

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;
    }

}

PHP

实例

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);
}

C

实例

typedef struct _Range {
  int start, end;
} Range;

Range new_Range(int s, int e) {
  Range r;
  r.start = s;
  r.end = e;
  return r;
}

void swap(int *x, int *y) {
  int t = *x;
  *x = *y;
  *y = t;
}

void quick_sort(int arr[], const int len) {
  if (len <= 0)
    return; *// 避免len等於負值時引發段錯誤（Segment Fault）*
  *// r[]模擬列表,p為數量,r[p++]為push,r[--p]為pop且取得元素*
  Range r[len];
  int p = 0;
  r[p++] = new_Range(0, len - 1);
  while (p) {
    Range range = r[--p];
    if (range.start >= range.end)
      continue;
    int mid = arr[(range.start + range.end) / 2]; *// 選取中間點為基準點*
    int left = range.start, right = range.end;
    do {
      while (arr[left] < mid) ++left;  *// 檢測基準點左側是否符合要求*
      while (arr[right] > mid) --right; *//檢測基準點右側是否符合要求*
      if (left <= right) {
        swap(&arr[left], &arr[right]);
        left++;
        right--;        *// 移動指針以繼續*
      }
    } while (left <= right);
    if (range.start < right) r[p++] = new_Range(range.start, right);
    if (range.end > left) r[p++] = new_Range(left, range.end);
  }
}

递归法

实例

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 <typename T> // 整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)、"大於"(>)、"不小於"(>=)的運算子功能
void quick_sort(T arr[], const int len) {
  if (len <= 0)
    return; // 避免len等於負值時宣告堆疊陣列當機
  // r[]模擬堆疊,p為數量,r[p++]為push,r[--p]為pop且取得元素
  Range r[len];
  int p = 0;
  r[p++] = Range(0, len - 1);
  while (p) {
    Range range = r[--p];
    if (range.start >= range.end)
      continue;
    T mid = arr[range.end];
    int left = range.start, right = range.end - 1;
    while (left < right) {
      while (arr[left] < mid && left < right) left++;
      while (arr[right] >= mid && left < right) right--;
      std::swap(arr[left], arr[right]);
    }
    if (arr[left] >= arr[range.end])
      std::swap(arr[left], arr[range.end]);
    else
      left++;
    r[p++] = Range(range.start, left - 1);
    r[p++] = Range(left + 1, range.end);
  }
}

递归法

实例

template <typename T>
void quick_sort_recursive(T arr[], int start, int end) {
  if (start >= end)
    return;
  T 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--;
    std::swap(arr[left], arr[right]); //交换元素
  }
  if (arr[left] >= arr[end])
    std::swap(arr[left], arr[end]);
  else
    left++;
  quick_sort_recursive(arr, start, left - 1);
  quick_sort_recursive(arr, left + 1, end);
}
template <typename T> //整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)、"大於"(>)、"不小於"(>=)的運算子功能
void quick_sort(T arr[], int len) {
  quick_sort_recursive(arr, 0, len - 1);
}

参考地址:

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

上方没有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;
    }
}

艾孜尔江艾孜尔江 bju*ft@sina.com5个月前 (10-08)

霍旺

xxx*x@aliyun.com

1

补充 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(","))

} ```

总结

1.6 快速排序

分类算法

1. 算法步骤

2. 动图演示

代码实现

JavaScript

实例

Python

实例

Go

实例

C++

实例

Java

实例

PHP

实例

C

实例

实例

C++

实例

实例

results matching ""

No results matching ""

1.6 快速排序

分类 算法

1. 算法步骤

2. 动图演示

代码实现

JavaScript

实例

Python

实例

Go

实例

C++

实例

Java

实例

PHP

实例

C

实例

实例

C++

实例

实例

results matching ""

No results matching ""

分类算法