排序

排序算法

冒泡排序

可以先这么想，

• 对于外层循环，就是五个数字要比较四轮（又例如，99个数字比较98轮），n 个数字比较n - 1轮。
• 对于内层循环，（以第一次循环的时候为例子）五个数字需要比较四次（才能将最大的那一个沉底），（以第一次循环的时候为例子）99个数字比较98次（才能将最大的那一个沉底）。

public void BubbleSort(int[] nums){
    //比如说5个数字，就总共比较四轮
    for (int i = 1; i < nums.length; i++) {
        //比如说5个数字，那么第一轮就比较四次
        for (int j = 0; j < nums.length - i; j++){
            //每一次都会和下面的数字进行比较
            if (nums[j] > nums[j + 1]) {
                int tmp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = tmp;
            }
        }
    }
}

选择排序

• 新的理解，将下标逐次赋给min_index的时候，并不需要把最后一个（即n - 1）赋给它，因为每次遍历已经将最小值置换到前面去了，最后一个肯定是最大的那一个

public void select_sort(int[] arr){
    int n = arr.length, min_index;
    for (int i = 0; i < n - 1; i++) {
        //这里相当于将每一个元素的下标逐个赋给min_index
        min_index = i;
        for (int j = i + 1; j < n; j++) {
            //将每一个元素和自己后面的元素进行比较（i前面的元素一定是每一轮中的最小值）
            if (arr[min_index] > arr[j]) {
                //然后记录最小元素的下标
                min_index = j;
            }
        }
        //通过本轮最小元素的下标将元素置换到前面去（每一轮的i）
        if(i != min_index){
            int tmp = arr[i];
            arr[i] = arr[min_index];
            arr[min_index] = tmp;
        }
    }
}

插入排序

这个版本的插入排序和希尔排序都挺好记忆的，（对我而言）是最优的版本

static void insert_sort(int[] arr) {
    int n = arr.length;
    //可以进行i = 1的优化，但是这个就很刻意了（追求时间复杂度）
    for (int i = 0; i < n; i++) {
        int j = i, v = arr[i];
        //这里只能是arr[j] =arr[--j];只能先减去，后赋值，不能j--
        while (j - 1 >= 0 && arr[j - 1] > v) arr[j] = arr[--j];
        arr[j] = v;
    }
}

希尔排序

static void shell_sort(int[] arr) {
    int gap = arr.length;
    while (gap > 1) {
        //每次到这里的时候才会/2操作，先判断再除法所以gap = 1的时候，仍然在里面
        gap /= 2;
        //其实可以将这里优化为 i = gap,因为如果i < gap的话它就会无效遍历
        //可以进行i = gap的优化，但是这个就很刻意了（追求时间复杂度）
        for (int i = 0; i < arr.length; i++) {
            int v = arr[i];
            //它将用于在数组中向后查找应该插入v的位置。
            int j = i;
            while (j - gap >= 0 && arr[j - gap] >= v) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = v;
        }
    }
}

归并排序

是我太无知了，将这个程序Debug了四五次，我还是把这个程序先背过吧，以后多写几遍慢慢理解

System.arraycopy();中的五个参数分别是：

源数组，（复制）起始位置，目的数组，（拷贝）起始位置，复制的长度。

public void merge_Sort(int l, int r){
    if (l >= r) return;
    int mid = (l + r) >> 1;
    merge_Sort(l, mid);
    merge_Sort(mid + 1, r);
    merge(l, mid, r);
}

public void merge(int l, int m, int r){
    int s = l;
    int j = m + 1;
    int idx = l;
    while (l <= m && j <= r){
        if (arr0[l] <= arr0[j]) arr1[idx] = arr0[l++];
        else arr1[idx] = arr0[j++];
        idx++;
    }
    while (l <= m) arr1[idx++] = arr0[l++];
    while (j <= r) arr1[idx++] = arr0[j++];
    if (r + 1 - s >= 0) System.arraycopy(arr1, s, arr0, s, r + 1 - s);
}

快速排序

它第一次循环下来肯定是左边的数字小于参考值，右边的数全部大于参考值，（参考值就可以完全归位了）

