iT邦幫忙

2021 iThome 鐵人賽

DAY 26
2
Software Development

資料結構與演算法,使用JavaScript與Python系列 第 26

【Day26】[演算法]-快速排序法Quick Sort

快速排序法(Quick Sort)又稱分割交換排序法,是目前公認效率極佳的演算法,使用了分治法(Divide and Conquer)的概念。原理是先從原始資料列中找一個基準值(Pivot),接著逐一將資料與基準值比較,小於基準值的資料放在左邊,大於基準值的資料放在右邊,再將兩邊區塊分別再找出基準值,重複前面的步驟,直到排序完為止。

常用的基準值(Pivot)選擇方式:

  • 選擇第1筆或最後1筆的資料
  • 隨機亂數
  • 三數中位數(Median-of-three),第一、中間、最後筆資料,排序之後取中間的值(Musser, 1997)。
    例如: 1,5,9,6,3,取出1,9,3,排序後1,3,9,取3為基準點。

平均時間複雜度為: O(n log n)

由於快速排序法有多種實作版本,下面介紹常見的3種實作版本。


遞迴版本

此版本雖然容易理解,但會影響到空間複雜度,每次都需要申請兩個子數列的記憶體空間,遞迴的深度越多,需要記憶體空間就越大。

操作流程:

  1. 資料列中找出一個基準值(Pivot)
  2. 將小於Pivot的資料放在左邊,大於Pivot的資料放在右邊
  3. 左右兩邊資料分別重複1~2步驟,直到剩下1筆資料
  4. 合併

下面利用50 90 70 20 10 30 40 60 80由小到大排序。
https://ithelp.ithome.com.tw/upload/images/20211007/20121027Rj3YsKAi1Q.jpg

JavaScript

let data = [50,90,70,20,10,30,40,60,80]

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  let left = [];
  let right = [];
  let pivot = arr[0];
  for (let i = 1; i < arr.length; i++) {
    let num = arr[i];
    if (num < pivot) {
      left.push(num);
    } else {
      right.push(num);
    }
  }
  return [...quickSort(left), pivot, ...quickSort(right)];
}
console.log(quickSort(data))//[10, 20, 30, 40, 50, 60, 70, 80, 90]

Python

#Quick Sort
def QuickSort(arr):
    n = len(arr)
    if n <= 1:
        return arr
    left = []
    right = []
    pivot = arr[0]
    for i in range(1,n):
        if arr[i] < pivot:
            left.append(arr[i])
        else:
            right.append(arr[i])
    return QuickSort(left) + [pivot] + QuickSort(right)

data = [50,90,70,20,10,30,40,60,80]

print(QuickSort(data))#[10, 20, 30, 40, 50, 60, 70, 80, 90]

原地交換版本(In-Place)-Lomuto partition scheme

基於Lomuto partition scheme的原理,原始資料列使用一個指標與索引,當索引的資料小於Pivot時,索引的資料與指標位置資料交換。

前面的版本會需要額外的記憶體空間,In-Place版本不需要額外的子數列記憶體空間,因為只會更改原本的數列,切割的同時也就等同合併了,所以只需花費常數O(1)的空間複雜度。實作時會需要用到Partition輔助函式,來直接分割原本的數列。

操作流程:

  1. 資料列最後一筆設定為基準值(Pivot)
  2. 設定一個指標指向資料列第一筆,用來記錄小於Pivot的資料位置
  3. 逐一與Pivot比較
  4. 若當前資料小於Pivot,就將該資料與指標位置的資料做交換,接著指標往下一個位置移動
  5. 若當前資料大於等於Pivot,則跳過不做任何動作
  6. 當所有資料比較過後,再將Pivot與指標位置的資料交換
  7. 左右兩邊資料列分別重複1~6步驟,直到剩下1筆分割交換完成,不須合併

下面利用90 40 10 60 70 30 80 20 50由小到大排序。

單回合細節圖

https://ithelp.ithome.com.tw/upload/images/20211007/20121027I0ZG6JYe7j.jpg

每回合簡略圖

https://ithelp.ithome.com.tw/upload/images/20211007/20121027cDfhdYpbrd.jpg

JavaScript

let data = [90, 40, 10, 60, 70, 30, 80, 20, 50];

function quickSort(arr, start, end) {
  if (start < end) {
    const pivotIndex = partition(arr, start, end);
    quickSort(arr, start, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, end);
  }
  return arr
}

function partition(arr, start, end) {
  let pivot = arr[end];
  let nextIndex = start;
  for (let i = start; i < end; i++) {
    if (arr[i] < pivot) {
      [arr[nextIndex],arr[i]] = [arr[i],arr[nextIndex]]
      nextIndex++;
    }
  }
  [arr[nextIndex],arr[end]] = [arr[end],arr[nextIndex]]  
  return nextIndex
}

