選擇、插入、氣泡排序
December 8, 2021選擇排序（Selection sort）、插入排序（Insertion sort）與氣泡排序（Bubble sort）是初學排序必須知道的三個基本排序方式，它們由於速度不快而不實用（平均與最快的時間複雜度都是O(n2)），然而用來值得觀察與探討排序的方式。
解法思路
基本上三個排序方式在整個過程，排序的對象都會被劃分為兩部份，已排序與未排序。
選擇排序
- 如果排序是由小而大，從後端未排序部份選擇一個最小值，並放入前端已排序部份的最後一個。例如排序前 70、80、31、37、10、1、48、60、33、85。
- [1] 80 31 37 10 70 48 60 33 85（選出最小值 1）
- [1 10] 31 37 80 70 48 60 33 85（選出最小值 10）
- [1 10 31] 37 80 70 48 60 33 85（選出最小值 31）
- [1 10 31 33] 80 70 48 60 37 85（選出最小值 33）
- [1 10 31 33 37] 70 48 60 80 85（選出最小值 37）
- [1 10 31 33 37 48] 70 60 80 85（選出最小值 48）
- [1 10 31 33 37 48 60] 70 80 85（選出最小值 60）
- [1 10 31 33 37 48 60 70] 80 85（選出最小值 70）
- [1 10 31 33 37 48 60 70 80] 85（選出最小值 80）
- [1 10 31 33 37 48 60 70 80 85]（選出最小值 85）
插入排序
- 每次從後端未排序部份取得最前端的值，然後插入前端已排序部份的適當位置。例如排序前 92、77、67、8、6、84、55、85、43、67。
- [77 92] 67 8 6 84 55 85 43 67（將 77 插入 92 前）
- [67 77 92] 8 6 84 55 85 43 67（將 67 插入 77 前）
- [8 67 77 92] 6 84 55 85 43 67（將 8 插入 67 前）
- [6 8 67 77 92] 84 55 85 43 67（將 6 插入 8 前）
- [6 8 67 77 84 92] 55 85 43 67（將 84 插入 92 前）
- [6 8 55 67 77 84 92] 85 43 67（將 55 插入 67 前）
- [6 8 55 67 77 84 85 92] 43 67（將 85 插入 92 前）
- [6 8 43 55 67 77 84 85 92] 67（將 43 插入 55 前）
- [6 8 43 55 67 67 77 84 85 92]（將 67 插入 77 前）
如果資料量很小或者有大致的排序，插入排序是個不錯的選擇，常作為快速排序（quick sort）法的補充，用於少量的資料排序（通常是 7、8 個以下）。
氣泡排序
- 排序時若是從小到大，以比較相鄰元素的方式，將較大元素交換至右端，較大的元素會不斷往右移動，像是氣泡一樣，直到適當位置為止。例如排序前 95、27、90、49、80、58、6、9、18、50。
- 27 90 49 80 58 6 9 18 50 [95]（95 浮出）
- 27 49 80 58 6 9 18 50 [90 95]（90 浮出）
- 27 49 58 6 9 18 50 [80 90 95]（80 浮出）
- 27 49 6 9 18 50 [58 80 90 95]（58 浮出）
- 27 6 9 18 49 [50 58 80 90 95]（50 浮出）
- 6 9 18 27 [49 50 58 80 90 95]（49 浮出）
- 6 9 18 [27 49 50 58 80 90 95]（27 浮出）
- 6 9 [18 27 49 50 58 80 90 95]（18 浮出）
- 6 [9 18 27 49 50 58 80 90 95]（9 浮出）
- [6 9 18 27 49 50 58 80 90 95]（6 浮出）
氣泡排序法可以利用旗標方式稍微減少比較時間，當尋訪完未排序部份都沒有發生任何交換動作，表示排序已經完成，不再進行後續的比較與交換動作。
程式實作
#include <stdio.h>
#include <stdlib.h>
#define LEN 8
#define SWAP(x,y) {int t; t = x; x = y; y = t;}
void selectionSort(int*, int, int(*)(int, int));
void insertionSort(int*, int, int(*)(int, int));
void bubbleSort(int*, int, int(*)(int, int));
void print(int*, int len);
int ascending(int, int);
int descending(int, int);
int main(void) {
int number[LEN] = {10, 9, 1, 2, 5, 3, 8, 7};
selectionSort(number, LEN, ascending);
print(number, LEN);
insertionSort(number, LEN, descending);
print(number, LEN);
bubbleSort(number, LEN, ascending);
print(number, LEN);
return 0;
}
int selectedIdx(int* arr, int from, int to, int(*compar)(int, int)) {
int selected = from;
int i;
for(i = from + 1; i < to; i++) if(compar(arr[i], arr[selected]) < 0) {
selected = i;
}
return selected;
}
void selectionSort(int* arr, int len, int(*compar)(int, int)) {
int i;
for(i = 0; i < len; i++) {
int selected = selectedIdx(arr, i, len, compar);
if(selected != i) { SWAP(arr[i], arr[selected]) }
}
}
int insertedIdx(int* arr, int eleIdx, int(*compar)(int, int)) {
int i;
for(i = 0; i < eleIdx; i++) if(compar(arr[i], arr[eleIdx]) > 0) {
break;
}
return i;
}
void insert(int* arr, int eleIdx, int inserted) {
int ele = arr[eleIdx];
int i;
for(i = eleIdx; i > inserted; i--) { arr[i] = arr[i - 1]; }
arr[inserted] = ele;
}
void insertionSort(int* arr, int len, int(*compar)(int, int)) {
int i;
for(i = 0; i < len; i++) {
int inserted = insertedIdx(arr, i, compar);
if(inserted != i) { insert(arr, i, inserted); }
}
}
void bubbleTo(int* arr, int to, int(*compar)(int, int)) {
int i;
for(i = 0; i < to - 1; i++) if(compar(arr[i + 1], arr[i]) < 0) {
SWAP(arr[i + 1], arr[i]);
}
}
void bubbleSort(int* arr, int len, int(*compar)(int, int)) {
int i;
for(i = 0; i < len; i++) { bubbleTo(arr, len - i, compar); }
}
void print(int* arr, int len) {
int i;
for(i = 0; i < len; i++) { printf("%d ", arr[i]); }
printf("\n");
}
int ascending(int a, int b) { return a - b; }
int descending(int a, int b) { return -ascending(a, b); }
import java.util.*;
import static java.lang.System.out;
import static java.util.Collections.swap;
public class Sort {
public static <T extends Comparable<? super T>>
int ascending(T t1, T t2) { return t1.compareTo(t2); }
public static <T extends Comparable<? super T>>
int descending(T t1, T t2) { return -ascending(t1, t2); }
private static <T> int selectedIdx(List<T> list,
int from, int to, Comparator<? super T> c) {
int selected = from;
for(int i = from + 1; i < to; i++) {
if(c.compare(list.get(i), list.get(selected)) < 0) {
selected = i;
}
}
return selected;
}
public static <T> void selectionSort(
List<T> list, Comparator<? super T> c) {
for(int i = 0; i < list.size(); i++) {
int selected = selectedIdx(list, i, list.size(), c);
if(selected != i) { swap(list, i, selected); }
}
}
public static <T extends Comparable<? super T>> void selectionSort(
List<T> list) {
selectionSort(list, Sort::ascending);
}
private static <T> int insertedIdx(
List<T> list, int eleIdx, Comparator<? super T> c) {
int i;
for(i = 0; i < eleIdx; i++) {
if(c.compare(list.get(i), list.get(eleIdx)) > 0) { break; }
}
return i;
}
public static <T> void insertionSort(
List<T> list, Comparator<? super T> c) {
for(int i = 0; i < list.size(); i++) {
int inserted = insertedIdx(list, i, c);
if(inserted != i) {
list.add(inserted, list.remove(i));
}
}
}
public static <T extends Comparable<? super T>>
void insertionSort(List<T> list) {
insertionSort(list, Sort::ascending);
}
public static <T> void bubbleTo(
List<T> list, int to, Comparator<? super T> c) {
for(int i = 0; i < to - 1; i++) {
if(c.compare(list.get(i + 1), list.get(i)) < 0) {
swap(list, i + 1, i);
}
}
}
public static <T> void bubbleSort(
List<T> list, Comparator<? super T> c) {
for(int i = 0; i < list.size(); i++) {
bubbleTo(list, list.size() - i, c);
}
}
public static <T extends Comparable<? super T>>
void bubbleSort(List<T> list) { bubbleSort(list, Sort::ascending); }
public static void main(String[] args) {
List<Integer> list =
new ArrayList<>(Arrays.asList(10, 9, 1, 2, 5, 3, 8, 7));
selectionSort(list);
out.println(list);
insertionSort(list, Sort::descending);
out.println(list);
bubbleSort(list);
out.println(list);
}
}
from functools import reduce
def ascending(a, b): return a - b
def descending(a, b): return -ascending(a, b)
def selectionSort(xs, compare = ascending):
return [] if not xs else __select(xs, compare)
def __select(xs, compare):
selected = reduce(
lambda m, k: m if compare(m, k) < 0 else k, xs)
remain = [elem for elem in xs if elem != selected]
return (xs if not remain
else [elem for elem in xs if elem == selected]
+ __select(remain, compare))
def insertionSort(xs, compare = ascending):
return ([] if not xs
else __insert(xs[0],
insertionSort(xs[1:], compare), compare))
def __insert(x, xs, compare):
return ([x] + xs if not xs or compare(x, xs[0]) <= 0
else [xs[0]] + __insert(x, xs[1:], compare))
def bubbleSort(xs, compare = ascending):
return [] if not xs else __up(xs, compare)
def __up(xs, compare):
if not xs[1:]:
return xs
else:
s = bubbleSort(xs[1:], compare)
return ([s[0]] + __up([xs[0]] + s[1:], compare)
if compare(xs[0], s[0]) > 0
else [xs[0]] + s)
list = [10, 9, 1, 2, 5, 3, 8, 7]
print(selectionSort(list))
print(insertionSort(list, descending))
print(bubbleSort(list))
object Sort {
def selection[T](xs: List[T], compare: (T, T) => Boolean): List[T] = {
if(xs.isEmpty) Nil
else select(xs, compare)
}
private def select[T](xs: List[T],
compare: (T, T) => Boolean): List[T] = {
val selected = xs.reduceLeft((m, k) => if(compare(m, k)) m else k)
val remain = xs.filter(_ != selected)
if(remain.isEmpty) xs
else xs.filter(_ == selected) ++ select(remain, compare)
}
def insertion[T](xs: List[T], compare: (T, T) => Boolean): List[T] = {
if(xs.isEmpty) Nil
else insert(xs.head, insertion(xs.tail, compare), compare)
}
private def insert[T](x: T, xs: List[T],
compare: (T, T) => Boolean): List[T] = {
if(xs.isEmpty || x == xs.head || compare(x, xs.head)) x :: xs
else xs.head :: insert(x, xs.tail, compare)
}
def bubble[T](xs: List[T], compare: (T, T) => Boolean):List[T] = {
if(xs.isEmpty) Nil
else up(xs, compare)
}
private def up[T](xs: List[T],
compare: (T, T) => Boolean): List[T] = {
if(xs.tail.isEmpty) xs
else {
val s = bubble(xs.tail, compare)
if(!compare(xs.head, s.head))
s.head :: up(xs.head :: s.tail, compare)
else xs.head :: s
}
}
}
val list = List(10, 9, 1, 2, 5, 3, 8, 7)
println(Sort.selection[Int](list, _ > _))
println(Sort.insertion[Int](list, _ < _))
println(Sort.bubble[Int](list, _ > _))
class Array
def comprehend(&block)
return self if block.nil?
self.collect(&block).compact
end
end
class Sort
@@ascending = ->(a, b) { a - b }
@@descending = ->(a, b) { -@@ascending.call(a, b) }
def self.ascending; @@ascending end
def self.descending; @@descending end
def self.selection(xs, compare)
xs.empty? ? [] : select(xs, compare)
end
def self.select(xs, compare)
selected = xs.reduce { |m, k| compare.call(m, k) < 0 ? m : k }
remain = xs.comprehend { |elem| elem if elem != selected}
remain.empty? ?
xs : xs.comprehend {
|elem| elem if elem == selected} + select(remain, compare
)
end
private_class_method :select
def self.insertion(xs, compare)
xs.empty? ? [] : insert(
xs[0], insertion(xs[1..-1], compare), compare)
end
def self.insert(x, xs, compare)
xs.empty? || compare.call(x, xs[0]) <= 0 ?
[x] + xs : [xs[0]] + insert(x, xs[1..-1], compare)
end
private_class_method :insert
def self.bubble(xs, compare)
xs.empty? ? [] : up(xs, compare)
end
def self.up(xs, compare)
if xs[1..-1].empty?
xs
else
s = bubble(xs[1..-1], compare)
compare.call(xs[0], s[0]) > 0 ?
[s[0]] + up([xs[0]] + s[1..-1], compare) : [xs[0]] + s
end
end
private_class_method :up
end
list = [10, 9, 1, 2, 5, 3, 8, 7]
print(Sort.selection(list, Sort.ascending).to_s + "\n")
print(Sort.insertion(list, Sort.descending).to_s + "\n")
print(Sort.bubble(list, Sort.ascending).to_s + "\n")
function swap(list, i, j) {
var ele = list[i];
list[i] = list[j];
list[j] = ele;
}
function ascending(a, b) {return a - b;}
function descending(a, b) {return -ascending(a, b);}
function selectedIdx(list, from, to, compare) {
var selected = from;
for(var i = from + 1; i < to; i++) {
if(compare(list[i], list[selected]) < 0) {
selected = i;
}
}
return selected;
}
function selectionSort(list, compare) {
for(var i = 0; i < list.length; i++) {
var selected = selectedIdx(list, i, list.length, compare);
if(selected !== i) { swap(list, i, selected); }
}
}
function insertedIdx(list, eleIdx, compare) {
for(var i = 0; i < eleIdx; i++) {
if(compare(list[i], list[eleIdx]) > 0) { break; }
}
return i;
}
function insert(list, eleIdx, inserted) {
var ele = list[eleIdx];
for(var i = eleIdx; i > inserted; i--) { list[i] = list[i - 1]; }
list[inserted] = ele;
}
function insertionSort(list, compare) {
for(var i = 0; i < list.length; i++) {
var inserted = insertedIdx(list, i, compare);
if(inserted !== i) { insert(list, i, inserted); }
}
}
function bubbleTo(list, to, compare) {
for(var i = 0; i < to - 1; i++) if(compare(list[i + 1], list[i]) < 0) {
swap(list, i + 1, i);
}
}
function bubbleSort(list, compare) {
for(var i = 0; i < list.length; i++) {
bubbleTo(list, list.length - i, compare);
}
}
var list = [10, 9, 1, 2, 5, 3, 8, 7];
selectionSort(list, ascending);
print(list);
insertionSort(list, descending);
print(list);
bubbleSort(list, ascending);
print(list);
ascending a b = a - b
descending a b = -ascending a b
select xs compare =
if remain == []
then xs
else [elem | elem <- xs, elem == selected] ++ select remain compare
where
selected = foldl1 (\m k -> if compare m k < 0 then m else k) xs
remain = [elem | elem <- xs, elem /= selected]
selectionSort xs compare =
if xs == [] then [] else select xs compare
insert x xs compare =
if xs == [] || (compare x $ head xs) <= 0
then x : xs
else head xs : insert x (tail xs) compare
insertionSort xs compare =
if xs == []
then []
else insert (head xs) (insertionSort (tail xs) compare) compare
up xs compare =
if tail xs == []
then xs
else
let s = bubbleSort (tail xs) compare
in if compare (head xs) (head s) > 0
then head s : up (head xs : tail s) compare
else head xs : s
bubbleSort xs compare =
if xs == [] then [] else up xs compare
main = sequence [print $ sort list ascending| sort <- sorts]
where list = [10, 9, 1, 2, 5, 3, 8, 7]
sorts = [selectionSort, insertionSort, bubbleSort]
