数据结构排序算法

排序也称排序算法(SortAlgorithm),排序是将一组数据,依指定的顺序进行排列的过程

分类

  • 内部排序【使用内存】
    • 指将需要处理的所有数据都加载到内部存储器中进行排序
    • 插入排序
      • 直接插入排序
      • 希尔排序
    • 选择排序
      • 简单选择排序
      • 堆排序
    • 交换排序
      • 冒泡排序
      • 快速排序
    • 归并排序
    • 基数排序
  • 外部排序法【使用内存和外存结合】
    • 数据量过大,无法全部加载到内存中,需要借助外部存储(文件等)进行排序

时间复杂度

度量一个程序(算法)执行时间的两种方法

  • 事后统计的方法
    • 这种方法可行,但是有两个问题:一是要想对设计的算法的运行性能进行评测,需要实际运行该程序;二是所得时间的统计量依赖于计算机的硬件、软件等环境因素,这种方式,要在同一台计算机的相同状态下运行,才能比较那个算法速度更快
  • 事前估算的方法
    • 通过分析某个算法的时间复杂度来判断哪个算法更优

基本概念

  • 时间频度

    • 一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为 T ( n ) T(n) T(n)
    • 对于时间频度而言
      • 常数项是可以忽略的
        • 如: T ( n ) = 2 n + 10 T(n)=2n+10 T(n)=2n+10 T ( n ) = 2 n T(n)=2n T(n)=2n的值是无限接近的
      • 低次项是可以忽略的
        • 如: T ( n ) = 2 n 2 + 3 n + 10 T(n)=2n^2+3n+10 T(n)=2n2+3n+10 T ( 2 n 2 ) T(2n^2) T(2n2) 无限接近
      • 系数项在一定情况下可忽略
        • 随着n值变大, 5 n 2 + 7 n 5n^2+7n 5n2+7n 3 n 2 + 2 n 3n^2+2n 3n2+2n,执行曲线重合,说明这种情况下,5和3可以忽略。
        • n 3 + 5 n n^3+5n n3+5n 6 n 3 + 4 n 6n^3+4n 6n3+4n,执行曲线分离,说明多少次方式关键,此时系数项不可忽略,且结果比例无限接近 1:6
  • 时间复杂度

    • 一般情况下,算法中的基本操作语句的重复执行次数是问题规模 n n n的某个函数,用 T ( n ) T(n) T(n)表示,若有某个辅助函数 f ( n ) f(n) f(n),使得当 n 趋近于无穷大时, T ( n ) f ( n ) \frac{T(n)}{f(n)} f(n)T(n)的极限值为不等于零的常数1,则称 f ( n ) f(n) f(n) T ( n ) T(n) T(n)的同数量级函数。记作 T ( n ) = O ( f ( n ) ) T(n)=O(f(n)) T(n)=O(f(n)),称 O ( f n ) O(fn) O(fn) 为算法的渐进时间复杂度,简称时间复杂度。
    • T ( n ) T(n) T(n)不同,但时间复杂度可能相同。如: T ( n ) = n 2 + 7 n + 6 T(n)=n^2+7n+6 T(n)=n2+7n+6 T ( n ) = 3 n 2 + 2 n + 2 T(n)=3n^2+2n+2 T(n)=3n2+2n+2 它们的 T ( n ) T(n) T(n)不同,但时间复杂度相同,都为 O ( n 2 ) O(n^2) O(n2)
    • 计算时间复杂度的方法:
      • 用常数1代替运行时间中的所有加法常数 T ( n ) = 3 n 2 + 2 n + 2 T(n)=3n^2+2n+2 T(n)=3n2+2n+2 ➡️ T ( n ) = 3 n 2 + 2 n + 1 T(n)=3n^2+2n+1 T(n)=3n2+2n+1
      • 修改后的运行次数函数中,只保留最高阶项 T ( n ) = 3 n 2 + 2 n + 1 T(n)=3n^2+2n+1 T(n)=3n2+2n+1 ➡️ T ( n ) = 3 n 2 T(n)=3n^2 T(n)=3n2
      • 去除 最高阶项的系数 T ( n ) = 3 n 2 T(n)=3n^2 T(n)=3n2 ➡️ T ( n ) = n 2 T(n)=n^2 T(n)=n2 ➡️ O ( n 2 ) O(n^2) O(n2)

