iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 9
0
Software Development

你總是躲不掉的,不如放膽面對 LeetCode 吧!系列 第 9

Day 09: Sort(3) - Merge Sort & Quick Sort

Merge Sort

簡單來說,將 Array 或是 Linked List 分割成幾乎等長的兩個串列,持續分割直到無法再分割為止。接著兩個兩個比較大小後合併成有排序的串列,持續合併直到只剩下一個串列,就完成了。

# 一開始
76 61 18 23 98 12 34 21 13 45
# 持續分割
76   61   18   23   98   12   34   21   13   45
# 開始比較與合併
# 第一回合
61 76    18 23    12 98    21 34    13 45
# 第二回合
18 23 61 76    12 21 34 98    13 45
# 第三回合
12 18 21 23 34 61 76 98    13 45
# 第四回合
12 13 18 21 23 34 45 61 76 98
# 排列結束

其背後的演算法可以歸類在:Divide and Conquer(分治法)。將複雜的問題分成兩個或更多的相同或相似的子問題,直到最後子問題可以簡單的直接求解,原問題的解即子問題的解的合併。

wiki

Array 實作

來源

JS

/**
 * @param {number[]} arr
 * @param {number} arrStartIndex
 * @param {number} middleIndex
 * @param {number} arrEndIndex
 */
const merge = (arr, arrStartIndex, middleIndex, arrEndIndex) => {
  // 計算左右兩陣列的長度
  const leftArrLength = middleIndex - arrStartIndex + 1;
  const rightArrLength = arrEndIndex - middleIndex;

  // 製作左右兩陣列
  let LeftArr = new Array(leftArrLength);
  let RightArr = new Array(rightArrLength);

  // 將資料放入左右兩陣列
  for (let i = 0; i < leftArrLength; i++) {
    // 從 arrStarIndex 開始
    LeftArr[i] = arr[arrStartIndex + i];
  }

  for (let j = 0; j < rightArrLength; j++) {
    // 從 middleIndex 開始
    RightArr[j] = arr[middleIndex + 1 + j];
  }

  // 接著要開始遍歷左右陣列準備合併,於是要先建立兩個陣列的 index
  let leftArrIndex = 0, rightArrIndex = 0;
  // 合併後的大陣列 index
  let mergedArrIndex = arrStartIndex;

  while (leftArrIndex < leftArrLength && rightArrIndex < rightArrLength) {
    // 比較左右兩陣列的數值,數值小的放入合併後的陣列
    if (LeftArr[leftArrIndex] <= RightArr[rightArrIndex]) {
      arr[mergedArrIndex] = LeftArr[leftArrIndex];
      leftArrIndex++;
    } else {
      arr[mergedArrIndex] = RightArr[rightArrIndex];
      rightArrIndex++;
    }

    mergedArrIndex++;
  }

  // 將剩餘的數值放入合併後的陣列,剩餘數值會將大於合併後的陣列內的任一元素
  while (leftArrIndex < leftArrLength) {
    arr[mergedArrIndex] = LeftArr[leftArrIndex];
    leftArrIndex++;
    mergedArrIndex++;
  }

  // 將剩餘的數值放入合併後的陣列,剩餘數值會將大於合併後的陣列內的任一元素
  while (rightArrIndex < rightArrLength) {
    arr[mergedArrIndex] = RightArr[rightArrIndex];
    rightArrIndex++;
    mergedArrIndex++;
  }
};

/**
 * @param {number[]} arr
 * @param {number} arrStartIndex
 * @param {number} arrEndIndex
 */
const mergeSort = (arr, arrStartIndex, arrEndIndex) => {
  if (arrStartIndex < arrEndIndex) {
    let middleIndex = (arrStartIndex + arrEndIndex) >> 1;

    // 這邊使用 Divide and Conquer,將複雜的問題分成兩個或更多的相同或相似的子問題
    mergeSort(arr, arrStartIndex, middleIndex);
    mergeSort(arr, middleIndex + 1, arrEndIndex);

    merge(arr, arrStartIndex, middleIndex, arrEndIndex);
  }
}

Java

