067_排序_快速排序算法_总结

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. 算法步骤

1. 从数列中挑出一个元素，称为 “基准”（pivot）;
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

3. 递归地（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 // 整數或浮點數皆可使用,若要使用物件(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 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 //整數或浮點數皆可使用,若要使用物件(class)時必須設定”小於”(<)、”大於”(>)、”不小於”(>=)的運算子功能 void quick_sort(T arr[], int len) { quick_sort_recursive(arr, 0, len - 1); }

![哔哩哔哩动画](https://cdn.nlark.com/yuque/0/2021/png/2460262/1635357300795-f7479ad6-d07f-451e-890c-d57f2c5d62ad.png)
> 参考地址:
> [https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/6.quickSort.md](e12d070972ee8cc0e5eedf6b873f98d9)
> [https://zh.wikipedia.org/wiki/快速排序](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;
}

}

[艾孜尔江](javascript:;)  艾孜尔江 bju***ft@sina.com5个月前 (10-08)
1.

霍旺

xxx*x@aliyun.com

1<br />补充 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(“,”))

} }

```