常见的时间复杂度

  1. 常数阶 O ( 1 ) O(1) O(1)

    无论代码执行了多少行,只要没有循环等复杂结构,那这个代码的时间复杂度就都是 O ( 1 ) O(1) O(1)2

  2. 对数阶 O ( log ⁡ 2 n ) O(\log_2n) O(log2n)

    int i = 1;
    while(i<n) {
        i = i * 2;
    }
    

    在while循环里面,每次都将i乘以2,乘完之后,i距离n就越来越近了。假设循环x次之后,i就大于2了,此时这个循环就退出了,也就是说2的 x x x 次方等于n,那么 x = log ⁡ 2 n x=\log_2n x=log2n也就是说当循环 log ⁡ 2 n \log_2n log2n次以后,这个代码就结束了。因此这个代码的时间复杂度为: O ( log ⁡ 2 n ) O(\log_2n) O(log2n) O ( log ⁡ 2 n ) O(\log_2n) O(log2n)的这个2时间上是根据代码变化的,i=i*3,则是 O ( log ⁡ 3 n ) O(\log_3n) O(log3n).

  3. 线性阶 O ( n ) O(n) O(n)

    for(int i = 0; i <= n; ++i) {
        j = i;
        j++;
    }
    

    这段代码,for循环里面的代码会执行n遍,因此它消耗的时间是随着n的变化而变化的,因此这类代码都可以用 O ( n ) O(n) O(n)来表示它的时间复杂度

  4. 线性对数阶 O ( n log ⁡ 2 n ) O(n\log_2{n}) O(nlog2n)

    for(m=1; m < n; m++) {
        i = 1;
        while(i < n) {
            i = i * 2;
        }
    }
    

    线性对数阶 O ( n log ⁡ 2 N ) O(n\log_2N) O(nlog2N)其实非常容易理解,将时间复杂度为 O ( log ⁡ 2 n ) O(\log_2n) O(log2n)的代码循环N遍的话,那么它的时间复杂度就是 n ∗ O ( log ⁡ 2 N ) n*O(\log_2N) nO(log2N),也就是了 O ( n log ⁡ 2 N ) O(n\log_2N) O(nlog2N)

  5. 平方阶 O ( n 2 ) O(n^2) O(n2)

    for(x = 1; i <= n; x++) {
        for(i = 1; i <= n; i++) {
            j = i;
            j++
        }
    }
    

    平方阶 O ( n 2 ) O(n^2) O(n2)就更容易理解了,如果把 O ( n ) O(n) O(n)的代码再嵌套循环一遍,它的时间复杂度就是 O ( n 2 ) O(n^2) O(n2),这段代码其实就是嵌套了2层n循环,它的时间复杂度就是 O ( n ∗ n ) O(n*n) O(nn),即 O ( n 2 ) O(n^2) O(n2)如果将其中一层循环的n改成m,那它的时间复杂度就变成了O(m*n)

  6. 立方阶 O ( n 3 ) O(n^3) O(n3)

  7. k次方阶 O ( n k ) O(n^k) O(nk)

  8. 指数阶 O ( 2 n ) O(2^n) O(2n)

常见的算法时间复杂度从小到大依次增加,其中 O ( n ! ) > O ( 2 n ) O(n!)>O(2^n) O(n!)>O(2n),随着问题规模 n n n的不断增大,上述时间复杂度不断增大,算法的执行效率越来越低,在日常开发中应尽可能避免使用指数阶的算法

平均时间复杂度和最坏时间复杂度

  • 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下,
    该算法的运行时间。
  • 最坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度
    均是最坏情况下的时间复杂度。这样做的原因是:最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限,这就保证了算法的运行时间不会比最坏情况更长。
  • 平均时间复杂度和最坏时间复杂度是否一致,和算法有关
