選擇、插入、氣泡排序


說明

選擇排序（Selection sort）、插入排序（Insertion sort）與氣泡排序（Bubble sort）是初學排序所必須知道的三個基本排序方式，它們由於速度不快而不實用（平均與最快的時間複雜度都是O(n2)），然而排序的方式確是值得觀察與探討的。

解法

  • 選擇排序
將要排序的對象分作兩部份，一個是已排序的，一個是未排序的。如果排序是由小而大，從後端未排序部份選擇一個最小值，並放入前端已排序部份的最後一個。例如：

排序前：70 80 31 37 10 1 48 60 33 80

  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 ......

  • 插入排序
將要排序的對象分作兩部份，一個是已排序的，一個是未排序的。每次從後端未排序部份取得最前端的值，然後插入前端已排序部份的適當位置。例如：

排序前：92 77 67 8 6 84 55 85 43 67

  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] ......

  • 氣泡排序法
將要排序的對象分作兩部份，一個是已排序的，一個是未排序的。排序時若是從小到大，最大元素會如同氣泡一樣移至右端，其利用比較相鄰元素的方式，將較大元素交換至右端，所以較大的元素會不斷往右移動，直到適當的位置為止。

排序前：95 27 90 49 80 58 6 9 18 50

  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    Java    Python    Scala    Ruby    JavaScript    Haskell

  • 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 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))

  • 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
    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")

  • 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);

  • Haskell
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]