console.log(quickSort(data, 0, data.length - 1)) //[10, 20, 30, 40, 50, 60, 70, 80, 90]

Python

def QuickSort(arr, start, end):
    if start < end:
        pivotIndex = partition(arr, start, end)
        QuickSort(arr, start, pivotIndex - 1)
        QuickSort(arr, pivotIndex + 1, end)
    return arr

def partition(arr, start, end):
    n = len(arr)
    pivot = arr[end]
    nextIndex = start
    for i in range(start,n-1):
        if arr[i] < pivot:
            arr[nextIndex],arr[i] = arr[i],arr[nextIndex]
            nextIndex += 1
    arr[nextIndex],arr[end] = arr[end],arr[nextIndex]
    return nextIndex

data = [50,90,70,20,10,30,40,60,80]

print(QuickSort(data, 0 , len(data)-1))
#[10, 20, 30, 40, 50, 60, 70, 80, 90]

原地交換版本(In-Place)-Hoare partition scheme

基於Hoare partition scheme的原理,將原始資料列使用兩個指標,從資料列的兩端開始相互移動,直到它們相遇或反轉為止。

操作流程:

  1. 資料列中找出一個基準值(Pivot)
  2. 最左邊有一個指標(Pointer) L,最右邊也有一個指標(Pointer) R
  3. L逐一往右移動直到找到大於Pivot停下來
  4. R逐一往左移動直到找到小於Pivot停下來
  5. L與R的資料互相交換,L與R繼續移動
  6. L與R重疊時,重疊位置的資料Pivot互相交換
  7. L與R反轉時,R位置的資料與Pivot互相交換
  8. 基準值的左右兩邊資料分別重複1~7步驟,直到剩下1筆分割交換完成,不須合併

下面利用30 10 40 5 70 15 60 20 50 25由小到大排序。

單回合細節圖

https://ithelp.ithome.com.tw/upload/images/20211007/2012102768BNby3GCy.jpg

每回合簡略圖

https://ithelp.ithome.com.tw/upload/images/20211007/20121027N6BgTG5zcF.jpg

JavaScript

let data = [30,10,40,5,70,15,60,20,50,25];

function quickSort(arr, start, end) {
  if (start < end) {
    let pivotIndex = partition(arr, start, end);
    quickSort(arr, start, pivotIndex-1);
    quickSort(arr, pivotIndex + 1, end);
  }
  return arr;
}

function partition(arr, start, end) {
  let pivot = arr[start]
  let leftPointer = start+1
  let rightPointer = end
  let done = false
  while (done===false) {
    while (leftPointer <= rightPointer&&arr[leftPointer] <= pivot) {
      leftPointer +=1
    }

    while (leftPointer <= rightPointer&&arr[rightPointer] >= pivot) {
      rightPointer -=1
    }

    if (leftPointer > rightPointer) {
      done = true
    }else{
      [arr[leftPointer],arr[rightPointer]]=[arr[rightPointer],arr[leftPointer]]
    }
  }
  [arr[start],arr[rightPointer]]=[arr[rightPointer],arr[start]]
  return rightPointer
}

console.log(quickSort(data, 0, data.length - 1))
//[5, 10, 15, 20, 25, 30, 40, 50, 60, 70]

Python

def QuickSort(arr, start, end):
    if start < end:
        pivotIndex = Partition(arr, start, end)
        QuickSort(arr, start, pivotIndex-1)
        QuickSort(arr, pivotIndex+1, end)
    return arr

def Partition(arr, start, end):
    pivot = arr[start]
    leftPointer = start+1
    rightPointer = end
    done = False
    while not done:
        while leftPointer <= rightPointer and arr[leftPointer] <= pivot:
            leftPointer += 1
        while arr[rightPointer] >= pivot and rightPointer >=leftPointer:
            rightPointer -= 1
        if rightPointer < leftPointer:
            done= True
        else:
            arr[leftPointer],arr[rightPointer] = arr[rightPointer],arr[leftPointer]
    arr[start],arr[rightPointer] = arr[rightPointer],arr[start]
    return rightPointer
    
        
data = [30,10,40,5,70,15,60,20,50,25]

print(QuickSort(data, 0 , len(data)-1))
#[5, 10, 15, 20, 25, 30, 40, 50, 60, 70]

上一篇
【Day25】[演算法]-合併排序法Merge Sort
下一篇
【Day27】[演算法]-堆積排序法 Heap Sort
系列文
資料結構與演算法,使用JavaScript與Python35
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言