排序平均时间最差情况稳定度额外空间备注
冒泡 O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2)稳定 O ( 1 ) O(1) O(1)n小时较好
交换 O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2)不稳定 O ( 1 ) O(1) O(1)n小时较好
选择 O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2)不稳定 O ( 1 ) O(1) O(1)n小时较好
插入 O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2)稳定 O ( 1 ) O(1) O(1)大部分已排序时较好
基数 O ( log ⁡ R B ) O(\log_RB) O(logRB) O ( log ⁡ R B ) O(\log_RB) O(logRB)稳定 O ( n ) O(n) O(n)B是真数(0-9)
R是基数(个十百)
Shell O ( n log ⁡ 2 n ) O(n\log_2n) O(nlog2n) O ( n s ) 1 < s < 2 O(n^s)1<s<2 O(ns)1<s<2不稳定 O ( 1 ) O(1) O(1)s是所选分组
快速 O ( n log ⁡ 2 n ) O(n\log_2n) O(nlog2n) O ( n 2 ) O(n^2) O(n2)不稳定 O ( n log ⁡ 2 n ) O(n\log_2n) O(nlog2n)n大时较好
归并 O ( n log ⁡ 2 n ) O(n\log_2n) O(nlog2n) O ( n log ⁡ 2 n ) O(n\log_2n) O(nlog2n)稳定 O ( 1 ) O(1) O(1)n大时较好
O ( n log ⁡ 2 n ) O(n\log_2n) O(nlog2n) O ( n log ⁡ 2 n ) O(n\log_2n) O(nlog2n)不稳定 O ( 1 ) O(1) O(1)n大时较好

空间复杂度

  • 类似于时间复杂度的讨论,一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间,它也是问题规模的函数。
  • 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模有关,它随着n的增大而增大,当较大时,将占用较多的存储单元,例如快速排序和归并排序算法,基数排序就属于这种情况
  • 在做算法分析时,主要讨论的是时间复杂度。从用户使用体验上看,更看重的程序执行的速度。一些缓存产品(redis,memcache)和算法(基数排序)本质就是用空间换时间.

测试代码运行时间

// 创建80000个随机的数组
int[] arr2 = new int[80000];
for (int i = 0; i < 80000; i++) {
    arr2[i] = (int) (Math.random() * 8000000);
}

Date date1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM--dd HH:mm:ss");
String date1Str = simpleDateFormat.format(date1);
System.out.println("排序前时间="+date1Str);

selectSort(arr2); // 选择排序
// BufferSort(arr2); // 冒泡排序

Date date2 = new Date();
SimpleDateFormat simpleDateFormat2 = new SimpleDateFormat("yyyy-MM--dd HH:mm:ss");
String date2Str = simpleDateFormat2.format(date2);
System.out.println("排序前时间="+date2Str);

冒泡排序

冒泡排序(Bubble Sorting)的基本思想是:通过对待排序序列从前向后(从下标较小的元素开始),依次比较相邻元素的值,若发现逆序则交换,使值较大的元素逐渐从前移向后部,就象水底下的气泡一样逐渐向上冒

因为排序的过程中,各元素不断接近自己的位置,如果一趟比较下来没有进行过交换,就说明序列有序,因此要在排序过程中设置一个标志 flag 判断元素是否进行过交换。从而减少不必要的比较。
请添加图片描述

// 冒泡排序 时间复杂度 O(n^2)
public static void BufferSort(int[] arr) {
    int temp = 0;
    // 标识变量,表示是否进行过交换
    boolean flag = false;
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                flag = true;
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        System.out.printf("第%d次循环:", i + 1);
        System.out.println(Arrays.toString(arr));
        if (!flag) {// 在一趟排序中,一次交换都没有发生过
            break;
        } else {
            flag = false; // 重置flag
        }
    }
}

选择排序

选择式排序也属于内部排序法,是从欲排序的数据中,按指定的规则选出某一元素,再依规定交换位置后达到排序的目的。

选择排序(select sorting)也是一种简单的排序方法。它的基本思想是:第一次从arr[0] ~ arr[n-1]中选取最小值,与arr[0]交换,第二次从arr[1] ~ arr[n-1]中选取最小值,与arr[1]交换,第三次从arr[2] ~ arr[n-1]中选取最小值,与arr[2]交换,…,第i次从arr[i-1] ~ arr[n-1]中选取最小值,与arr[i-1]交换,…,第n-1次从arr[n-2] ~ arr[n-1]中选取最小值,与arr[n-2]交换,总共通过n-1次,得到一个按排序码从小到大排列的有序序列。

// 选择排序 时间复杂度 O(n^2)
public static void selectSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i; // 最小值索引
        int min = arr[i]; // 最小值
        for (int j = i + 1; j < arr.length; j++) {
            if (min > arr[j]) {// 说明假定的最小值不是最小
                min = arr[j]; // 重置min
                minIndex = j; // 重置minIndex
            }
        }
        // 交换位置
        if (minIndex != i) {
            arr[minIndex] = arr[i];
            arr[i] = min;
        }
        System.out.printf("第%d次循环:", i + 1);
        System.out.println(Arrays.toString(arr));
    }
}

插入排序

