# 選擇、插入、氣泡排序

## 解法

• 選擇排序

1. [1] 80 31 37 10 70 48 60 33 80；選出最小值1
2. [1 10] 31 37 80 70 48 60 33 80；選出最小值10
3. [1 10 31] 37 80 70 48 60 33 80；選出最小值31
4. [1 10 31 33] 80 70 48 60 37 80 ......
5. [1 10 31 33 37] 70 48 60 80 80 ......
6. [1 10 31 33 37 48] 70 60 80 80 ......
7. [1 10 31 33 37 48 60] 70 80 80 ......
8. [1 10 31 33 37 48 60 70] 80 80 ......
9. [1 10 31 33 37 48 60 70 80] 80 ......

• 插入排序

1. [77 92] 67 8 6 84 55 85 43 67；將77插入92前
2. [67 77 92] 8 6 84 55 85 43 67；將67插入77前
3. [8 67 77 92] 6 84 55 85 43 67；將8插入67前
4. [6 8 67 77 92] 84 55 85 43 67；將6插入8前
5. [6 8 67 77 84 92] 55 85 43 67；將84插入92前
6. [6 8 55 67 77 84 92] 85 43 67；將55插入67前
7. [6 8 55 67 77 84 85 92] 43 67 ......
8. [6 8 43 55 67 77 84 85 92] 67 ......
9. [6 8 43 55 67 67 77 84 85 92] ......

• 氣泡排序法

1. 27 90 49 80 58 6 9 18 50 [95]；95浮出
2. 27 49 80 58 6 9 18 50 [90 95]；90浮出
3. 27 49 58 6 9 18 50 [80 90 95]；80浮出
4. 27 49 6 9 18 50 [58 80 90 95] ......
5. 27 6 9 18 49 [50 58 80 90 95] ......
6. 6 9 18 27 [49 50 58 80 90 95] ......
7. 6 9 18 [27 49 50 58 80 90 95] ......
8. 6 9 [18 27 49 50 58 80 90 95] ......
9. 6 [9 18 27 49 50 58 80 90 95] ......
10. [6 9 18 27 49 50 58 80 90 95] ......

• C
``#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); }``

• Java
``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);    }}``

• Python
``from functools import reducedef ascending(a, b): return a - bdef 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))``

• Scala
``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, _ > _))``

• Ruby
``class Array    def comprehend(&block)        return self if block.nil?        self.collect(&block).compact    endendclass 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 :upendlist = [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")``

• JavaScript
``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 - bdescending a b = -ascending a bselect 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 compareinsert x xs compare =    if xs == [] || (compare x \\$ head xs) <= 0        then x : xs        else head xs : insert x (tail xs) compareinsertionSort xs compare =    if xs == []         then []        else insert (head xs) (insertionSort (tail xs) compare) compareup 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 : sbubbleSort xs compare =    if xs == [] then [] else up xs comparemain = sequence [print \\$ sort list ascending| sort <- sorts]    where list = [10, 9, 1, 2, 5, 3, 8, 7]          sorts = [selectionSort, insertionSort, bubbleSort]``