冒泡晦款、插入炎功、選擇排序是最基礎(chǔ)的三種算法，這三種算法的最差復(fù)雜度都是O(n^2)缓溅，相對(duì)來說還是比較低效的蛇损。后面還會(huì)介紹O(nlogn)復(fù)雜度的算法。

圖片來源：極客時(shí)間

相關(guān)代碼如下：

package com.program;


public class Sort {

    /**
     * 冒泡排序
     * 時(shí)間復(fù)雜度：最好n,最壞情況下n^2
     * 空間復(fù)雜度：O(1)
     */
    public void bubbleSort(int[] data) {
        if (data == null || data.length == 0) {
            return;
        }
        int n = data.length;
        int k = 0;
        for (int i = 0; i < n; i++) {
            boolean flag = false;
            //注意這里需要減1坛怪，否則會(huì)角標(biāo)越界
            for (int j = 0; j < n - i - 1; j++) {
                k++;
                if (data[j] > data[j + 1]) {
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                    flag = true;
                }
            }
            //如果這一趟沒有數(shù)據(jù)交換了淤齐，那么一定是完全有序了。
            if (!flag) {
                break;
            }
        }
        System.out.println("\nk is " + k);
    }

    /**
     * 插入排序
     * 核心思想：將數(shù)據(jù)分為兩部分袜匿，一部分是有序的更啄，一部分是無序的，然后將無序的挨個(gè)兒往有序里插沉帮，插著插著就有感覺了锈死。
     * 空間復(fù)雜度：O(1)
     * 時(shí)間復(fù)雜度：最好n,最壞n^2
     * 說起來簡單贫堰，實(shí)際上很容易出錯(cuò)，just do it
     */
    public void insertionSort(int[] data) {
        if (data == null || data.length == 0) {
            return;
        }
        int n = data.length;
        //外面的循環(huán)是無序列表
        int m = 0;
        for (int i = 1; i < n; i++) {
            int value = data[i];
            //為了方便搬動(dòng)數(shù)據(jù)待牵，這里最好選擇從后往前遍歷插
            int j = i - 1;
            //里邊的循環(huán)是有序列表
            for (; j >= 0; j--) {
                //找到了插入的位置其屏，在插入之前需要搬遷數(shù)據(jù)
                m++;
                if (value < data[j]) {
                    data[j + 1] = data[j];
                } else {
                    break;
                }
            }
            data[j + 1] = value;
            for (int k = 0; k < data.length; k++) {
                System.out.print(data[k] + " ");
            }
            System.out.println("\n");
        }
        System.out.println("總共執(zhí)行了" + m + "次");
    }

    /**
     * 選擇排序
     * 核心思想：和插入排序很類似，都分為兩區(qū)缨该，有序區(qū)&無序區(qū)偎行，只不過不是從無序中往有序中插，
     * 而是從無序中選擇一個(gè)最小的放在有序區(qū)的末尾贰拿，over.
     * 空間復(fù)雜度：O(1)
     * 時(shí)間復(fù)雜度：O(n^2)
     * 缺點(diǎn):不夠穩(wěn)定
     */
    public void selectionSort(int[] data) {
        if (data == null || data.length == 0) {
            return;
        }
        int n = data.length;
        for (int i = 0; i < n; i++) {
            int min = data[i];
            int tempPosition = i;
            //找出最小數(shù)的位置
            for (int j = i; j < n - i; j++) {
                if (data[j] < min) {
                    min = data[j];
                    tempPosition = j;
                }
            }
            //最小數(shù)添加到后面
            if (tempPosition != i) {
                int temp = data[i];
                data[i] = data[tempPosition];
                data[tempPosition] = temp;
            }
        }
        for (int k = 0; k < data.length; k++) {
            System.out.print(data[k] + " ");
        }
    }


    public static void main(String[] args) {
        int[] data = new int[]{10,9,8,7,6,5,4,3,2,1};
        Sort sort = new Sort();
        //sort.bubbleSort(data);
        //sort.insertionSort(data);
        sort.selectionSort(data);
    }
}