插入式排序属于内部排序法,是对于欲排序的元素以插入的方式找寻该元素的适当位置,以达到排序的目的。

插入排序(Insertion Sorting)的基本思想是:把n个待排序的元素看成为一个有序表一个无序表开始时有序表中只包含一个元素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,把它的排序码依次与有序表元素的排序码进行比较,将它插入到有序表中的适当位置,使之成为新的有序表。

缺点:当需要插入的数是较小的数时,后移的次数明显增多,对效率有影响,可用希尔排序优化

// 插入排序
public static void insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        // 定义待插入的数
        int insertVal = arr[i];
        int insertIndex = i - 1; // 即arr[1]的前面这个数的下标

        // 给insertVal 找插入的位置
        // insertIndex >= 0 保证在给insertVal 找插入位置时不越界
        // insertVal < arr[insertIndex] 待插入的数,还没有找到插入位置
        while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
            arr[insertIndex + 1] = arr[insertIndex];  // arr[insertIndex] 后移
            insertIndex--;
        }
        // 当退出while循环时,说明插入的位置找到,insertIndex + 1
        if (insertIndex + 1 != i) {// 如果待插入值大于前一位值,则 insertIndex + 1 != i但是多了判读时间+交换时间,因此可加可不加
            arr[insertIndex + 1] = insertVal;
        }
        System.out.printf("第%d次循环:", i);
        System.out.println(Arrays.toString(arr));
    }
}

希尔排序

希尔排序是希尔(Donald Shell)于I959年提出的一种排序算法。希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序:随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止

请添加图片描述

交换法

比较值,一发现大小关系直接交换

希尔排序时,对有序序列在插入时采用交换法,速度较慢

// 希尔排序 -- 交换法
public static void shellSort(int[] arr) {
    int temp = 0;
    int count = 0; // 计数器【可不写】
    // 增量gap,并逐步的缩小增量
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < arr.length; i++) {
            // 遍历各组中所有的元素(共gap组,每组有 x(按实际来分) 个元素),步长gap
            for (int j = i - gap; j >= 0; j -= gap) {
                // 如果当前元素大于加上步长后的哪个元素,说明需要交换【从小到大】
                if (arr[j] > arr[j + gap]) {
                    temp = arr[j];
                    arr[j] = arr[j + gap];
                    arr[j + gap] = temp;
                }
            }
        }
        System.out.printf("希尔排序第%d次循环:", ++count);
        System.out.println(Arrays.toString(arr));
    }

}

移动法

比较值,发现关系大小时先不交换,后移值,继续比较,当找到合适的位置时再插入

希尔排序时,对有序序列在插入时采用移动法,速度快,推荐使用

希尔排序快的主要原因不在于数据的操作方式,而在于宏观调控

// 希尔排序 -- 移位法
public static void shellSort2(int[] arr) {
    int temp = 0;
    int count = 0; // 计数器【可不写】

    // 增量gap,并逐步的缩小增量
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        // 从第gap个元素,逐个对其所在的组进行直接插入排序
        for (int i = gap; i < arr.length; i++) {
            int j = i;
            temp = arr[j];
            if (arr[j] < arr[j - gap]) {
                while (j - gap >= 0 && temp < arr[j - gap]) {
                    // 后 移动
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                // 当退出while后,就给temp找到插入的位置
                arr[j] = temp;
            }
        }
        System.out.printf("希尔排序第%d次循环:", ++count);
        System.out.println(Arrays.toString(arr));
    }
}

快速排序法

快速排序(Quicksort)是对冒泡排序的一种改进。

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列

