凉冰的手记
凉冰
2023-06-30
目录

排序

# 基础知识

# 分析排序算法

  • 排序算法的执行效率

    • 最好情况、最坏情况、平均情况时间复杂度
    • 时间复杂度的系数、常数 、低阶
      • 在对同一阶时间复杂度的排序算法性能对比的时候，我们就要把系数、常数、低阶也考虑进来。
    • 比较次数和交换（或移动）次数
      • 虽然冒泡、插入都是O(n^2^)，但是插入排序移动次数是少的，所有性能要优

  • 排序算法的内存消耗

    • 类似于空间复杂度
    • 新概念--原地排序
      • 指的是，空间复杂度为O(1)的排序算法

  • 排序算法的==稳定性==

    这个概念是说，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的==先后顺序不变==

    • 说明

      • 平时练习排序的时候都是利用整数来练习，所以稳定与否看不出来利弊，但是当我们对一个对象进行排序时，对象会有多个属性，这时稳定性就有很大作用了。

    • 订单排序

      • 要求——我们希望按照金额从小到大对订单数据排序。对于金额相同的订单，我们希望按照下单时间从早到晚有序。
      • 实现
        • 先按照下单时间给订单排序
        • 再按照订单金额重新排序
      • 这样，如果算法稳定的话，之前按时间排好序的订单在按照金额排序时，顺序不会发生变化。

# 有序度-逆序度

  • 有序度

    有序元素对：a[i] <= a[j], 如果i < j。

    • 1,2,3,4,5,6
      • 有序度为15，即n*(n-1)/2
      • 这种完全有序的数组的有序度叫作满有序度

  • 逆序度

    • 逆序度与有序度定义相反
    • 逆序度 = 满有序度 - 有序度

  • 例子——冒泡排序

    • 排序时，每交换一次，就会增加一个有序度，直到最后完全有序。
    • 所以总的交换次数是逆序度= 满有序度(n*(n-1)/2) - 初始有序度

# 基于比较的排序

# 冒泡排序-O(n^2^)

  • 算法原理

    ​ 从底部开始遍历，依次比较相邻元素的大小，如果下方元素大，则交换。这样一轮过后，最上方的元素肯定是最大的。在继续进行n-1轮就可以啦。

  • 算法性能

    • 空间复杂度——O(1)
    • 时间复杂度(最好、最坏、平均)——O(n)、O(n^2^)、O(n^2^)
    • 稳定
    • 交换次数较多

  • 代码

    //冒泡排序
public void bubbleSort(int[] nums) {
    int len = nums.length;
    if (len <= 1) {
        return;
    }
    //外层循环表示已经排序好的元素块
    for (int i = 0; i < len; i++) {
        boolean flag = false;//设置判断变量
        //内层循环表示从无序块中选拔一个最大的元素进入有序块中
        for (int j = 0;j < len - i -1; j++) {
            if (nums[j] > nums[j+1]) {
                swap(nums, j,j+1);
                flag = true;
            }
        }
        //当这一轮排序没有元素交换时，表示数组已经有序，不需要在进行排序了
        if (!flag) {
            break;
        }
    }
}

# 快速排序-O(nlogn)

  • 算法原理

    ​ 将大的序列不断的进行分区排序。

    ​ 分区时，找到一个中间值，使其左边都小于它，右边都大于它。不断的减小序列，直到最后剩下一个时，即截止。

  • 算法性能

    • 空间复杂度——O(1)
    • 时间复杂度(最好、最坏、平均)——O(nlogn)、O(n^2^)、O(nlogn)
    • 不稳定

  • 代码

    //快速排序