class MergeSort {
    void merge(int arr[], int arrStartIndex, int middleIndex, int arrEndIndex) {
        // 計算左右兩陣列的長度
        int leftArrLength = middleIndex - arrStartIndex + 1;
        int rightArrLength = arrEndIndex - middleIndex;

        // 製作左右兩陣列
        int LeftArr[] = new int[leftArrLength];
        int RightArr[] = new int[rightArrLength];

        // 將資料放入左右兩陣列
        for (int i = 0; i < leftArrLength; i++) {
            // 從 arrStarIndex 開始
            LeftArr[i] = arr[arrStartIndex + i];
        }

        for (int j = 0; j < rightArrLength; j++) {
            // 從 middleIndex 開始
            RightArr[j] = arr[middleIndex + 1 + j];
        }

        // 接著要開始遍歷左右陣列準備合併,於是要先建立兩個陣列的 index
        int leftArrIndex = 0, rightArrIndex = 0;
        // 合併後的大陣列 index
        int mergedArrIndex = arrStartIndex;

        while (leftArrIndex < leftArrLength && rightArrIndex < rightArrLength) {
            // 比較左右兩陣列的數值,數值小的放入合併後的陣列
            if (LeftArr[leftArrIndex] <= RightArr[rightArrIndex]) {
                arr[mergedArrIndex] = LeftArr[leftArrIndex];
                leftArrIndex++;
            } else {
                arr[mergedArrIndex] = RightArr[rightArrIndex];
                rightArrIndex++;
            }

            mergedArrIndex++;
        }

        // 將剩餘的數值放入合併後的陣列,剩餘數值會將大於合併後的陣列內的任一元素
        while (leftArrIndex < leftArrLength) {
            arr[mergedArrIndex] = LeftArr[leftArrIndex];
            leftArrIndex++;
            mergedArrIndex++;
        }

        // 將剩餘的數值放入合併後的陣列,剩餘數值會將大於合併後的陣列內的任一元素
        while (rightArrIndex < rightArrLength) {
            arr[mergedArrIndex] = RightArr[rightArrIndex];
            rightArrIndex++;
            mergedArrIndex++;
        }
    }

    void mergeSort(int arr[], int arrStartIndex, int arrEndIndex) {
        if (arrStartIndex < arrEndIndex) {
            int middleIndex = (arrStartIndex + arrEndIndex) / 2;

            // 這邊使用 Divide and Conquer,將複雜的問題分成兩個或更多的相同或相似的子問題
            mergeSort(arr, arrStartIndex, middleIndex);
            mergeSort(arr, middleIndex + 1, arrEndIndex);

            merge(arr, arrStartIndex, middleIndex, arrEndIndex);
        }
    }
}

C

#include <stdio.h>

void merge(int arr[], int arrStartIndex, int middleIndex, int arrEndIndex)
{
    int i, j, k;
    // 計算左右兩陣列的長度
    int leftArrLength = middleIndex - arrStartIndex + 1;
    int rightArrLength = arrEndIndex - middleIndex;

    // 製作左右兩陣列
    int LeftArr[leftArrLength], RightArr[rightArrLength];

    // 將資料放入左右兩陣列
    for (i = 0; i < leftArrLength; i++)
    {
        // 從 arrStarIndex 開始
        LeftArr[i] = arr[arrStartIndex + i];
    }

    for (j = 0; j < rightArrLength; j++)
    {
        // 從 middleIndex 開始
        RightArr[j] = arr[middleIndex + 1 + j];
    }

    // 接著要開始遍歷左右陣列準備合併,於是要先建立兩個陣列的 index
    int leftArrIndex = 0;
    int rightArrIndex = 0;
    // 合併後的大陣列 index
    int mergedArrIndex = arrStartIndex;

    while (leftArrIndex < leftArrLength && rightArrIndex < rightArrLength)
    {
        // 比較左右兩陣列的數值,數值小的放入合併後的陣列
        if (LeftArr[leftArrIndex] <= RightArr[rightArrIndex])
        {
            arr[mergedArrIndex] = LeftArr[leftArrIndex];
            leftArrIndex++;
        }
        else
        {
            arr[mergedArrIndex] = RightArr[rightArrIndex];
            rightArrIndex++;
        }

        mergedArrIndex++;
    }

    // 將剩餘的數值放入合併後的陣列,剩餘數值會將大於合併後的陣列內的任一元素
    while (leftArrIndex < leftArrLength)
    {
        arr[mergedArrIndex] = LeftArr[leftArrIndex];
        leftArrIndex++;
        mergedArrIndex++;
    }

    // 將剩餘的數值放入合併後的陣列,剩餘數值會將大於合併後的陣列內的任一元素
    while (rightArrIndex < rightArrLength)
    {
        arr[mergedArrIndex] = RightArr[rightArrIndex];
        rightArrIndex++;
        mergedArrIndex++;
    }
}