• 之前，我一直有一个疑问为啥要先从右边找（第一个比tmp小的值）呢？为啥我不可以从左边先找一个比参考值（tmp）大的数字呢

在进行循环比较的时候，一定是tmp <= arr[j]，如果忘了等于号就会导致从左边到右边第一个数字（也就是tmp）被选中交换

public static void quick_sort(int[] arr, int l, int r){
    if (l >= r) return;
    int i = l, j = r, tmp = arr[l];
    while (i < j){
        //从右边向着左边找一个比tmp小的数字
        while (tmp <= arr[j] && j > i) j--;
        //从左边向着右边找到第一个比tmp大的数字
        while (tmp >= arr[i] && j > i) i++;
        if (i < j){
            arr[i] ^= arr[j];
            arr[j] ^= arr[i];
            arr[i] ^= arr[j];
        }
    }
    //这两句相当于参考值和i,j相遇时候（小于参考值的那一个）进行交换
    arr[l] = arr[j];
    arr[j] = tmp;
    //其实就是j - 1终结的循环
    quick_sort(arr, l, j - 1);
    quick_sort(arr, j + 1, r);
}

• 当二者（i,j）相遇之后，那一个数字肯定比参考值小（tmp），才能进行交换操作，使得参考值左边的数字都小于自己，参考值右边的数字都大于自己。

桶排序

void bucketSort(int[] arr) {
       int min = 0x3f3f3f3f, max = -min;
       for(var e : arr) {
           min = Math.min(min, e);
           max = Math.max(max, e);
       }
       int bucketSize = (max - min) / arr.length + 1;  //根据区间范围和数量确定单个桶范围
       int bucketCount = (max - min) / bucketSize + 1;  //根据区间范围和单个桶的数量确定需要多少个桶
       List<Integer>[] lists = new ArrayList[bucketCount];
       Arrays.setAll(lists, e -> new ArrayList<>());
       for (var e : arr) {
           lists[(e - min) / bucketSize].add(e);  //类似于求多少个桶
       }
       for (var list : lists) list.sort(Comparator.comparing(e -> e));
       int idx = 0;
       for (int i = 0; i < bucketCount; i++) {
           for (var e : lists[i])
               arr[idx++] = e;
       }
   }

计数排序

不能处理负数,如果有负数就得加偏移量。

有一些像我之前写过的统计字符串中的字符那一道题目，应该也是10个中最简单的一个了

void countSort(int[] arr) {
        int n = arr.length;
        Integer[] array = new Integer[1000];
        for (var e : arr) {
            if (array[e] == null) array[e] = 1;
            else array[e] += 1;
        }
        int idx = 0;
        for (int i = 0; i < 1000; i++) {
            if (array[i] != null) {
                int cnt = array[i];
                while (cnt-- > 0) arr[idx++] = i;
            }
        }
    }

基数排序

核心思想: 用0~9表示位上面的数,总共10个桶,遍历maxLen次,每次遍历当前位,将每个数放到自己值的位置。时间复杂度稳定O(k * n),不能处理负数,如果有负数就得加偏移量。

void radixSort(int[] arr) {
    LinkedList<Integer>[] lists = new LinkedList[10];
    Arrays.setAll(lists, e -> new LinkedList<>());  //这里使用linkedList比较好,使用linkedlist方便删除
    int maxLen = -1;
    for (var e : arr) maxLen = Math.max(getLength(e), maxLen);
    for (int i = 1; i <= maxLen; i++) {
        for (var e : arr) lists[getIndexValue(i, e)].add(e);
        int idx = 0;
        for (var list : lists) {
            while (!list.isEmpty()) {
                arr[idx++] = list.poll();
            }
        }
    }
}

int getLength(int num) {
        int ans = 0;
        while (num > 0) {
            num /= 10;
            ans++;
        }
        return ans;
    }

int getIndexValue(int k, int num) {
        int res = num % 10;
        for (int i = 0; i < k; i++) {
            res = num % 10;
            num /= 10;
        }
        return res;
    }