Insertion Sort

簡單來說，將陣列分成左右兩塊，左邊這塊負責放置排序好的元素，右邊則是即將要排序的元素。執行的順序會是：

1. 第一個元素，直接放在左邊後結束。
2. 第二個元素，開始與第一個比較，較大放右；較小放左。
3. 第三個元素，開始與前兩個比較，找出適合放置的位置。
4. 剩下的持續下去，直到陣列排序完成。

範例：

# 一開始
76 61 18 23 98 12 34 21 13
# 第一回合
76        61 18 23 98 12 34 21 13
# 第二回合
# 61 比 76 小，放在左邊
61 76        18 23 98 12 34 21 13
# 第三回合
# 18 比 76 小，放在左邊
# 18 比 61 小，放在左邊
18 61 76        23 98 12 34 21 13
# 第四回合
# 23 比 76 小，放在左邊
# 23 比 61 小，放在左邊
# 23 比 18 大，放在右邊
18 23 61 76        98 12 34 21 13
# 第五回合
# 98 比 76 大，放在右邊
18 23 61 76 98        12 34 21 13
# 第六回合
# 12 比 98 小，放在左邊
# 12 比 76 小，放在左邊
# 12 比 61 小，放在左邊
# 12 比 23 小，放在左邊
# 12 比 18 小，放在左邊
12 18 23 61 76 98        34 21 13
# 第七回合
# 34 比 98 小，放在左邊
# 34 比 76 小，放在左邊
# 34 比 61 小，放在左邊
# 34 比 23 大，放在右邊
12 18 23 34 61 76 98        21 13
# 第八回合
# 21 比 98 小，放在左邊
# 21 比 76 小，放在左邊
# 21 比 61 小，放在左邊
# 21 比 34 小，放在左邊
# 21 比 23 小，放在左邊
# 21 比 18 大，放在右邊
12 18 21 23 34 61 76 98        13
# 第九回合
# 13 比 98 小，放在左邊
# 13 比 76 小，放在左邊
# 13 比 61 小，放在左邊
# 13 比 34 小，放在左邊
# 13 比 23 小，放在左邊
# 13 比 21 小，放在左邊
# 13 比 18 小，放在左邊
# 13 比 12 大，放在右邊
12 13 18 21 23 34 61 76 98
# 排列結束

用 Array 實作

連結

JS

/**
 * @param {number[]} arr
 */
const insertionSort = (arr) => {
  // 回合的控制
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i];
    let j = i - 1;

    // 比較與交換的過程，過程中會不斷將舊元素的 Index 往後挪一
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }

    // 找到正確的位置，將目標元素放入
    arr[j + 1] = key;
  }
};

Java

class InsertionSort {
    void insertionSort(int arr[]) {
        // 回合的控制
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;

            // 比較與交換的過程，過程中會不斷將舊元素的 Index 往後挪一
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }

            // 找到正確的位置，將目標元素放入
            arr[j + 1] = key;
        }
    }
}

C

#include <stdio.h>

void insertionSort(int arr[], int n)
{
    int i;
    int j;
    int key;

    // 回合的控制
    for (i = 1; i < n; i++)
    {
        key = arr[i];
        j = i - 1;

        // 比較與交換的過程，過程中會不斷將舊元素的 Index 往後挪一
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j--;
        }

        // 找到正確的位置，將目標元素放入
        arr[j + 1] = key;
    }
}

用 Linked List 實作

來源

JS

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

/**
 * @param {node} headRef
 * @param {node} newNode
 */
const sortedInsert = (headRef, newNode) => {
  /**
   * @type {node}
   */
  let current = null;

  if (headRef === null || headRef.val >= newNode.val) {
    newNode.next = headRef;
    headRef = newNode;
  } else {
    current = headRef;

    while (current.next !== null && current.next.val < newNode.val) {
      current = current.next;
    }

    newNode.next = current.next;
    current.next = newNode;
  }

  return headRef;
};

