算法

冒泡排序，选择排序
快速排序，插入排序，希尔，堆排序，归并排序，桶排序，计数，基数
时间与空间复杂度

排序算法

冒泡排序:两两交换，双重for循环

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;
    }
}

选择排序：每次选择一个最小的放第一位（与原本的第一位交换）双重for循环

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;
    }
}

直接插入排序：提出一个值并放在合适的位置,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){
        // 记录当前查找的数字
        int cur;
        // 从1开始  假设 0 已经是排好的
        for (int i = 1; i < arr.length; i++) {
            cur = arr[i];
            // 准备查找 i 之前的数字 如果有比i大的往后移动一位
            int index = i - 1;
            // 索引最小为0 并且 在此索引
            while (index >= 0 && arr[index] > cur){
                arr[index + 1] = arr[index];
                index --;
            }
            arr[++index] = cur;
        }
        return arr;
    }
}

桶排序

即计数排序 桶排可以优化 即减少桶的长度 可以传入最大值和最小值

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

    // 桶数组
    private int[] bucket;
    // 要进行排序的数组
    private int[] array;
    // 初始化成员变量
    public Bucketsort (int bucket, int[] array){
        this.bucket = new int[bucket];
        this.array = array;
    }
    // 将数组中和桶的索引相同的数字 装入桶中 并且将桶索引的值+1
    public Bucketsort sort(){
        for (int i = 0; i < array.length; i++) {
            bucket[array[i]]++;
        }
        return this;
    }
    // 输出桶中索引值大于0的所有排好的数字
    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){
            //因为基准数是从左边定义的所以要从右边先找
            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);
    }
}