Java陣列三大基本排序

1、冒泡排序
2、選擇排序
3、插入排序
個人思路，大家互相參考，討論
排序是把一堆陣列有小到大、由大到小從頭到尾按照一定的順序排列起來的，（全部以從小到大排列討論）

1、冒泡排序

冒泡排序指陣列中的從頭開始的元素兩個兩個相比，陣列中的一二相比、二三相比、三四相比········
每兩個數相比完就排一次，排完后，再比較下一個（二三相比）一直向下····直到排序完成，
按照這樣的方式依次向下比較排序，通過這樣的排序，可以直接把陣列中的最大值直接排到陣列最后，則下一次的排序，可以不用管最后一個陣列比較，這樣可以大幅優化代碼時間復雜度，

import java.util.Arrays;

public class Demo1 {
    public static void main(String[] args){
        int [] a = new int[] {3,4,2,1,1,5};
        //                    4 3 2 1 1 5
        //                    3 2 1 1 4 5
        //                    2 1 1 3 4 5
        //                    1 1 2 3 4 5
        for (int i = 0; i < a.length-1; i++) {
            for (int j = 0; j < a.length-1-i; j++) {
                if (a [j] > a [j+1]){
                    //加不加等于號，對于在陣列相等情況下的排序不造成任何影響
                    int num;
                    num = a[j] + a[j+1];
                    a[j] = num - a[j];
                    a[j+1] = num - a[j+1];
                    /*這是另一種交換資料的方法
                    num = a[j+1];
                    a[j+1] = a[j];
                    a[j] = num;     */
                }
            }
        }
        //列印輸出陣列中的元素
        System.out.println(Arrays.toString(a));
    }
}

外層回圈控制陣列中的元素從第一個開始往后每一個都比較到
內層回圈控制陣列比較的元素與后面的每一個元素進行一一對比

輸出結果為

2、選擇排序

陣列從頭開始的元素與其后的所有元素依次比較，選擇最小的放在其比較的元素位置，
選擇排序同冒泡排序一樣，每次排序后都會確定之前那的元素不會再改變，之所以之前的元素可以不用再參與回圈，同樣可以減少時間復雜度

import java.util.Arrays;

public class Demo1 {
    public static void main(String[] args) {
        int [] a = {4,5,1,2,3};
        //          5,4,1,2,3
        //          1,4,5,2,3
        //          1,2,4,5,3
        //          1,2,3,5,4
        //          1,2,3,4,5
        for (int i = 0; i < a.length - 1; i++) {//外層回圈，控制第幾個數字開始相比較
            for (int j = i+1; j < a.length; j++) {
                //內層回圈，控制int i 與之后的數字相比較（是int i之后的元素相比較）
                if ( a[i] > a[j]){
                    int num = a[i];
                    a[i] = a[j];
                    a[j] = num;
                }
            }
        }
        System.out.println(Arrays.toString(a));
    }
}

輸出結果為
也可以借用C語言指標的思想，來看這個問題，在回圈內部傳遞陣列的下標，這樣更能減少一些時間復雜度（這里是用空間復雜度的增加，減少時間復雜度）

import java.util.Arrays;

public class Demo1 {
    public static void main(String[] args) {
        int[] a = {5,4,1,2,3};
        for (int i = 0; i < a.length-1; i++) {//外層回圈，把 i 設為最小值
            int min = i;
            for (int j = i+1; j < a.length; j++) {//與之后的數相比，把第 j 個數字設為min
                if (a[min] > a[j]){
                    min = j;//只進行位置的交換
                }
            }
            //交換第i個數字和min的陣列交換
            int temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        }
        System.out.println(Arrays.toString(a));
    }
}

3、插入排序

就是從陣列中的第二個數字開始回圈，從當前這個數開始向前依次比較，一旦發現比它小的，就進行交換，
插入排序就好比，打牌時，整理牌時，從最左邊的第二個開始看起，把現在看的牌跟之前的牌依次從右到做依次比較，直到找到比一張牌小時，就可以停止了，把這張牌放到這個位置即可，插入排序的思想就和這個一樣理解即可，

import java.util.Arrays;

public class Demo1 {
    public static void main(String[] args) {
        int[] a = {4,3,2,5,1};
        //外層回圈，控制第幾個數字進行回圈
        for(int i = 1; i < a.length; i++) {
            //內層回圈控制進行與之前的比較
            for (int j = i; j > 0; j--) {
                if (a[j-1] > a[j]){
                    int t = a[j-1];
                    a[j-1] = a[j];
                    a[j] = t;
                }else {
                    break;//一旦前面的沒有這個數字大時，即可結束內層回圈，減少時間復雜度
                }
            }
        }
        System.out.println(Arrays.toString(a));
    }
}

同選擇排序一樣，插入排序也可以用空間復雜度來換取時間復雜度，
插入排序代碼對初學者，可能難懂，詳細注釋在代碼注釋里有詳細決議

import java.util.Arrays;

public class Demo1 {
    public static void main(String[] args) {
        int a[] = {3,4,2,1,5};
        for (int i = 0; i < a.length-1; i++) {
            int place = i;  //計數當前排序的位置,初始值是當前排序位置的前一個
            int data = a[i+1];//記錄當前所要比較位置的資料，從陣列中的第二個開始
            while (place >=0 && a[place]>data){
        //判斷當前回圈計數在回圈體內，并且前面的元素比調取的元素data大，執行回圈
                a[place+1] = a[place];//把前面的小值賦值給后面的
                place --;//前面的陣列位置向前推進一個
            }
            a[place + 1] = data;
    //把當前比較的元素放到回圈判斷結束后的位置，因為回圈結束完前還多減了一個place，在這補上
        }
        System.out.println(Arrays.toString(a));
    }
}

好了，這就是用Java實作三大經典排序，歡迎大家討論，