冒泡排序忙上，選擇排序
快速排序，插入排序闲坎，希爾，堆排序茬斧，歸并排序腰懂，桶排序，計(jì)數(shù)项秉，基數(shù)
時(shí)間與空間復(fù)雜度

排序算法

冒泡排序:兩兩交換绣溜，雙重for循環(huán)

public class Bubble {
    public static void main(String[] args) {
        int[] arr = {1,233,546,43,2};
        System.out.println(Arrays.toString(bubble(arr)));
    }

    public static int[] bubble(int arr[]){
        //冒泡排序
        int len = arr.length;
        int Max;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len - 1; j++) {
                if(arr[j] < arr[j+1]){
                    Max = arr[j+1];
                    arr[j+i] = arr[j];
                    arr[j] = Max;
                }
            }
        }
        return arr;
    }
}

選擇排序：每次選擇一個(gè)最小的放第一位（與原本的第一位交換）雙重for循環(huán)

public class XuanZhe {
    public static void main(String[] args) {
        int[] arr = {1,233,546,43,2};
        System.out.println(Arrays.toString(xuanZhe(arr)));
    }
    public static int[] xuanZhe(int arr[]){
        // 選擇排序
        int len = arr.length;
        int Max = arr[0];
        int index = 0;
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                if(arr[i] < arr[j]){
                    Max = arr[j];
                    arr[j] = arr[i];
                    arr[i] = Max;
                }
            }
        }

        return arr;
    }
}

直接插入排序：提出一個(gè)值并放在合適的位置,for + while

public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {6,1,2,7,9,3,4,5,10,8};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static int[] insertionSort(int[] arr){
        // 記錄當(dāng)前查找的數(shù)字
        int cur;
        // 從1開始  假設(shè) 0 已經(jīng)是排好的
        for (int i = 1; i < arr.length; i++) {
            cur = arr[i];
            // 準(zhǔn)備查找 i 之前的數(shù)字 如果有比i大的往后移動一位
            int index = i - 1;
            // 索引最小為0 并且 在此索引
            while (index >= 0 && arr[index] > cur){
                arr[index + 1] = arr[index];
                index --;
            }
            arr[++index] = cur;
        }
        return arr;
    }
}

桶排序

即計(jì)數(shù)排序 桶排可以優(yōu)化 即減少桶的長度 可以傳入最大值和最小值

public class Bucketsort {
    // 桶排序 &  箱排序

    // 桶數(shù)組
    private int[] bucket;
    // 要進(jìn)行排序的數(shù)組
    private int[] array;
    // 初始化成員變量
    public Bucketsort (int bucket, int[] array){
        this.bucket = new int[bucket];
        this.array = array;
    }
    // 將數(shù)組中和桶的索引相同的數(shù)字 裝入桶中 并且將桶索引的值+1
    public Bucketsort sort(){
        for (int i = 0; i < array.length; i++) {
            bucket[array[i]]++;
        }
        return this;
    }
    // 輸出桶中索引值大于0的所有排好的數(shù)字
    public Bucketsort sortPrt(){
        int index = 0;
        for (int i = 0; i < bucket.length; i++) {
            for(int j = 0; j < bucket[i]; j++){
               array[index++] = i;
            }
        }
        System.out.println(Arrays.toString(array));
        return this;
    }

    public static void main(String[] args) {
        int[] array = {1,10,8,9,5,2};

        new Bucketsort(11, array).sort().sortPrt();
    }
}

快速排序

image

public class QuickSort {
    //快速排序 效率比通常排序高
    public static void main(String[] args) {
        int[] arr = {6,1,2,7,9,3,4,5,10,8};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
    public static void quickSort(int[] arr, int low, int high) {
        if(low > high){
            return;
        }
        int i = low,
                j = high,
                temp = arr[low],
                reser;

        while (i < j){
            //因?yàn)榛鶞?zhǔn)數(shù)是從左邊定義的所以要從右邊先找
            if(temp <= arr[j] && i < j){
                j--;
            }
            if(temp >= arr[i] && i < j){
                i++;
            }

            if(i < j){
                reser = arr[j];
                arr[j] = arr[i];
                arr[i] = reser;
            }
        }
        arr[low] = arr[i];
        arr[i] = temp;
        quickSort(arr,  low,  i - 1);
        quickSort(arr, i + 1, high);
    }
}