简单排序

*用处：简单，体现思路，特殊情况下有用，改进特殊排序

*选择排序：从后面j中拎出一个最小值与前面元素i交换。比如人眼排列有限数据（可以一眼看出最小值的话，如1, 10, 7, 8）

def selectionSort(nums):
    for i in range(0, len(nums)):
        min = i
        for j in range(i + 1, len(nums)):
            if nums[j] < nums[min]:
                min = j # find the place of the min value in range(i + 1, len(nums))
        nums[i], num[min] = nums[min], nums[i] # swap current value with min value

public static void selectionSort(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        int min = i;
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] < nums[min]) {
                min = j;
            }
        }
        swap(nums, min, i);
    }

*插入排序：先从后面拎出一个元素i和前面已经排好序的j进行比较，如打牌的时候摸牌。

public static void insertionSort(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        int key = nums[i];
        int j = i - 1;
        while (j >= 0 && nums[j] > key) {
            nums[j + 1] = nums[j]; // shift bigger number to right
            j--; // compare previous
        }
        nums[j + 1] = key;
    }
}

交换法：

public static void swap(int[] nums, int a, int b) {
    int tmp = nums[a];
    nums[a] = nums[b];
    nums[b] = tmp;
}

public static void insertionSort1(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        for (int j = i; j > 0 && nums[j - 1] > nums[j]; j--) {
            swap(nums, j, j - 1);
        }
    }
}

*冒泡排序：i代表需要进行两两排序的数字(所以边界是数组长度减去一)，j代表剩下的需要排序的数字。

def bubbleSort(nums):
    for i in range(0, len(nums) - 1):
        for j in range(0, len(nums) - 1 - i):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]

# different boundary
def bubbleSort2(nums):
    for i in range(0, len(nums)):
        for j in range(1, len(nums) - i):
            if nums[j - 1] > nums[j]:
                nums[j], nums[j - 1] = nums[j - 1], nums[j]

桶排序：洗扑克牌，先按花色分成四堆，再排

Merge Sort:适合链表

排序算法比较

一个完整的插入排序和选择排序算法的运行时间比较：

包括产生测试用例/检查算法正确性的辅助函数：

• randomArray
• nearlySortedArray
• isSorted

计算时间的函数（使用到反射）：

• testSort

import java.util.Arrays;
import java.util.Random;
import java.lang.reflect.Method;

public class Sort {
    public static int[] randomArray(int n, int l, int r) {
        Random rand = new Random();
        if (l >= r) {
            throw new ArrayIndexOutOfBoundsException();
        }
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = rand.nextInt(r - l + 1) + l;
        }
        return arr;
    }

    public static int[] nearlySortedArray(int n, int swapTimes) {
        Random rand = new Random();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = i;
        }
        // swap several pairs in a sorted array
        for (int i = 0; i < swapTimes; i++) {
            int x = rand.nextInt(n); // the upper bound is exclusive
            int y = rand.nextInt(n);
            while (y == x)          // maybe add this to reduce self duplications
                y = rand.nextInt(n);
            swap(nums, x, y);
        }
        return nums;
    }

    public static boolean isSorted(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i + 1] < arr[i])
                return false;
        }
        return true;
    }

    public static void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }

    public static void insertionSort1(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int key = nums[i];
            int j = i - 1;
            while (j >= 0 && nums[j] > key) {
                nums[j + 1] = nums[j]; // shift bigger number to right
                j--; // compare previous
            }
            nums[j + 1] = key;
        }
    }

    public static void insertionSort1_1(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int key = nums[i];
            int j = i;
            while (j > 0 && nums[j - 1] > key) {
                nums[j] = nums[j - 1]; // shift bigger number to right
                j--; // compare previous
            }
            nums[j] = key;
        }
    }

    public static void insertionSort1_2(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int key = nums[i];
            int j;
            for (j = i; j > 0 && nums[j - 1] > key; j--) {
                nums[j] = nums[j - 1]; // shift bigger number to right
            }
            nums[j] = key;
        }
    }

    public static void insertionSort2(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            for (int j = i; j > 0 && nums[j - 1] > nums[j]; j--) {
                swap(nums, j, j - 1);
            }
        }
    }

    public static void selectionSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int min = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[min]) {
                    min = j;
                }
            }
            swap(nums, min, i); // swap the min value with current index
        }
    }

    public static void testSort(String sortName, int[] nums) throws Exception {
        Method method = Sort.class.getMethod(sortName, int[].class);
        long startTime = System.currentTimeMillis();
        method.invoke(null, nums);
        long timeElapsed = System.currentTimeMillis() - startTime;
        System.out.println(sortName + ": " + timeElapsed + " ms");
    }

    public static void main(String[] args) throws Exception {
        // create two test arrays
        int length = 100000;
        String[] func = {"insertionSort1", "insertionSort1_1", "insertionSort1_2",
                "insertionSort2", "selectionSort"};
        int[] random = Sort.randomArray(length, 1, length);
        int[] dummy = Arrays.copyOf(random, length);
        // System.arraycopy(random, 0, copy1, 0, length); //alternatives
        System.out.println("Dummy call:");
        Sort.testSort("insertionSort1", dummy); // dummy call


        System.out.println("Test Random Array:");
        for (int i = 0; i < func.length; i++) {
            int[] c = Arrays.copyOf(random, length);
            Sort.testSort(func[i], c);
        }

        System.out.println("Test Nearly Sorted Array:");
        int[] sorted = Sort.nearlySortedArray(length, 10);
        for (int i = 0; i < func.length; i++) {
            int[] s = Arrays.copyOf(sorted, length);
            Sort.testSort(func[i], s);
        }
    }
}

output: insertion比selection快的原因是insertion可以比较并且终止没有必要的操作（一旦找到合适的位置就会终止），所以效率较高，特别是数组元素近乎有序的时候，可以退化成O(n)，所以当数组元素较小或者有序的时候，可以使用插入排序。

// not sure why this happend(the first funciton call always cost more time), but I'm just make a dummy call here..
Dummy call:
insertionSort1: 1245 ms
Test Random Array:
insertionSort1: 937 ms
insertionSort1_1: 977 ms
insertionSort1_2: 970 ms
insertionSort2: 1700 ms
selectionSort: 4673 ms
Test Nearly Sorted Array:
insertionSort1: 1 ms
insertionSort1_1: 2 ms
insertionSort1_2: 2 ms
insertionSort2: 3 ms
selectionSort: 4628 ms