// 快速排序法1
public static void quickSort1(int[] arr, int left, int right) {
    int l = left; // 左下标
    int r = right; // 右下标
    int pivot = arr[(left + right) / 2];
    int temp = 0; // 临时变量
    // while循环目的是让比pivot 值小的放到左边,大的放右边
    while (l < r) {
        // 在pivot 的左边一直找,直到找到大于等于pivot 值才退出
        while (arr[l] < pivot) {
            l += 1;
        }
        // 在pivot 的右边一直找,直到找到小于等于pivot 值才退出
        while (arr[r] > pivot) {
            r -= 1;
        }
        // 如果l >= r说明pivot 的左右两的值,已经按照左边全部是
        // 小于等手pivot值,右边全部是大于等于pivot值
        if (l >= r) {
            break;
        }

        // 交换
        temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;

        // 如果交换完后发现这个arr[l] == pivot ,则 r 前移,r--
        if (arr[l] == pivot) {
            r -= 1;
        }
        // 如果交换完后发现这个arr[r] == pivot ,则 l 后移,l++
        if (arr[r] == pivot) {
            l += 1;
        }
    }
    // 如果 l == r,必须l++,r--,否则出现栈溢出
    if (l == r) {
        l += 1;
        r -= 1;
    }
    // 向左递归
    if (left < r) {
        quickSort1(arr, left, r);
    }

    // 向右递归
    if (right > l) {
        quickSort1(arr, l, right);
    }
}
// 快速排序法2
public static void quickSort2(int[] arr, int start, int end) {
    if (start < end) {
        // 标准数
        int stard = arr[start];
        // 记录下标
        int low = start;
        int high = end;
        // 循环找比标准数大的数和比标准数小的数
        while (low < high) {
            // 右边的数字比标准数大
            while (low < high && stard <= arr[high]) {
                high--;
            }
            // 使用右边的数字替换左边的数
            arr[low] = arr[high];
            // 如果左边的数字比标准数小
            while (low < high && arr[low] <= stard) {
                low++;
            }
            arr[high] = arr[low];
        }
        // 把标准数付给低位或高位
        arr[low] = stard;

        // 递归
        // 处理所有小的数字
        quickSort2(arr, start, low);
        // 处理所有大的数字
        quickSort2(arr, low + 1, end);
    }
}
// 快速排序法3
public static void quickSort3(int[] arr, int low, int high) {
    int i, j, stard, t;
    if (low > high) {
        return;
    }
    i = low;
    j = high;
    //temp就是基准位
    stard = arr[low];

    while (i < j) {
        //先看右边,依次往左递减
        while (stard <= arr[j] && i < j) {
            j--;
        }
        //再看左边,依次往右递增
        while (stard >= arr[i] && i < j) {
            i++;
        }
        //如果满足条件则交换
        if (i < j) {
            t = arr[j];
            arr[j] = arr[i];
            arr[i] = t;
        }

    }
    //最后将基准为与i和j相等位置的数字交换
    arr[low] = arr[i];
    arr[i] = stard;
    //递归调用左半数组
    quickSort3(arr, low, j - 1);
    //递归调用右半数组
    quickSort3(arr, j + 1, high);
}

快速排序之所比较快,因为相比冒泡排序,每次交换是跳跃式的。每次排序的时候设置一个基准点,将小于等于基准点的数全部放到基准点的左边,将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换,交换的距离就大的多了。因此总的比较和交换次数就少了,速度自然就提高了。当然在最坏的情况下,仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是 O ( N 2 ) O(N_2) O(N2),它的平均时间复杂度为 O ( N log ⁡ 2 N ) O(N\log_2N) O(Nlog2N)。其实快速排序也是基于一种叫做“二分”的思想。


归并排序

归并排序(MERGE-SOT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。

请添加图片描述

// 归并排序 - 分+合
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
    if (left < right) {
        int mid = (left + right) / 2; // 中间索引
        // 向左递归进行分解
        mergeSort(arr, left, mid, temp);
        // 向右递归进行分解
        mergeSort(arr, mid + 1, right, temp);
        // 合并
        merge(arr, left, mid, right, temp);
    }
}

// 归并排序 - 合
/**
 * @param arr   原始数组
 * @param left  左边有序序列的初始索引
 * @param mid   中间索引
 * @param right 右边索引
 * @param temp  做中转的数组
 */
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
    int i = left; // 初始化i,左边有序序列的初始索引
    int j = mid + 1; // 初始化j,右边有序序列的初始索引
    int t = 0; // 指向temp数组的当前索引

    // 1、先把左右两边(有序)的数据按照规则填充到temp数组
    // 直到左右两边的有序序列,有一边处理完毕为止
    while (i <= mid && j <= right) {
        // 如果左边的有序序列的当前元素,小于等于右边有序序列的当前元素
        // 即将左边的当前元素,填充到temp数组
        // 然后 t++,i++
        if (arr[i] <= arr[j]) {
            temp[t] = arr[i];
            t += 1;
            i += 1;
        } else { // 反之亦然
            temp[t] = arr[j];
            t += 1;
            j += 1;
        }
    }

    // 2、把有剩余数据的一边的数据依次全部填充到temp
    while (i <= mid) { // 左边的有序序列还有剩余的元素,就全部填充到temp
        temp[t] = arr[i];
        t += 1;
        i += 1;
    }
    while (j <= right) { // 右边的有序序列还有剩余的元素,就全部填充到temp
        temp[t] = arr[j];
        t += 1;
        j += 1;
    }

    // 3、将temp数组的元素拷贝到arr
    // 但不是每次都拷贝所有值
    t = 0;
    int tempLeft = left;
    System.out.println("tempLeft=" + tempLeft + "\tright=" + right);
    while (tempLeft <= right) {
        arr[tempLeft] = temp[t];
        t += 1;
        tempLeft += 1;
    }
}