/**
 * @param {node} headRef
 */
const insertionSortLinkedList = (headRef) => {
  let sorted = null;
  let current = headRef;

  while (current !== null) {
    let nextNode = current.next;
    sorted = sortedInsert(sorted, current);
    current = nextNode;
  }

  headRef = sorted;
  return headRef;
};

Java

public class InsertionSortLinkedList {
    Node head;
    Node sorted;

    class Node {
        int val;
        Node next;

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

    void sortedInsert(Node newNode) {
        // 舊節點數值大於新節點，所以將新節點的 next 導向舊節點
        if (sorted == null || sorted.val >= newNode.val) {
            newNode.next = sorted;
            sorted = newNode;
        } else {
            // 舊節點數值小於新節點，進行交換
            Node current = sorted;

            while (current.next != null && current.next.val < newNode.val) {
                current = current.next;
            }

            newNode.next = current.next;
            current.next = newNode;
        }
    }

    void insertionSortLinkedList(Node headRef) {
        // 建議儲存的 List，最後更新成這個
        sorted = null;
        // 將目前的節點導向傳入的節點
        Node current = headRef;

        // 回合的控制
        while (current != null) {
            // 儲存 next 節點，供下次的 while-loop 使用
            Node nextNode = current.next;
            // 插入節點
            sortedInsert(current);
            // 更新目前的節點
            current = nextNode;
        }

        // 排序完成，進行更新
        head = sorted;
    }
}

C

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

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

void sortedInsert(struct Node **head_ref, struct Node *new_node)
{
    struct Node *current;

    // 舊節點數值大於新節點，所以將新節點的 next 導向舊節點
    if (*head_ref == NULL || (*head_ref)->val >= new_node->val)
    {
        new_node->next = *head_ref;
        *head_ref = new_node;
    }
    else
    {
        // 舊節點數值小於新節點，進行交換
        current = *head_ref;
        while (current->next != NULL && current->next->val < new_node->val)
        {
            current = current->next;
        }

        new_node->next = current->next;
        current->next = new_node;
    }
}

void insertionSortLinkedList(struct Node **head_ref)
{
    // 建議儲存的 List，最後更新成這個
    struct Node *sorted = NULL;
    // 將目前的節點導向傳入的節點
    struct Node *current = *head_ref;

    // 回合的控制
    while (current != NULL)
    {
        // 儲存 next 節點，供下次的 while-loop 使用
        struct Node *next = current->next;
        // 插入節點
        sortedInsert(&sorted, current);
        // 更新目前的節點
        current = next;
    }

    // 排序完成，進行更新
    *head_ref = sorted;
}

Heap Sort

Heap 的結構在之後會介紹，總之，這是用 Array 或 Linked List 製作出 Heap 結構後，接著重新排序 Heap 的內容。排序完成後開始找尋最大的元素，然後重新排列 Heap。重複以上的步驟，最後得到一個排列好的 Array 或 Linked List。

用 Array 實作

來源

JS

const heapify = (arr, heapSize, index) => {
  let largest = index, left = 2 * index + 1, right = 2 * index + 2;

  if (left < heapSize && arr[left] > arr[largest]) {
    largest = left;
  }

  if (right < heapSize && arr[right] > arr[largest]) {
    largest = right;
  }

  if (largest !== index) {
    let temp = arr[index];
    arr[index] = arr[largest];
    arr[largest] = temp;

    heapify(arr, heapSize, largest);
  }
};

/**
 * @param {number[]} arr
 */
const heapSort = (arr) => {
  const n = arr.length;

  for (let i = (n >> 1) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  for (let i = n - 1; i > 0; i--) {
    let temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;

    heapify(arr, i, 0);
  }
};

Java

public class HeapSort {
    void heapify(int arr[], int heapSize, int index) {
        int largest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;

        if (left < heapSize && arr[left] > arr[largest]) {
            largest = left;
        }

        if (right < heapSize && arr[right] > arr[largest]) {
            largest = right;
        }

        if (largest != index) {
            int temp = arr[index];
            arr[index] = arr[largest];
            arr[largest] = temp;

            heapify(arr, heapSize, largest);
        }
    }

    public void heapSort(int arr[]) {
        int n = arr.length;

        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        for (int i = n - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            heapify(arr, i, 0);
        }
    }
}

C

#include <stdio.h>

void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

void heapify(int arr[], int heapSize, int index)
{
    int largest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;

    if (left < heapSize && arr[left] > arr[largest])
    {
        largest = left;
    }

    if (right < heapSize && arr[right] > arr[largest])
    {
        largest = right;
    }

    if (largest != index)
    {
        swap(&arr[index], &arr[largest]);
        heapify(arr, heapSize, largest);
    }
}

void heapSort(int arr[], int arr_length)
{
    for (int i = arr_length / 2 - 1; i >= 0; i--)
    {
        heapify(arr, arr_length, i);
    }

    for (int i = arr_length - 1; i > 0; i--)
    {
        swap(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
}

用 Linked List 實作

來源

JS

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

/**
 * @param {number} a
 * @param {number} b
 */
const swap = (a, b) => {
  const temp = a;
  a = b;
  b = temp;
};

/**
 * @param {node} tmp
 */
const heapSortLinkedList = (tmp) => {
  if (tmp.right == null && tmp.left == null) {
    return;
  }

  if (tmp.right == null) {
    if (tmp.left.val > tmp.val) {
      swap(tmp.left.val, tmp.val);
    }
  } else {
    if (tmp.right.val > tmp.left.val) {
      if (tmp.right.val > tmp.val) {
        swap(tmp.right.val, tmp.val);
        heapSortLinkedList(tmp.right);
      }
    } else {
      if (tmp.left.val > tmp.val) {
        swap(tmp.left.val, tmp.val);
        heapSortLinkedList(tmp.left);
      }
    }
  }
};

Java

public class HeapSortLinkedList {
    class Node {
        int val;
        Node left;
        Node right;

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

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

    void heapSortLinkedList(Node tmp) {
        if (tmp.right == null && tmp.left == null) {
            return;
        }

        if (tmp.right == null) {
            if (tmp.left.val > tmp.val) {
                swap(tmp.left.val, tmp.val);
            }
        } else {
            if (tmp.right.val > tmp.left.val) {
                if (tmp.right.val > tmp.val) {
                    swap(tmp.right.val, tmp.val);
                    heapSortLinkedList(tmp.right);
                }
            } else {
                if (tmp.left.val > tmp.val) {
                    swap(tmp.left.val, tmp.val);
                    heapSortLinkedList(tmp.left);
                }
            }
        }
    }
}

C

#include <stdio.h>

void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

void heapSort(node *tmp)
{
    if (!tmp->right && !tmp->left)
    {
        return;
    }

    if (!tmp->right)
    {
        if (tmp->left->data > tmp->data)
        {
            swap(&tmp->left->data, &tmp->data);
        }
    }
    else
    {
        if (tmp->right->data > tmp->left->data)
        {
            if (tmp->right->data > tmp->data)
            {
                swap(&tmp->right->data, &tmp->data);
                heapSort(tmp->right);
            }
        }
        else
        {
            if (tmp->left->data > tmp->data)
            {
                swap(&tmp->left->data, &tmp->data);
                heapSort(tmp->left);
            }
        }
    }
}

刷題

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

結論

時間複雜度的部分：

• Insertion Sort 要遍歷每個元素，最糟糕的情況是 O(n^2)。
• Heap Sort 轉換為 Heap 要花 O(n log n)，從 Heap 找到目標元素後重新排列要花 O(n log n)，所以耗費 O(2n log n) -> O(n log n)。