void mergeSort(int arr[], int arrStartIndex, int arrEndIndex)
{
    if (arrStartIndex < arrEndIndex)
    {
        int middleIndex = arrStartIndex + (arrEndIndex - arrStartIndex) / 2;

        // 這邊使用 Divide and Conquer,將複雜的問題分成兩個或更多的相同或相似的子問題
        mergeSort(arr, arrStartIndex, middleIndex);
        mergeSort(arr, middleIndex + 1, arrEndIndex);

        merge(arr, arrStartIndex, middleIndex, arrEndIndex);
    }
}

Linked List 實作

來源

JS

class node {
  /**
   * @param {number} val
   * @param {node} next
   */
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

/**
 * @param {node} headRef
 */
const mergeSort = (headRef) => {
  let head = new node();
  let a = new node();
  let b = new node();


  if (head === null || head.next === null) {
    return;
  }

  frontBackSplit(head, a, b);

  mergeSort(a);
  mergeSort(b);

  headRef = sortedMerge(a, b);
}

/**
 * @param {node} a
 * @param {node} b
 */
const sortedMerge = (a, b) => {
  let result = null;

  if (a === null) {
    return b;
  }

  if (b === null) {
    return a;
  }

  if (a.val <= b.val) {
    result = a;
    result.next = sortedMerge(a.next, b);
  } else {
    result = b;
    result.next = sortedMerge(a, b.next);
  }
};

/**
 * @param {node} source
 * @param {node} frontRef
 * @param {node} backRef
 */
const frontBackSplit = (source, frontRef, backRef) => {
  let slow = source, fast = source.next;

  while (fast !== null) {
    fast = fast.next;

    if (fast !== null) {
      slow = slow.next;
      fast = fast.next;
    }
  }

  frontRef = source;
  backRef = slow.next;
  slow.next = null;
};

Java

public class MergeSortLinkedList {
    Node head = null;

    static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
            this.next = null;
        }
    }

    Node sortedMerge(Node a, Node b) {
        Node result = null;

        if (a == null) {
            return b;
        }

        if (b == null) {
            return a;
        }

        if (a.val <= b.val) {
            result = a;
            result.next = sortedMerge(a.next, b);
        } else {
            result = b;
            result.next = sortedMerge(a, b.next);
        }

        return result;
    }

    Node mergeSort(Node head) {
        if (head == null || head.next == null) {
            return head;
        }

        Node middle = getMiddle(head);
        Node nextOfMiddle = middle.next;

        middle.next = null;

        Node left = mergeSort(head);

        Node right = mergeSort(nextOfMiddle);

        Node sortedList = sortedMerge(left, right);
        return sortedList;
    }

    public static Node getMiddle(Node head) {
        if (head == null) {
            return head;
        }

        Node slow = head, fast = head;

        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }
}

C

#include <stdio.h>

struct Node
{
    int val;
    struct Node *next;
};

struct Node *SortedMerge(struct Node *a, struct Node *b);
void FrontBackSplit(struct Node *source, struct Node **front_ref, struct Node **back_ref);

// 藉由改變下個節點來排序 Linked List
void MergeSort(struct Node **head_ref)
{
    struct Node *head = *head_ref;
    struct Node *a;
    struct Node *b;

    // 如果節點只有一個或是沒有,那不用排序
    if ((head == NULL) || (head->next == NULL))
    {
        return;
    }

    // 將 List 拆解成兩個子 List: a & b
    FrontBackSplit(head, &a, &b);

    // 對子 List 使用遞迴排序
    MergeSort(&a);
    MergeSort(&b);

    // 將兩個子 List 組合
    *head_ref = SortedMerge(a, b);
}