合并的次数为数组长度-1


基数排序

空间换时间的经典算法,速度较快,具体速度看规模

  • 基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是通过键值的各个位的值,将要排序的元素分配至某些“桶”中,达到排序的作用
  • 基数排序法是属于稳定性的排序,基数排序法的是效率高的稳定性排序法
  • 基数排序(Radix Sort)是桶排序的扩展
  • 基数排序是1887年赫尔曼何乐礼发明的。它是这样实现的:将整数按位数切割成不同的数字,然后按每个位数分别比较。
  • 基数排序是对传统桶排序的扩展,速度很快
  • 基数排序是经典的空间换时间的方式,占用内存很大,当对海量数据排序时,容易造成OutOfMemoryError
  • 基数排序时稳定的。[注:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i] = r[j],且r[i] 在r[j] 之前,而在排序后的序列中,r[i] 仍在r[j] 之前,则称这种排序算法是稳定的;否则称为不稳定的]
  • **注意:**如果有负数的数组,一般不用基数排序来进行排序

基本思路

将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

第1轮排序:

  • 将每个元素的个位数取出,然后看这个数应该放在哪个对应下标的桶【会先创建十个桶】(一个桶对应一个一维数组)
  • 按照这个桶的顺序(从一维数组的下标依次取出数据,放入到原来的数组中)

第2轮排序:

  • 将每个元素的十位数取出,然后看这个数应该放在哪个对应下标的桶(一个桶对应一个一维数组)
  • 按照这个桶的顺序(从一维数组的下标依次取出数据,放入到原来的数组中)

第3轮排序:

  • 将每个元素的百位数取出,然后看这个数应该放在哪个对应下标的桶(一个桶对应一个一维数组)
  • 按照这个桶的顺序(从一维数组的下标依次取出数据,放入到原来的数组中)

// 基数排序【空间换时间的算法】
public static void radixSort(int[] arr) {
    // 得到数组中最大的位数
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    // 得到最大数的位数
    int maxLength = (max + "").length();

    // 定义一个二维数组,表示10个桶,每个桶就是一个一维数组
    // 为了防止放入数时数据溢出,因此每个桶大小定位arr.length
    int[][] bucket = new int[10][arr.length];
    int[] bucketElementCounts = new int[10]; // 记录每个桶放入的数据个数

    for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
        // 针对每个元素对应位进行排序处理,第一次是个位,第二次是十位,第三次是百位......
        // 循环取出数组放入桶中
        for (int j = 0; j < arr.length; j++) {
            // 取出每个元素的个位的值
            int digitOfElement = arr[j] / n % 10;
            // 放入到对应的桶中
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            bucketElementCounts[digitOfElement]++; // 更新记录桶的数据个数
        }
        // 按照这个桶的顺序(一维数组的下标依次取出数据,放入到原来的数组中)
        int index = 0;
        // 遍历每一桶,并将桶中的数据放入到原数组
        for (int k = 0; k < bucket.length; k++) {
            // 如果桶中有数据才放入到原数组
            if (bucketElementCounts[k] != 0) {
                // 循环该桶,即第k个桶放入
                for (int l = 0; l < bucketElementCounts[k]; l++) {
                    // 取出元素放入到arr
                    arr[index++] = bucket[k][l];
                }
            }
            // 第l轮处理后,需要清空每个 bucketElementCounts[k] 的值
            bucketElementCounts[k] = 0;
        }
        System.out.println("第" + (i + 1) + "轮,排序处理 arr=" + Arrays.toString(arr));
    }

}

