iT邦幫忙

第 12 屆 iThome 鐵人賽
DAY 7
0
Software Development

你總是躲不掉的，不如放膽面對 LeetCode 吧！系列 第 7 篇

Day 07: Sort(1) - Bubble Sort & Selection Sort

12th鐵人賽
3084 瀏覽

  • 分享至 

  • xImage
    •  

關於 Sort

昨天與前天介紹兩個線性結構：Array & Linked List，基本上，任何資料結構都十分看重如何找到特定資料的方法，因此會在乎兩點：

  • Sort，排序，幫助 Search 可以更快速。
  • Search，搜尋

接下來幾天要介紹常見的 Sort 與 Search。對於 JS 出身的工程師來說，Array 的操作相對來說較 Linked List 來的好學習。

Bubble Sort

是的，市面上的書籍幾乎第一個 Sort 相關的演算法就是 Bubble Sort。相關原理簡單來說，從頭開始，一個一個比較元素兩者，過程中找尋最大的元素，將其交換到最後的位置。接著進行第二圈，一樣從頭開始比較。持續以上步驟，直到陣列排序完成。

技術上來說，可以分成兩種做法：

  • 從頭開始進行，依序找出最大的元素將其放在最後一個。
  • 從尾開始進行，依序找出最小的元素將其放在第一個。

這邊實作第一種。

用 Array 實作

來源

JS

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

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

  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr[j], arr[j + 1])
      }
    }
  }
};

Java

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

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

        // 外圈，負責全部跑完的次數
        for (int i = 0; i < n - 1; i++) {
            // 內圈，負責比較與交換
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr[j], arr[j+1]);
                }
            }
        }
    }
}

C

#include <stdio.h>

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

// A function to implement bubble sort
void bubbleSort(int arr[], int n)
{
    int i, j;

    for (i = 0; i < n - 1; i++)
    {
        for (j = 0; j < n - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(&arr[j], &arr[j + 1]);
            }
        }
    }
}

用 Linked List 實作

來源

JS

class node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

const bubbleSortLinkedList = (start) => {
  let swapped, ptr1, lptr = null;

  if (start === null) {
    return;
  }

  do {
    swapped = 0;
    ptr1 = start;

    while (ptr1.next !== lptr) {
      if (ptr1.val > ptr1.next.val) {
        const temp = ptr1.val;
        ptr1.val = ptr1.next.val;
        ptr1.next.val = temp;
        swapped = 1;
      }

      ptr1 = ptr1.next;
    }

    lptr = ptr1;
  } while (swapped);
};

Java

class Node {
    int val;
    Node next;

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

class BubbleSortLinkedList {
    public void bubbleSortLinkedList(Node start) {
        int swapped;
        Node ptr1;
        Node lptr = null;

        if (start == null) {
            return;
        }

        do {
            swapped = 0;
            ptr1 = start;

            while (ptr1.next != lptr) {
                if (ptr1.val > ptr1.next.val) {
                    int temp = ptr1.val;
                    ptr1.val = ptr1.next.val;
                    ptr1.next.val = temp;
                    swapped = 1;
                }

                ptr1 = ptr1.next;
            }

            lptr = ptr1;
        } while (swapped);
    }
}

C

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

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

void swap(struct Node *a, struct Node *b)
{
    int temp = a->val;
    a->val = b->val;
    b->val = temp;
}

void bubbleSort(struct Node *start)
{
    int swapped;
    struct Node *ptr1;
    struct Node *lptr = NULL; // 當作停止器，避免遇到 Circular Linked List 形成無限 while-loop

    if (start == NULL)
    {
        return;
    }

    do
    {
        swapped = 0;
        ptr1 = start;

        while (ptr1->next != lptr)
        {
            if (ptr1->val > ptr1->next->val)
            {
                swap(ptr1, ptr1->next);
                swapped = 1;
            }

            ptr1 = ptr1->next;
        }

        lptr = ptr1;
    } while (swapped);
}

Selection Sort

簡單來說，從頭開始，找尋陣列中最小的元素，然後將其交換至第一個，接著第二圈，從下一個元素開始，一樣找尋最小的。持續以上步驟，直到陣列排序完成。

用 Array 實作

來源

JS

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

/**
 * @param {number[]} arr
 */
const selectionSort = (arr) => {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i;

    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    swap(arr[minIndex], arr[i]);
  }
};

Java

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

    void selectionSort(int arr[]) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;

            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            swap(arr[minIndex], arr[i]);
        }
    }
}

C

#include <stdio.h>

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

void selectionSort(int arr[], int n)
{
    int i, j, min_index;

    for (i = 0; i < n - 1; i++)
    {
        min_index = i;

        for (j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[min_index])
            {
                min_index = j;
            }
        }

        swap(&arr[min_index], &arr[i]);
    }
}

用 Linked List 實作

來源

JS

class node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

const selectionSortLinkedList = (start) => {
  let ptr1 = start;

  while (ptr1) {
    let min = ptr1;
    let nextNode = ptr1.next;

    while (nextNode) {
      if (min.val > nextNode.val) {
        min = nextNode;
      }
    }

    const temp = ptr1.val;
    ptr1.val = ptr1.next.val;
    ptr1.next.val = temp;


    ptr1 = ptr1.next;
  }
};

Java

class Node {
    int val;
    Node next;

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

class SelectionSortLinkedList {
    public void selectionSortLinkedList(Node start) {
        Node ptr1 = start;

        while (ptr1) {
            Node min = ptr1;
            Node nextNode = ptr1.next;

            while (nextNode) {
                if (min.val > nextNode.val) {
                    min = nextNode;
                }
            }

            int temp = ptr1.val;
            ptr1.val = ptr1.next.val;
            ptr1.next.val = temp;

            ptr1 = ptr1.next;
        }
    }
}

C

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

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

void swap(struct Node *a, struct Node *b)
{
    int temp = a->val;
    a->val = b->val;
    b->val = temp;
}

void selectionSortLinkedList(struct Node *start)
{
    struct Node *ptr1 = start;

    while (ptr1)
    {
        struct Node *min = ptr1;
        struct Node *r = ptr1->next;

        while (r)
        {
            if (min->val > r->val)
            {
                min = r;
            }
        }

        swap(min, ptr1);
        ptr1 = ptr1->next;
    }
}

刷題

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

結論

時間複雜度的部分，因為要遍歷每個元素，所以是最可怕的 O(n^2)。
今天跟昨天一樣，個人筆記的成份較重，著重在如何用 Linked List 實作。


上一篇
Day 06: Linked List
下一篇
Day 08: Sort(2) - Insertion Sort & Heap Sort
系列文
你總是躲不掉的，不如放膽面對 LeetCode 吧！ 共 31 篇
  1. 27
    Day 27: Memoization
  2. 28
    Day 28: Divide and Conquer
  3. 29
    Day 29: Dynamic Programming, DP
  4. 30
    Day 30: Greedy Method
  5. 31
    完結心得
完整目錄
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言
iThome鐵人賽
參賽組數
1064 組
團體組數
40 組
累計文章數
22200 篇
完賽人數
602 人
iT+看影片追技術 看影片追技術 看更多
熱門tag 看更多
15th鐵人賽 16th鐵人賽 13th鐵人賽 14th鐵人賽 12th鐵人賽 11th鐵人賽 鐵人賽 2019鐵人賽 javascript 2018鐵人賽 python 2017鐵人賽 windows php c# windows server linux css react vue.js
熱門問題
熱門回答
熱門文章
IT邦幫忙