struct Node *SortedMerge(struct Node *a, struct Node *b)
{
    struct Node *result = NULL;

    // List 為 NULL,不用合併排列
    if (a == NULL)
    {
        return b;
    }

    // List 為 NULL,不用合併排列
    if (b == NULL)
    {
        return a;
    }

    // 比較兩個子 List,較小的元素先放入,然後用遞迴處理
    if (a->val <= b->val)
    {
        result = a;
        result->next = SortedMerge(a->next, b);
    }
    else
    {
        result = b;
        result->next = SortedMerge(a, b->next);
    }

    return result;
}

// 將 List 拆解成兩個子 List
void FrontBackSplit(struct Node *source, struct Node **front_ref, struct Node **back_ref)
{
    // 使用快慢指標來處理
    struct Node *fast;
    struct Node *slow;
    slow = source;
    fast = source->next;

    // 關鍵,讓 fast 前進兩個節點,slow 前進一個節點
    // 當 slow 走到一半時,fast 肯定在最後,一前一後可以形成兩個長度相似的子 List
    while (fast != NULL)
    {
        fast = fast->next;

        if (fast != NULL)
        {
            slow = slow->next;
            fast = fast->next;
        }
    }

    *front_ref = source;
    *back_ref = slow->next;
    slow->next = NULL;
}

Quick Sort

簡單來說,在數列中隨機選擇一個作為基準,接著剩餘的數與基準比較,放入較大的數列或是較小的數列。完成後,分別對這兩個數列使用相同方法來處理。

Array 實作

來源

JS

/**
 * @param {number[]} arr
 * @param {number} low
 * @param {number} high
 */
const partition = (arr, low, high) => {
  let pivot = arr[high];
  let i = (low - 1);

  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      let temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
  }

  let temp = arr[i + 1];
  arr[i + 1] = arr[high];
  arr[high] = temp;
  return (i + 1);
};

/**
 * @param {number[]} arr
 * @param {number} low
 * @param {number} high
 */
const quickSort = (arr, low, high) => {
  if (low < high) {
    let pi = partition(arr, low, high);

    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
};

Java

class QuickSort {
    int partition(int arr[], int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);

        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return (i + 1);
    }

    void quickSort(int arr[], int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);

            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }
}

C

#include <stdio.h>

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int low, int high)
{
    // 將數列最後一個當作基準
    int pivot = arr[high];
    // i 負責扮演最小元素的 index
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++)
    {
        if (arr[j] < pivot)
        {
            // 找到最小元素後,先增加 i ,挪到下一個位置,好放置新的最小元素
            i++;
            swap(&arr[i], &arr[j]);
        }
    }

    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int startIndex, int endIndex)
{
    if (startIndex < endIndex)
    {
        int pi = partition(arr, startIndex, endIndex);

        quickSort(arr, startIndex, pi - 1);
        quickSort(arr, pi + 1, endIndex);
    }
}

Linked List 實作

來源

JS

// 才疏學淺,暫時用 class 語法撰寫
class node {
  /**
   * @param {number} val
   * @param {node} next
   */
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class QuickSortLinkedList {
  constructor() {
    this.head = null;
  }

  /**
   * @param {node} start
   * @param {node} end
   */
  partitionLast(start, end) {
    if (start == end || start == null || end == null) {
      return start;
    }

    let pivotPrev = start;
    let current = start;
    let pivot = end.val;

    while (start != end) {
      if (start.val < pivot) {
        pivotPrev = current;
        let temp = current.val;
        current.val = start.val;
        start.val = temp;
        current = current.next;
      }

      start = start.next;
    }

    let temp = current.val;
    current.val = pivot;
    end.val = temp;

    return pivotPrev;
  }

  /**
   * @param {node} start
   * @param {node} end
   */
  quickSort(start, end) {
    if (start == end) {
      return;
    }

    let pivot_prev = this.partitionLast(start, end);
    this.quickSort(start, pivot_prev);

    if (pivot_prev != null && pivot_prev == start) {
      this.quickSort(pivot_prev.next, end);
    } else if (pivot_prev != null && pivot_prev.next != null) {
      this.quickSort(pivot_prev.next.next, end);
    }
  }

  /**
   * @param {number} data
   */
  addNode(data) {
    if (this.head == null) {
      this.head = new node(data);
      return;
    }

    let current = this.head;

    while (current.next != null) {
      current = current.next;
    }

    let newNode = new node(data);
    current.next = newNode;
  }

  /**
   * @param {node} node
   */
  printList(node) {
    let message = '';

    while (node !== null) {
      message += (node.val + ' ');
      node = node.next;
    }

    console.log(message);
  }
}

Java

public class QuickSortLinkedList {
    static class Node {
        int val;
        Node next;