补充

  • 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;
  • 不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面;
  • 内排序:所有排序操作都在内存中完成;
  • 外排序:由于数据太大,因此把数据放在兹盘中,而排序通过磁盘和内存的数据传输才能进行;
  • 时间复杂度:一个算法执行所耗费的时间。
  • 空间复杂镀:运行完一个程序所需内存的大小。
  • n:数据规模
  • k:“桶”的个数
  • In-place:不占用额外内存
  • Out-place:占用额外内存

  1. T ( n ) f ( n ) \frac{T(n)}{f(n)} f(n)T(n)​​的值无限趋近于 1 1 1​​时,此时 f ( n ) = O ( 1 ) f(n)=O(1) f(n)=O(1)​​ ↩︎

  2. 代码在执行的时候,当它消耗的时间并不随着某个变量的增长而增长,那么无论代码多长,都可以用 O ( 1 ) O(1) O(1)​​表示它的时间复杂度 ↩︎

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/552405.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

两阶段提交进阶

两阶段提交之进阶 上一节我们讲了&#xff0c;两阶段提交逻辑上的表现&#xff0c;其实较为肤浅&#xff0c;并且偏向理论&#xff0c;可能大家都能看懂&#xff0c;但是如果放入实际的mysql应用中并联系事务和日志进行分析&#xff0c;又会怎么样呢&#xff1f; 这次就专门分…

Unity类银河恶魔城学习记录13-1 p142 Save system源代码

Alex教程每一P的教程原代码加上我自己的理解初步理解写的注释&#xff0c;可供学习Alex教程的人参考 此代码仅为较上一P有所改变的代码 【Unity教程】从0编程制作类银河恶魔城游戏_哔哩哔哩_bilibili FileDataHandler.cs using System; using System.IO; using UnityEngine; p…

软考133-上午题-【软件工程】-软件项目估算

一、COCOMO 估算模型 COCOMO 模型是一种精确的、易于使用的成本估算模型。 COCOMO 模型按其详细程度分为&#xff1a;基本 COCOMO 模型、中级 COCOMO 模型和详细 COCOMO 模型。 1&#xff09;基本 COCOMO 模型 基本 COCOMO 模型是一个静态单变量模型&#xff0c;用于对整个软…

内衣裤洗衣机如何选购?掌握这六个挑选技巧,轻松选购!

这两年内衣裤洗衣机可以称得上较火的小电器&#xff0c;小小的身躯却有大大的能力&#xff0c;一键可以同时启动洗、漂、脱三种全自动为一体化功能&#xff0c;在多功能和性能的提升上&#xff0c;还可以解放我们双手的同时将衣物给清洗干净&#xff0c;让越来越多小伙伴选择一…

node基础 第二篇

01 ffmpeg开源跨平台多媒体处理工具&#xff0c;处理音视频&#xff0c;剪辑&#xff0c;合并&#xff0c;转码等 FFmpeg 的主要功能和特性:1.格式转换:FFmpeg 可以将一个媒体文件从一种格式转换为另一种格式&#xff0c;支持几乎所有常见的音频和视频格式&#xff0c;包括 MP…

Node Version Manager(nvm):轻松管理 Node.js 版本的利器

文章目录 前言一、名词解释1、node.js是什么&#xff1f;2、nvm是什么&#xff1f; 二、安装1.在 Linux/macOS 上安装2.在 Windows 上安装 二、使用1.查看可安装的node版本2.安装node3. 查看已安装node4.切换node版本5.其它 总结 前言 Node.js 是现代 Web 开发中不可或缺的一部…

docker-compose 安装MongoDB续创建用户及赋权

文章目录 1. 问题描述2. 分析2.1 admin2.2 config2.3 local 3. 如何连接3.解决 1. 问题描述 在这一篇使用docker-compose创建MongoDB环境的笔记里&#xff0c;我们创建了数据库&#xff0c;但是似乎没有办法使用如Robo 3T这样的工具去连接数据库。连接的时候会返回这样的错误&…

c语言,单链表的实现----------有全代码!!!!

1.单链表的定义和结构 单链表是一种链式的数据结构&#xff0c;它用一组不连续的储存单元存反线性表中的数据元素。链表中的数据是以节点的形式来表示的&#xff0c;节点和节点之间相互连接 一般来说节点有两部分组成 1.数据域 &#xff1a;数据域用来存储各种类型的数据&…

基于SpringBoot+Vue的疾病防控系统设计与实现(源码+文档+包运行)

一.系统概述 在如今社会上&#xff0c;关于信息上面的处理&#xff0c;没有任何一个企业或者个人会忽视&#xff0c;如何让信息急速传递&#xff0c;并且归档储存查询&#xff0c;采用之前的纸张记录模式已经不符合当前使用要求了。所以&#xff0c;对疾病防控信息管理的提升&a…

