用一首诗来总结下常见排序算法及其时间复杂度和稳定性：

选泡插
快归堆希统计基
恩方恩老恩一三
对恩加K恩乘K
不稳稳稳不稳稳
不稳不稳稳稳稳

常见排序算法 .png

如何写算法程序：

1. 由简单到复杂
   • 验证一步走一步
   • 多打印中间结果
2. 先局部后整体
   • 没思路时先细分
3. 先粗糙后精细
   • 变量更名
   • 语句合并
   • 边界处理

• 选择排序
  最简单但是最没用的算法：时间复杂度高O(n*n)，但是不稳定，基本不用。

public class SelectionSort {
    public static void main(String[] args){
        int[] arr = {4,7,1,3,8,2,9};
        int minPos;


        for (int i = 0; i < arr.length - 1; i++) {
            minPos = i;
            for (int j = i + 1; j < arr.length; j++) {
                minPos = arr[j] < arr[minPos] ? j : minPos;
            }

            System.out.println("minPos:" + minPos);
            swap(arr,i,minPos);
            System.out.println("这是经过第:" + i + "次循环后数组的内容");
            print(arr);
        }
    }

    static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    static void print(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

• 验证算法的正确性：对数器
  生成一个足够大的随机数组，copy一份相同的数据。用确定正确的算法对数组排序，再使用自己的算法对copy的数组排序。生成多次随机数进行操作，如果每次排序后两个数组的数据排序结果都完全一样，证明自己的算法是正确的。

public class DataCheck {
    
    public static void main(String[] args){
        check();
    }

    private static void check() {
        int[] arr = generateRandomArray();
        int[] arr2 = new int[arr.length];
        System.arraycopy(arr,0,arr2,0,arr.length);
        Arrays.sort(arr);
        SelectionSort.sort(arr2);
        boolean same = true;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != arr2[i]){
                same = false;
            }
        }
    }

    private static int[] generateRandomArray() {
        Random random = new Random();
        int[] arr = new int[10000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(10000);
        }
        return arr;
    }
}

• 冒泡排序
  平均时间复杂度是O(n*n)，最好时间复杂度是O(n)，是稳定的。基本不用冒泡排序，因为要两两比较，太慢。

public class BubbleSort {

    public static void main(String[] args){
        int[] arr = {9,6,1,3,5};
        sort(arr);
        print(arr);
    }

    private static void print(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print( arr[i] + " ");
        }
    }

    private static void sort(int[] arr) {
        for (int i = arr.length - 1;i > 0;i--){
            for (int j = 0;j < i ;j++){
                if (arr[j] > arr[j + 1]){
                    swap(arr,j,j +1);
                }
            }
        }
    }
    
    private static void swap(int[] arr,int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

• 插入排序
  对于基本有序的数组最好用，是稳定的

public class InsertionSort {

    public static void main(String[] args){
        int[] arr = {9,6,1,3,5};
        sort(arr);
        print(arr);
    }

    private static void print(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            System.out.print( arr[i] + " ");
        }
    }

    private static void sort(int[] arr) {
        for (int i = 1;i < arr.length;i++){
            for (int j = i;j > 0;j--){
                if (arr[j] < arr[j - 1]){
                    swap(arr,j,j - 1);
                }
            }
        }
    }

    private static void swap(int[] arr,int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}