public void quickSort(int[] nums) {
    int len = nums.length;
    Qsort(nums, 0, len-1);
}
//递归函数
public void Qsort(int[] nums, int low, int high) {
    //递归终止条件
    if (low >= high) {
        return;
    }
    int mid = partition(nums, low, high);//找中枢
    Qsort(nums, low, mid-1);//排中枢左边
    Qsort(nums, mid+1, high);//排中枢右边

}
//找中间点-空间复杂度为1，直接在原数组上修改
// 双边循环
public int partition(int[] nums, int low, int high) {
    //三数取中，作为中枢值；将中间的放入low位置
    int mid = low + (high - low) / 2;
    if (nums[low] > nums[high]) {
        swap(nums, low, high);
    }
    if (nums[mid] > nums[high]) {
        swap(nums, mid, high);
    }
    if (nums[mid] > nums[low]) {
        swap(nums, mid, low);
    }
    int value = nums[low];//默认选取第一个为中枢值--这里用三数取中进行了优化，

    while (low < high) {
        //从右往左，大于中枢值的不动，小于的移动到low位
        while (high > low && nums[high] >= value) {
            high--;
        }
        nums[low] = nums[high];
        //从左往右，小于中枢值的不动，大于的移动到high位
        while (low < high && nums[low] <= value) {
            low ++;
        }
        nums[high] = nums[low];
    }
    //循环结束后，low和high指向一个位置，将该位置设为中枢值
    nums[low] = value;
    return low;
}

  • 如何在O(n)内查找数组内第K大元素

    ​ 利用快速排序中的分区思想，设中枢下标为x，若x+1=k，则说明x指向的值即为第k大值

    若`k<x+1`，则将x左半部分进行分区；若大于，则将x右半部分进行分区。

    ​ 知道最后找到 k=x+1 为止。

# 插入排序-O(n^2^)

  • 算法原理

    ​ 在前方构造一个有序元素块，不断的取出后方的无序块中第一个元素，插入到有序块中。

    ​ （通过不断的移动和交换，确保有序块的有序性）

  • 算法性能

    • 空间复杂度——O(1)
    • 时间复杂度(最好、最坏、平均)——O(n)、O(n^2^)、O(n^2^)
    • 稳定
    • 交换次数较少

  • 代码

    //直接插入排序
public void insertionSort(int[] nums) {
    int len = nums.length;
    if (len <= 1) {
        return;
    }
    //外层循环表示已经排序好的元素块
    for (int i = 1; i < len; i++) {
        //内层循环表示 无序元素块中的第一个(它-nums[i]=nums[j]) 在有序块中的排序过程
        //如果它比前面的小，就交换，否则就退出循环
        for (int j = i ; j > 0; j--) {
            if (nums[j] < nums[j-1]) {
                swap(nums,j,j-1);
            }else {
                break;
            }
        }
    }
}


    //直接插入排序1----性能更好，使用了移动而非交换，交换相当于多次移动

    public void insertionSort1(int[] nums) {
        int len = nums.length;
        if (len <= 1) {
            return;
        }
        int value;
        int j;
        //外层循环表示已经排序好的元素块
        for (int i = 1; i < len; i++) {
            value = nums[i];

            //内层循环表示无序 元素块中的第一个(它-nums[i]=value) 在有序块中的排序过程
            //如果它比左面小，左后的元素右移，直到不小或者到了数组开头，在将它插入到合适的位置
            for (j = i-1 ; j >= 0; j--) {
                if (value < nums[j]) {
                    //元素右移，覆盖掉待入队的值
                    nums[j+1] = nums[j];
                }else {
                    break;
                }
            }
            nums[j+1] = value;
        }
    }

# 希尔排序-O(nlogn--n^2^)

  • 算法原理

    ​ 基于插入排序；将原序列，按照跳跃分割的策略，分成若干个子序列。然后在这些子序列内进行，直接插入排序，可以保证序列基本有序，当增量为1时，最后一轮排序，可保证完全有序。

    ​ 跳跃分割策略：将相距某个增量的记录组成一个子序列，这样能保证子序列内分别进行直接插入排序后得到的结果是基本有序，而不是局部有序。

  • 算法性能

    • 空间复杂度——O(1)
    • 时间复杂度(最好、最坏、平均)——O()、O(n^2^)、O(nlogn——n^2^)
    • 不稳定——跳跃式排序

  • 代码

    • 增量为1的时候，就退化成了直接插入排序。
    • 增量的选取是一个非常难的问题。
    //希尔排序--- 将数组按照某个增量跳跃式分割
public void shellSort(int[] nums) {
    int len = nums.length;
    if (len <= 1) {
        return;
    }
    int value;//用来记录无序元素块中的第一个
    int j;
    int increment=len; //增量表示,开始时设为数组长度

    while (increment > 1) {
        increment = (increment/3) + 1;
        //外层循环表示已经排序好的元素块
        for (int i = increment; i < len; i++) {
            value = nums[i];

            //内层循环表示 无序元素块中的第一个(它） 在有序块中的排序过程
            //如果它比左面小，左后的元素右移，直到不小或者到了数组开头，在将它插入到合适的位置
            for (j = i - increment; j >= 0; j = j - increment) {
                if (value < nums[j]) {
                    //元素右移，覆盖掉待入队的值
                    nums[j + increment] = nums[j];
                }else {
                    break;
                }
            }
            nums[j + increment] = value;
        }

    }

}

