鸣谢B站up主 烂牌_ 讲的很好,就是基数排序负数的时候有点问题,本篇博客进行了小小的修复。放心食用

选择排序

原理

遍历元素找到一个最小(或最大)的元素,把它放在第一个位置,然后再在剩余元素中找到最小(或最大)的元素,把它放在第二个位置,依次下去,完成排序。

时间复杂度


平均:O(nn)
最好:O(n
n)
最坏:O(n*n)

空间复杂度

O(1)

代码

public static void selectSort(int[] arr){
    for (int i = 0; i < arr.length - 1; i++) {
        int minIdx =i;
        for (int j = i+1; j < arr.length; j++) {
            if (arr[j]<arr[i]){
                minIdx = arr[minIdx]< arr[j]?minIdx:j;
            }
        }
        if (minIdx!=0 && minIdx !=i){
            int tmp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = tmp;
        }
    }
}

或者

public static void selectSort2(int[] arr){
    for (int i = 0; i < arr.length - 1; i++) {
        int minIdx =i;
        for (int j = i+1; j < arr.length; j++) {
            if (arr[j]<arr[minIdx]){
                minIdx = j;
            }
        }
        if (minIdx!=0 && minIdx !=i){
            int tmp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = tmp;
        }
    }
}

归并排序

原理

分而治之的思想,先分割,再合并

时间复杂度

平均:O(nn)
最好:O(n
n)
最坏:O(n*n)

空间复杂度

O(1)

代码

我这里分割的时候计算mid用了位运算,其实就相当于/2, 但效率更高。

public static void split(int[] arr, int low, int high, int[] tmp){
    if (low <high){
        int mid = (low+high)>>1;
        split(arr, low,  mid, tmp);
        split(arr,mid+1,high, tmp);
        // 合并
        mergeSort(arr, low, mid, high, tmp);
    }
}
public static void mergeSort(int[] arr, int low, int mid, int high, int[] tmp){
    int i=low, j=mid+1,t=0;

    // 遍历mid分隔开的两部分,将他们有序的合起来,放到tmp, 这也是为什么要保存一份low , high
    while (i<=mid && j<=high){
        if (arr[i] <= arr[j]){
            tmp[t++] = arr[i++];
        }else{
            tmp[t++]  = arr[j++];
        }
    }
    // 下面的两个连续的循环,每次只有一个会进去,单边的还是有序的,所以他才有胆量只接放到tmp
    // 如果左边还有
    while (i<=mid){
        tmp[t++] = arr[i++];
    }
    // 如果右边还有
    while (j<=high) {
        tmp[t++] = arr[j++];
    }

    // 填充到arr数组指定位置,
    t = 0;
    while ((t+low)<=high){
        arr[low+t] = tmp[t];
        t++;
    }
}

基数排序

基数排序是比较稳定的一种排序算法,取决于最大的数的位数。

原理

将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。

时间复杂度

平均时间复杂度,最好最坏都是O(nxk)

空间复杂度

O(n+k)

代码

改进前

基础代码是这样的,但下面的代码不支持负数,需要做一下改进

public static void redixSort(int[] arr) {

    int[][] bucket = new int[10][arr.length-1];
    int[] bucketElementCounts = new int[10];
    int max = 0;
    for (int i = 0; i < arr.length; i++) {
        max = arr[i] > max ? arr[i] : max;
    }
    // 获取最大的数的长度
    int maxLength = (max + "").length();

    for (int i = 0; i < maxLength; i++) {
        // 将每一次取的位数的元素放到bucket中,每一次循环的bucket中存放的是当前遍历的个位十位或者百位的结果
        for (int j = 0; j < arr.length; j++) {
            //                int digit = getDigit(arr[j], i);
            int digit = arr[j]/ (int) Math.pow(10,i)%10;

            bucket[digit][ bucketElementCounts[digit]] = arr[j];
            bucketElementCounts[digit]++;
        }
        printDemision(bucket);

        // 将元素从bucket中取出来
        int index = 0;
        for (int j = 0; j < bucketElementCounts.length; j++) {
            if (bucketElementCounts[j]!=0){
                for (int k = 0; k < bucketElementCounts[j]; k++) {
                    arr[index++] = bucket[j][k];
                }
            }
            bucketElementCounts[j] = 0;
        }
    }
}

改进后

下面的代码判断了数组中是否有负数,有负数的话所有的diget+10,不会出现数组越界。

public static void redixSort(int[] arr) {
    int[][] bucket = new int[20][arr.length-1];
    int[] bucketElementCounts = new int[20];
    int max = 0;boolean flag= false;
    for (int i = 0; i < arr.length; i++) {
        max = arr[i] > max ? arr[i] : max;
        if (!flag){
            flag = arr[i]<0;
        }
    }
    // 获取最大的数的长度
    int maxLength = (max + "").length();

    for (int i = 0; i < maxLength; i++) {
        // 将每一次取的位数的元素放到bucket中,每一次循环的bucket中存放的是当前遍历的个位十位或者百位的结果
        for (int j = 0; j < arr.length; j++) {
            //                int digit = getDigit(arr[j], i);
            int digit = arr[j]/ (int) Math.pow(10,i)%10;
            if (flag){
                digit=digit+10;
            }
            bucket[digit][ bucketElementCounts[digit]] = arr[j];
            bucketElementCounts[digit]++;
        }
        printDemision(bucket);

        // 将元素从bucket中取出来
        int index = 0;
        for (int j = 0; j < bucketElementCounts.length; j++) {
            if (bucketElementCounts[j]!=0){
                for (int k = 0; k < bucketElementCounts[j]; k++) {
                    arr[index++] = bucket[j][k];
                }
            }
            bucketElementCounts[j] = 0;
        }
    }
}

工具类

private static void printDemision(int[][] arr){
    int rows = arr.length;
    int cols = arr[0].length;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            System.out.print(arr[i][j] + " ");
        }
        System.out.println();
    }
}

// 一串数字2345,i=,0的时候要求取得5,i=1取得4 ,i=2取得3,i=3取得2,i=4取得0,i=5取得0,要求在不转字符串的前提下,请用java实现,2345不是固定的,请用参数number来表示
public static int getDigit(int number, int position) {
    if (position < 0) {
        throw new IllegalArgumentException("位置不能为负数");
    }

    int divisor = (int) Math.pow(10, position);
    return (number / divisor) % 10;
}

参考文献

堆排
知乎文章 八大排序算法
排序算法 b站视频

分类: java

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

ICP备案号: 辽ICP备20003309号