提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  .Net

当前栏目

线性时间非比较类排序

2023-02-18 16:36:15 时间
原理：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。
 
图解：
桶排序：
计数排序：
 
基数排序： 
 
 
代码示例：
 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
 
public class MySort2 {
 
    /**
     * 基本概念：
     * 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
     * <p>
     * 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
     * <p>
     * 内排序：所有排序操作都在内存中完成；（in-place 占用常数内存，不占用额外内存）
     * 举例：为了将arr排序，借用了一个temp的临时变量，开辟了一个临时空间，这个空间是常数量，这就是in-place
     * <p>
     * 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行（out-place 占用额外内存）
     * 举例：把排序时把数组中的数按顺序放入了一个新的数组，我就开了一个n规模大小的数组，这个就与数据规模有关。
     *
     * @param args
     */
    public static void main(String[] args) {}
 
    /**
     * 桶排序（又称箱排序）
     * <p>
     * 原理：划分多个范围相同的区间，每个子区间自排序，最后合并.
     * 设置一个定量的数组当作空桶；
     * 遍历输入数据，并且把数据一个一个放到对应的桶里去；
     * 对每个不是空的桶进行排序；
     * 从不是空的桶里把排好序的数据拼接起来。
     * <p>
     * 缺点：桶排序需要尽量保证元素分散均匀，否则当所有数据集中在同一个桶中时，桶排序失效
     * <p>
     * 分析：
     * 时间复杂度：
     * 最好：O(n+k)
     * 最坏：O(n^2)
     * 平均时间复杂度: O(n+k)
     * 空间复杂度: O(n+k)
     * 稳定性：稳定（其稳定性是根据桶内排序使用的算法）
     * <p>
     *
     * @param arr
     */
    public static void bucketSort(int[] arr) {
        //计算最大值最小值
        int max = arr[0], min = arr[0];
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }
 
        // 计算桶的数量
        int bucketNum = (max - min) / arr.length + 1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
        for (int i = 0; i < bucketNum; i++) {
            bucketArr.add(new ArrayList<Integer>());
        }
 
        // 将每个元素放入桶
        for (int i = 0; i < arr.length; i++) {
            int num = (arr[i] - min) / (arr.length);
            bucketArr.get(num).add(arr[i]);
        }
        // 对每个桶进行排序
        for (int i = 0; i < bucketArr.size(); i++) {
            Collections.sort(bucketArr.get(i));
        }
 
        // 将桶中的元素赋值到原序列
        int index = 0;
        for (int i = 0; i < bucketArr.size(); i++) {
            for (int j = 0; j < bucketArr.get(i).size(); j++) {
                arr[index++] = bucketArr.get(i).get(j);
            }
        }
        System.out.println(Arrays.toString(arr));
    }
 
    /**
     * 计数排序
     * <p>
     * 原理：
     * <p>
     * 分析：
     * 时间复杂度：
     * 最好：O(d*(n+r))
     * 最坏：O(d*(n+r))
     * 平均时间复杂度: O(d*(n+r))
     * 空间复杂度: O(n+r)
     * 稳定性：稳定
     * d 为位数，r 为基数，n 为原数组个数
     * <p>
     *
     * @param arr
     */
    public static void countingSort(int[] arr) {
        if (arr == null || arr.length < 2)
            return;
 
//        第一种方法，这种方法实际上应该算是用了三次N循环完成排序，单是空间上会出现比较大的问题，
//        就是如果[1,2,90,120,300],那么实际上会新开辟300个位置的数组但是数据却只有五个.
//        但是目测java在定义数组的时候要求规定长度，这个还没有想到处理方案
        int max = arr[0], min = arr[0], offset;
        //获取最大值与最小值
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max)
                max = arr[i];
            if (arr[i] < min)
                min = arr[i];
        }
        offset = 0 - min;
        //根据最大值和最小值的范围来设置一个包含所有数的桶用于存放数据
        int[] bucket = new int[max - min + 1];
        for (int i = 0; i < arr.length; i++) {
            bucket[arr[i] + offset]++;
        }
        int index = 0, i = 0;
 
        //循环直至桶内的数据全部拿出
        while (index < arr.length) {
            if (bucket[i] != 0) {
                arr[index] = i - offset;
                bucket[i]--;
                index++;
            } else
                i++;
        }
        System.out.println(Arrays.toString(arr));
 
    }
 
    /**
     * 基数排序
     * <p>
     * 原理：
     * 基数排序是按照低位先排序，然后收集；
     * 再按照高位排序，然后再收集；
     * 依次类推，直到最高位。
     * 有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
     * 基数排序基于分别排序，分别收集，所以其是稳定的排序算法
     * <p>
     * 分析：
     * 时间复杂度：
     * 最好：O(d*(n+r))
     * 最坏：O(d*(n+r))
     * 平均时间复杂度: O(d*(n+r))
     * 空间复杂度: O(n+r)
     * 稳定性：稳定
     * d 为位数，r 为基数，n 为原数组个数
     * <p>
     *
     * @param arr
     * @return
     */
    public static void radixSort(int[] arr) {
        if (arr == null || arr.length < 2)
            return;
 
        //获取最大值
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        //计算最大值的位数
        int maxDigit = String.valueOf(max).length();
 
        //建立10个数据存储的队列
        List<ArrayList> queue = new ArrayList<ArrayList>();
        for (int i = 0; i < 10; i++) {
            queue.add(new ArrayList<Integer>());
        }
        ArrayList<Integer> temp = null;
        System.out.println("原始数据");
        System.out.println(Arrays.toString(arr));
        for (int i = 0, mod = 10, div = 1; i < maxDigit; i++, mod *= 10, div *= 10) {
            //将数组的数按照位的数放入对应的基队列
            for (int j = 0; j < arr.length; j++) {
                int num = (arr[j] % mod) / div;
                temp = queue.get(num);
                temp.add(arr[j]);
            }
 
            int count = 0;//元素计数器
            //将存放在队列里面的数全部再次放回到数组里面进行第二轮排序
            for (int k = 0; k < 10; k++) {
                while (queue.get(k).size() > 0) {
                    temp = queue.get(k);
                    arr[count] = temp.get(0);
                    temp.remove(0);
                    count++;
                }
            }
            System.out.println("第" + (i + 1) + "次排序后");
            System.out.println(Arrays.toString(arr));
        }
    }
}
 

相关文章