昨天與前天介紹兩個線性結構:Array
& Linked List
,基本上,任何資料結構都十分看重如何找到特定資料的方法,因此會在乎兩點:
接下來幾天要介紹常見的 Sort 與 Search。對於 JS
出身的工程師來說,Array
的操作相對來說較 Linked List
來的好學習。
是的,市面上的書籍幾乎第一個 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);
}
簡單來說,從頭開始,找尋陣列中最小的元素,然後將其交換至第一個,接著第二圈,從下一個元素開始,一樣找尋最小的。持續以上步驟,直到陣列排序完成。
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
實作。