        Node(int val) {
            this.val = val;
            this.next = null;
        }
    }

    Node head;

    Node partitionLast(Node start, Node end) {
        if (start == end || start == null || end == null) {
            return start;
        }

        Node pivotPrev = start;
        Node current = start;
        int pivot = end.val;

        while (start != end) {
            if (start.val < pivot) {
                pivotPrev = current;
                int temp = current.val;
                current.val = start.val;
                start.val = temp;
                current = current.next;
            }

            start = start.next;
        }

        int temp = current.val;
        current.val = pivot;
        end.val = temp;

        return pivotPrev;
    }

    void sort(Node start, Node end) {
        if (start == end) {
            return;
        }

        Node pivot_prev = partitionLast(start, end);
        sort(start, pivot_prev);

        if (pivot_prev != null && pivot_prev == start) {
            sort(pivot_prev.next, end);
        } else if (pivot_prev != null && pivot_prev.next != null) {
            sort(pivot_prev.next.next, end);
        }
    }
}

C

#include <stdio.h>
#include <stdlib.h>

struct Node
{
    int data;
    struct Node *next;
};

struct Node *getTail(struct Node *cur)
{
    while (cur != NULL && cur->next != NULL)
    {
        cur = cur->next;
    }

    return cur;
}

struct Node *partition(struct Node *head, struct Node *end,
                       struct Node **newHead, struct Node **newEnd)
{
    struct Node *pivot = end;
    struct Node *prev = NULL;
    struct Node *cur = head;
    struct Node *tail = pivot;

    while (cur != pivot)
    {
        if (cur->data < pivot->data)
        {
            if ((*newHead) == NULL) {
                (*newHead) = cur;
            }

            prev = cur;
            cur = cur->next;
        }
        else
        {
            if (prev) {
                prev->next = cur->next;
            }

            struct Node *tmp = cur->next;
            cur->next = NULL;
            tail->next = cur;
            tail = cur;
            cur = tmp;
        }
    }

    if ((*newHead) == NULL) {
        (*newHead) = pivot;
    }

    (*newEnd) = tail;

    return pivot;
}

struct Node *quickSortRecur(struct Node *head, struct Node *end)
{
    if (!head || head == end)
    {
        return head;
    }

    struct Node *newHead = NULL;
    struct Node *newEnd = NULL;

    struct Node *pivot = partition(head, end, &newHead, &newEnd);

    if (newHead != pivot)
    {

        struct Node *tmp = newHead;

        while (tmp->next != pivot) {
            tmp = tmp->next;
        }

        tmp->next = NULL;

        newHead = quickSortRecur(newHead, tmp);

        tmp = getTail(newHead);
        tmp->next = pivot;
    }

    pivot->next = quickSortRecur(pivot->next, newEnd);

    return newHead;
}

void quickSort(struct Node **headRef)
{
    (*headRef) = quickSortRecur(*headRef, getTail(*headRef));
    return;
}

刷題

跟前兩天一樣先跳過,之後介紹完 Sort 之後,會花一天時間,同一題用不同 Sort 來處理。

結論

時間複雜度的部分:

  • Merge Sort 切成小數列要花費 O(log n),合併時花費 O(n),所以耗費 O(n log n)
  • Quick Sort 如同 Merge Sort,切出小數列要花費 O(log n),比較合併時花費 O(n),所以耗費 O(n log n)

六種 Sort 告一段落,明天來刷題。


上一篇
Day 08: Sort(2) - Insertion Sort & Heap Sort
下一篇
Day 10: Sort(4) - 演算法練習
系列文
你總是躲不掉的,不如放膽面對 LeetCode 吧!31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言