# 选择排序-O(n^2^)

  • 算法原理

    ​ 将整个序列分已排序区间和未排序区间。选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

    ​ 极大减少了交换的次数。

  • 算法性能

    • 空间复杂度——O(1)
    • 时间复杂度(最好、最坏、平均)——O(n^2^)、O(n^2^)、O(n^2^)
    • 不稳定
    • 交换次数极少

  • 代码

    //选择排序
public void selectSort(int[] nums) {
    int len = nums.length;
    if (len <= 1) {
        return;
    }
    int min;//存储最小值
    int minIndex;//存储最小值下标

    //外层循环表示已经排序好的元素块
    for (int i = 0; i < len; i++) {
        minIndex = i;
        min = nums[i];
        //内层循环表示 从无序元素块中找到一个最小的 ，然后将它放到有序元素块的末尾 的过程
        for (int j = i + 1; j < len; j++) {
            if (nums[j] < min) {
                min = nums[j];
                minIndex = j;
            }
        }
        //相等说明无序块中的第一个就是最小的，不用交换
        if (minIndex != i) {
            swap(nums,i,minIndex);
        }
    }
}

# 归并排序-O(nlogn)

  • 算法原理

    ​ 我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

  • 算法性能

    • 空间复杂度——O(n)
    • 时间复杂度——突出一个稳定——(最好、最坏、平均)——O(nlogn)、O(nlogn)、O(nlogn)
    • 稳定排序

  • 程序

    • int mid = low + (high - low) / 2-----这样写是为了防止二者和过大导致溢出
    • 这里的等号表示稳定性---让左边的优先 if (nums[p1] <= nums[p2]) {
    //归并排序
public void mergeSort(int[] nums) {
    //统一函数入口
    int len = nums.length;
    Msort(nums,0,len-1);
}

//递归函数
public void Msort(int[] nums, int low, int high) {
    //先定义递归终止条件
    if (low >= high) {//这里写成== 无可厚非
        return;
    }
    //计算中值
    //mid=(low+high)/2-----下面的写法是为了防止二者和过大导致溢出
    int mid = low + (high - low) / 2;

    Msort(nums,low,mid); //分左边
    Msort(nums,mid+1,high);//分右边
    Merge(nums,low,mid,high);//合并左右两边

}

//合并
public void Merge(int[] nums, int low, int mid, int high){
    int len = high - low + 1;//要合并的数组长度
    int[] temps = new int[len];//申请新的数组，用来排序
    int p1 = low;//保留初始下标，最后将新数组，并到原数组中
    int p2 = mid + 1;
    int flag = -1;
    int i;
    //开始合并--直到有一边全部放入新数组
    for (i = 0; i < len; i ++) {
        //这里的等号表示稳定性---让左边的优先
        if (nums[p1] <= nums[p2]) {
            temps[i] = nums[p1++];
            if (p1 > mid) {
                flag = 0;
                break;
            }
        }else {
            temps[i] = nums[p2++];
            if (p2 > high) {
                flag = 1;
                break;
            }
        }
    }
    //将剩余数组的所有元素，依次写入即可
    for (i = i + 1;i < len; i++) {
        if (flag == 0) {//左边写完了，这次写右边剩余部分
            temps[i] = nums[p2++];
        }else {
            temps[i] = nums[p1++];
        }
    }
    //将排好序的数组 写入到原数组对应位置
    for (i = 0; i < len; i++) {
        nums[low + i] = temps[i];
    }
}

# ==练习题==

  • 问题

​ 现在你有 10 个接口访问日志文件，每个日志文件大小约 300MB，每个文件里的日志都是按照时间戳从小到大排序的。你希望将这 10 个较小的日志文件，合并为 1 个日志文件，合并之后的日志仍然按照时间戳从小到大排列。如果处理上述排序任务的机器内存只有 1GB，你有什么好的解决思路，能“快速”地将这 10 个日志文件合并吗？

  • 解答

1.申请10个40M的数组和一个400M的数组。

2.每个文件都读40M，取各数组中最大时间戳中的最小值。

3.然后利用二分查找，在其他数组中快速定位到小于/等于该时间戳的位置，并做标记。

4.再把各数组中标记位置之前的数据全部放在申请的400M内存中。

5.在原来的40M数组中清除已参加排序的数据。[可优化成不挪动数据，只是用两个索引标记有效数据的起始和截止位置]

6.对400M内存中的有效数据[没装满]做快排。 将排好序的直接写文件。

7.再把每个数组尽量填充满。

从第2步开始继续，直到各个文件都读区完毕。

​ 这么做的好处有： 1.每个文件的内容只读区一次，且是批量读区。比每次只取一条快得多。 2.充分利用了读区到内存中的数据。曹源 同学在文件中查找那个中间数是会比较困难的。 3.每个拷贝到400M大数组中参加快排的数据都被写到了文件中，这样每个数只参加了一次快排。

# 不基于比较的排序

# 桶排序-O(n)

  • 算法

    ​ 核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

  • 时间复杂度分析

    ​ 如果要排序的数据有 n 个，我们把它们均匀地划分到 m 个桶内，每个桶里就有 k=n/m 个元素。每个桶内部使用快速排序，时间复杂度为 O(k * logk)。

    ​ m 个桶排序的时间复杂度就是 O(m * k * logk)，因为 k=n/m，所以整个桶排序的时间复杂度就是 O(n*log(n/m))。

    ​ 当桶的个数 m 接近数据个数 n 时，log(n/m) 就是一个非常小的常量，这个时候桶排序的时间复杂度接近 O(n)。

  • 应用场景

    ​ 桶排序对要排序数据的要求是非常苛刻的。

    ​ 首先，要排序的数据需要很容易就能划分成 m 个桶，并且，桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。

    ​ 其次，数据在各个桶之间的分布是比较均匀的。在极端情况下，如果数据都被划分到一个桶里，那就退化为 O(nlogn) 的排序算法了。

    ​ 桶排序比较适合用在外部排序中。

  • 代码

    //桶排序
public void bucketSort(int[] nums) {
    int index = 0;
    //根据数据情况，划分为 5 个桶 ，每个桶用链表实现,将5个桶放到List集合中
    LinkedList<Integer> bucket1 = new LinkedList<>();
    LinkedList<Integer> bucket2 = new LinkedList<>();
    LinkedList<Integer> bucket3 = new LinkedList<>();
    LinkedList<Integer> bucket4 = new LinkedList<>();
    LinkedList<Integer> bucket5 = new LinkedList<>();

    List<LinkedList<Integer>> bucket = new LinkedList<>();
    bucket.add(bucket1);
    bucket.add(bucket2);
    bucket.add(bucket3);
    bucket.add(bucket4);
    bucket.add(bucket5);

    //遍历元素，放入桶中
    for (int num : nums) {
        if (num >= 0 && num <=9) {
            bucket1.add(num);
        }else if (num >= 10 && num <= 19) {
            bucket2.add(num);
        }else if (num >= 20 && num <= 29) {
            bucket3.add(num);
        }else if (num >= 30 && num <= 39) {
            bucket4.add(num);
        }else if (num >= 40 && num <= 49) {
            bucket5.add(num);
        }
    }

    //桶内归并排序--稳定
    for (LinkedList<Integer> list : bucket) {
        //记录每个桶排序后的元素
        int [] sortArray = mergeSort(list);
        //因为桶之间是有序的，所以直接按照桶序号，将桶内排好序的元素放入原数组即可
        for (int i = 0; i < list.size(); i++) {
            nums[index++] = sortArray[i];
        }
    }
}

  • 外部排序例子

    • 问题

      ​ 比如说我们有 10GB 的订单数据，我们希望按订单金额（假设金额都是正整数）进行排序，但是我们的内存有限，只有几百 MB，没办法一次性把 10GB 的数据都加载到内存中。这个时候该怎么办呢？

    • 解法

      1. 我们可以先扫描一遍文件，看订单金额所处的数据范围。
      2. 假设经过扫描之后我们得到，订单金额最小是 1 元，最大是 10 万元。我们将所有订单根据金额划分到 100 个桶里，第一个桶我们存储金额在 1 元到 1000 元之内的订单，第二桶存储金额在 1001 元到 2000 元之内的订单，以此类推。每一个桶对应一个文件，并且按照金额范围的大小顺序编号命名（00，01，02...99）。
      3. 理想的情况下，如果订单金额在 1 到 10 万之间均匀分布，那订单会被均匀划分到 100 个文件中，每个小文件中存储大约 100MB 的订单数据，我们就可以将这 100 个小文件依次放到内存中，用快排来排序。（10GB/100=100MB）
      4. 等所有文件都排好序之后，我们只需要按照文件编号，从小到大依次读取每个小文件中的订单数据，并将其写入到一个文件中，那这个文件中存储的就是按照金额从小到大排序的订单数据了。
      5. 针对这些划分之后还是比较大的文件，我们可以继续划分，比如，订单金额在 1 元到 1000 元之间的比较多，我们就将这个区间继续划分为 10 个小区间，1 元到 100 元，101 元到 200 元，201 元到 300 元....901 元到 1000 元。直到所有的文件都能读入内存为止。

# 计数排序-O(n)

  • 算法原理

    ​ 计数排序其实是桶排序的一种特殊情况。当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。

  • 算法实现

    • 问题

      ​ 假设只有 8 个考生，分数在 0 到 5 分之间。这 8 个考生的成绩我们放在一个数组 A[8]中，它们分别是：2，5，3，0，2，3，0，3。

    • 解决方案

      1. 最高分为5分，使用6个桶，0——5,我们使用大小为 6 的数组 C[6]表示桶。
        • C[6]内存储的并不是考生，而是对应的考生个数。
      2. 我们对 C[6]数组顺序求和。
        • C[k]里存储小于等于分数 k 的考生个数
      3. 我们从后到前依次扫描数组 A（为了稳定）。比如，当扫描到 3 时，我们可以从数组 C 中取出下标为 3 的值 7，也就是说 3 是数组 R 中的第 7 个元素（也就是数组 R 中下标为 6 的位置）。当 3 放入到数组 R 中后，小于等于 3 的元素就只剩下了 6 个了，所以相应的 C[3]要减 1，变成 6。
      4. 当我们扫描到第 2 个分数为 3 的考生的时候，就会把它放入数组 R 中的第 6 个元素的位置（也就是下标为 5 的位置）。当我们扫描完整个数组 A 后，数组 R 内的数据就是按照分数从小到大有序排列的了。

  • 应用场景

    ​ 计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。

    ​ 如果考生成绩精确到小数后一位，我们就需要将所有的分数都先乘以 10，转化成整数，然后再放到 9010 个桶内。再比如，如果要排序的数据中有负数，数据的范围是[-1000, 1000]，那我们就需要先对每个数据都加 1000，转化成非负整数。

  • 代码

    //计数排序
public void countingSort(int[] nums) {
    int len = nums.length;
    if (len < 1) {
        return;
    }

    //查找nums中的最大值
    final int SIZE = Arrays.stream(nums).max().getAsInt() + 1;


    //分数是0到5分，分为6个桶，用数组bucket来表示,
    // 数组下标表示分数，下标对应内容为改分数下学生个数
    //        final int SIZE = 6;//桶数
    int[] bucket = new int[SIZE];
    int[] sortArray = new int[len];// 用来存储排好序的数组

    //遍历原数组，给bucket赋初始值
    for (int num : nums) {
        bucket[num]++;
    }

    //将bucket数组求和
    for (int i = 1; i < SIZE; i++){
        bucket[i] += bucket[i - 1];
    }

    //倒序遍历数组（为了保证稳定），将原数组中元素，排列到新数组中
    for (int i = len - 1; i >= 0; i--) {
        //当读入第一个3的时候，bucket中的值为7，即意味着大于等于3的个数有7个，所有这个3要排入sortArray的第7位，即下标为6的位置
        int index = bucket[nums[i]] - 1;
        sortArray[index] = nums[i];
        //这个3 放入对应位置后，bucket中相应的值要减一，表示下一个3来的时候，大于等于这个新3的个数有6个
        bucket[nums[i]]--;
    }

    //将排好序的数组 复制到新数组中
    int index = 0;
    for (int num : sortArray) {
        nums[index++] = num;
    }
}

# 基数排序-O(n)

  • 算法原理

    ​ 将代排序数据按位分割，用稳定排序算法分别对每一位进行排序，从后往前排序，这样第一位的顺序排好后，整个数据的顺序即排列好。

    ​ 如果每位数据范围不是很大，可以采用之前的桶排序或者计数排序。

    ​ **如果数据不等长，可以采用尾部补齐的方式。**尾部不影响最终的顺序

  • 时间复杂度分析

    ​ 根据每一位来排序，我们可以用刚讲过的桶排序或者计数排序，它们的时间复杂度可以做到 O(n)。如果要排序的数据有 k 位，那我们就需要 k 次桶排序或者计数排序，总的时间复杂度是 O(k*n)。当 k 不大的时候，比如手机号码排序的例子，k 最大就是 11，所以基数排序的时间复杂度就近似于 O(n)。

  • 适用范围

    ​ 基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。

    ​ 除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。

  • 代码

    • 对电话号码进行排序
    • 对每一位采用计数排序
    //基数排序————对11位的手机号排序
public void radixSort(String[] nums) {
    final int SIZE = 11;
    int len = nums.length;
    int[] biteArray = new int[len];//用来存储每一位数字
    int index;//数组下标
    int[] sub;//原数组元素对应下标
    String[] newNum = new String[nums.length];//用来排序的新数组


    //对每一位用计数排序
    for (int i = SIZE - 1; i >= 0; i--) {
        index = 0;
        //读取每一位数字
        for (String num : nums) {
            //char 类型 转换成int型，默认是转换成 assic 码值
            biteArray[index++] = num.charAt(i) - '0';
        }
        //对每一位进行 计数排序
        sub = countingSortIndex(biteArray);

        //将原数组按照下标调换位置-----空间复杂度O(n)
        for (int j = 0; j < sub.length; j++) {
            newNum [j] = nums[sub[j]];
        }
        index = 0;
        for (String num : newNum) {
            nums[index++] = num;
        }

        //将原数组按照下标调换位置-----空间复杂度O(1)---不正确
        //            for (int j = 0; j < sub.length; j++) {
        //                if (j < sub[j]) {
        //                    //这个时候直接交换，不影响什么
        //                    swap(nums,j,sub[j]);
        //                }else if (j > sub[j] && j != sub[sub[j]]) {
        //                    //这个时候，说明位于 sub[j]的元素已经交换过了，再次交换会打乱顺序，
        //                    //所有要干两件事，第一交换的时候，去和已经交换之后的位置换
        //                    //第二，要记录下原值被交换的位置
        //                    swap(nums,j,sub[sub[j]]);
        //                    sub[j] = sub[sub[j]];
        //                }
        //            }
    }

}

==练习题==

  • 如何根据年龄给 100 万用户排序？

    • 解答

      ​ 我们假设年龄的范围最小 1 岁，最大不超过 120 岁。我们可以遍历这 100 万用户，根据年龄将其划分到这 120 个桶里，然后依次顺序遍历这 120 个桶中的元素。这样就得到了按照年龄排序的 100 万用户数据。

  • 题2

    • 题目

      ​ 假设我们现在需要对D,a,3,F,B,1,c,2,A,z这个字符串进行排序，要将小写字母的放到前面，大写字母放在最后，数字放在中间，不用排序算法，又该怎么解决呢？

    • 解答

      法1，可以用桶排序，设置三个桶，一个装小写字母，一个装数字，一个装大写字母，最后遍历一下，即可得到排好序的字符串。

      ​ 法2，使用快排的分区思想。第一次分区，认为只有小写和非小写。第二次分区，则将数字和大写字母分开。

      //法2 
//快排思想-分区
//参数说明，low，high为低位和高位指针
//lowc和highc 为满足条件的 要排在左侧 的 最小值和最大值
public int partition(StringBuffer str, int low, int high, char lowc, char highc) {
    char value = str.charAt(low);
    while (low < high) {
        //从右往左遍历，只要不在区间内就停
        while (high >= low && (str.charAt(high) < lowc || str.charAt(high) > highc)) {
            high--;
        }
        str.setCharAt(low,str.charAt(high));

        //从右往左遍历，只要不在区间内就停
        while (low <= high && str.charAt(low) >= lowc && str.charAt(low) <= highc) {
            low++;
        }
        str.setCharAt(high,str.charAt(low));
    }
    //循环结束，low和high执向同一位置，即为中枢值
    str.setCharAt(low,value);
    return low;
}
//字符串排序
public String stringSort(String nums) {

    //使用StringBuffer 就可以像数组一样操作字符串中某个值
    StringBuffer str = new StringBuffer(nums);

    //第一轮分区  区分小写和非小写
    int partition = partition(str, 0, nums.length() - 1, 'a', 'z');
    //判断中枢值是否合法
    char c = str.charAt(partition);
    if ( c >= 'a' && c <= 'z') {
        //中枢位置是小写字母
        partition++;
    }
    //第二轮分区  区分大写和数字
    partition(str, partition, nums.length() - 1, '0', '9');
    return str.toString();
}
#知识#算法
上次更新: 2023 07 3
图
二分查找

← 二分查找→

最近更新
01
数据层解决方案
07-03
02
第三方技术整合
07-03
03
原理篇
07-03
更多文章>
Theme by Vdoing | Copyright © 2023-2023 by 凉冰
FIND YOU
G_E_M_ 邓紫棋