windows 如何安装 perl ?

链接&#xff1a;https://strawberryperl.com/ 我们选择安装 “草莓 perl” 下载后根据引导安装就行了

node.jd版本降级/升级

第一步.先清空本地安装的node.js版本 按健winR弹出窗口&#xff0c;键盘输入cmd,然后敲回车&#xff08;或者鼠标直接点击电脑桌面最左下角的win窗口图标弹出&#xff0c;输入cmd再点击回车键&#xff09; 进入命令控制行窗口&#xff0c;输入where node&#xff0c;查看本地…

双指针的引入和深入思考(持续更新中)

目录 1.引入双指针 2.使用场景 3.例题引入 1.引入双指针 当我们需要维护某个区间性质的或者是求满足某些性质的区间的长度时&#xff0c;对于一个区间是由左右端点的&#xff0c;我们有简单的枚举左右端点的O()的时间的做法&#xff0c;当时在大多数题目中是不可行的&#…

DataX案例,MongoDB数据导入HDFS与MySQL

【尚硅谷】Alibaba开源数据同步工具DataX技术教程_哔哩哔哩_bilibili 目录 1、MongoDB 1.1、MongoDB介绍 1.2、MongoDB基本概念解析 1.3、MongoDB中的数据存储结构 1.4、MongoDB启动服务 1.5、MongoDB小案例 2、DataX导入导出案例 2.1、读取MongoDB的数据导入到HDFS 2…

论文笔记:Does Writing with Language Models Reduce Content Diversity?

iclr 2024 reviewer评分 566 1 intro 大模型正在迅速改变人们创造内容的方式 虽然基于LLM的写作助手有可能提高写作质量并增加作者的生产力&#xff0c;但它们也引入了算法单一文化——>论文旨在评估与LLM一起写作是否无意中降低了内容的多样性论文设计了一个控制实验&…

Kubernetes部署应用利器Helm详解

文章目录 一、helm概述&安装1.为什么需要Helm2.Helm介绍3.Helm架构4.部署Helm客户端5.Helm基本使用5.1 创建Chart示例 二、Helm 应用部署、升级1.创建项目&#xff08;chat所需目录、文件&#xff09;2.创建/拷贝项目的yaml文件到templates目录下3.使用Helm进行部署项目4.H…

第十五届蓝桥杯复盘python大学A组——试题B 召唤数学精灵

按照正常思路解决&#xff0c;由于累乘消耗大量时间&#xff0c;因此这不是一个明智的解决方案。 这段代码执行速度非常慢的原因在于它试图计算非常大的数的阶乘&#xff08;累乘&#xff09;&#xff0c;并且对于每一个i的值都执行这个计算。阶乘的增长是极其迅速的&#xff…

49.HarmonyOS鸿蒙系统 App(ArkUI)Tab导航组件的使用

HarmonyOS鸿蒙系统 App(ArkUI)Tab导航组件的使用 图片显示 Row() {Image($r(app.media.leaf)).height(100).width(100)Image($r(app.media.icon)).height(100).width(100) } 左侧导航 import prompt from ohos.prompt; import promptAction from ohos.promptAction; Entry C…

vue2知识点1 ———— (vue指令,vue的响应式基础)

vue2的知识点&#xff0c;更多前端知识在主页&#xff0c;还有其他知识会持续更新 Vue 指令 Vue指令是Vue.js中的一个重要概念&#xff0c;用于向DOM元素添加特定行为或功能。Vue指令以v-开头&#xff0c;例如v-bind、v-if、v-for等。 v-bind 动态绑定属性 用法&#xff1a…

windows ubuntu 子系统:肿瘤全外篇,2. fq 数据质控,比对。

首先我们先下载一组全外显子测序数据。nabi sra库&#xff0c;随机找了一个。 来自受试者“16177_CCPM_1300019”(SRR28391647, SRR28398576)的样本“16177_CCPM_1300019_BB5”的基因组DNA配对端文库“0369547849_Illumina_P5-Popal_P7-Hefel”的Illumina随机外显子测序 下载下…

SGI_STL空间配置器源码剖析(一)总览

SGI 全称为 Silicon Graphics [Computer System] Inc. 硅图[计算机系统] 公司&#xff0c;SGI_STL是SGI实现的C的标准模板库。 SGI STL的空间配置器包括一级和二级两种。 一级空间配置器allocator采用malloc和free来管理内存&#xff0c;这与C标准库中提供的allocator是相似的…