開心生活站

請輸入關鍵字詞

熱門搜索排行

位置：首頁 > IT科技 > 

快速排序算法例題

IT科技1.58W

排序算法是《數據結構與算法》中最基本的算法之一。排序算法可以分爲內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸併排序、快速排序、堆排序、基數排序等。以下是快速排序算法：

快速排序是由東尼·霍爾所發展的一種排序算法。在平均狀況下，排序 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

以下是熱心網友對快速排序算法的補充，僅供參考：

熱心網友提供的補充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 idef 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_arrayif __name__ == "__main__":    array = [21, -17, 1, -27, 41, 17, -5, -49]    sorted_array = quickSort(array)    print("排序前：{array1}排序後：{array2}".format(array1=array, array2=sorted_array))
以上爲快速排序算法詳細介紹，插入排序、希爾排序、選擇排序、冒泡排序、歸併排序、快速排序、堆排序、基數排序等排序算法各有優缺點，用一張圖概括：

快速排序算法例題

快速排序算法例題 第2張

關於時間複雜度

平方階 (O(n2)) 排序 各類簡單排序：直接插入、直接選擇和冒泡排序。

線性對數階 (O(nlog2n)) 排序 快速排序、堆排序和歸併排序；

O(n1+§)) 排序，§ 是介於 0 和 1 之間的常數。 希爾排序

線性階 (O(n)) 排序 基數排序，此外還有桶、箱排序。

關於穩定性

穩定的排序算法：冒泡排序、插入排序、歸併排序和基數排序。

不是穩定的排序算法：選擇排序、快速排序、希爾排序、堆排序。

名詞解釋：

n：數據規模

k："桶"的個數

In-place：佔用常數內存，不佔用額外內存

Out-place：佔用額外內存

穩定性：排序後 2 個相等鍵值的順序和排序之前它們的順序相同

標籤：算法 例題

相關文章