怎么查看网站是否被百度惩罚降权或者被k,wordpress设置移动端模版,北海网站设计,wordpress主题导航排序也称排序算法(SortAlgorithm)#xff0c;排序是将一组数据#xff0c;依指定的顺序进行排列的过程。 分类
内部排序【使用内存】 指将需要处理的所有数据都加载到内部存储器中进行排序插入排序 直接插入排序希尔排序 选择排序 简单选择排序堆排序 交换排序 冒泡排序快速… 排序也称排序算法(SortAlgorithm)排序是将一组数据依指定的顺序进行排列的过程。 分类
内部排序【使用内存】 指将需要处理的所有数据都加载到内部存储器中进行排序插入排序 直接插入排序希尔排序 选择排序 简单选择排序堆排序 交换排序 冒泡排序快速排序 归并排序基数排序 外部排序法【使用内存和外存结合】 数据量过大无法全部加载到内存中需要借助外部存储文件等进行排序 时间复杂度
度量一个程序算法执行时间的两种方法
事后统计的方法 这种方法可行但是有两个问题一是要想对设计的算法的运行性能进行评测需要实际运行该程序二是所得时间的统计量依赖于计算机的硬件、软件等环境因素这种方式要在同一台计算机的相同状态下运行才能比较那个算法速度更快。 事前估算的方法 通过分析某个算法的时间复杂度来判断哪个算法更优
基本概念 时间频度 一个算法花费的时间与算法中语句的执行次数成正比例哪个算法中语句执行次数多它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为 T ( n ) T(n) T(n)。对于时间频度而言 常数项是可以忽略的 如 T ( n ) 2 n 10 T(n)2n10 T(n)2n10 和 T ( n ) 2 n T(n)2n T(n)2n的值是无限接近的 低次项是可以忽略的 如 T ( n ) 2 n 2 3 n 10 T(n)2n^23n10 T(n)2n23n10 和 T ( 2 n 2 ) T(2n^2) T(2n2) 无限接近 系数项在一定情况下可忽略 随着n值变大 5 n 2 7 n 5n^27n 5n27n 和 3 n 2 2 n 3n^22n 3n22n执行曲线重合说明这种情况下5和3可以忽略。而 n 3 5 n n^35n n35n 和 6 n 3 4 n 6n^34n 6n34n执行曲线分离说明多少次方式关键此时系数项不可忽略且结果比例无限接近 16 时间复杂度 一般情况下算法中的基本操作语句的重复执行次数是问题规模 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^27n6 T(n)n27n6 与 T ( n ) 3 n 2 2 n 2 T(n)3n^22n2 T(n)3n22n2 它们的 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^22n2 T(n)3n22n2 ➡️ T ( n ) 3 n 2 2 n 1 T(n)3n^22n1 T(n)3n22n1修改后的运行次数函数中只保留最高阶项 T ( n ) 3 n 2 2 n 1 T(n)3n^22n1 T(n)3n22n1 ➡️ 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)
常见的时间复杂度 常数阶 O ( 1 ) O(1) O(1) 无论代码执行了多少行只要没有循环等复杂结构那这个代码的时间复杂度就都是 O ( 1 ) O(1) O(1)2 对数阶 O ( log 2 n ) O(\log_2n) O(log2n) int i 1;
while(in) {i i * 2;
}在while循环里面每次都将i乘以2乘完之后i距离n就越来越近了。假设循环x次之后i就大于2了此时这个循环就退出了也就是说2的 x x x 次方等于n那么 x log 2 n x\log_2n xlog2n也就是说当循环 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时间上是根据代码变化的ii*3,则是 O ( log 3 n ) O(\log_3n) O(log3n). 线性阶 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)来表示它的时间复杂度 线性对数阶 O ( n log 2 n ) O(n\log_2{n}) O(nlog2n) for(m1; 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) n∗O(log2N)也就是了 O ( n log 2 N ) O(n\log_2N) O(nlog2N) 平方阶 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(n∗n)即 O ( n 2 ) O(n^2) O(n2)如果将其中一层循环的n改成m那它的时间复杂度就变成了O(m*n) 立方阶 O ( n 3 ) O(n^3) O(n3) k次方阶 O ( n k ) O(n^k) O(nk) 指数阶 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)1s2 O(ns)1s2不稳定 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的增大而增大当较大时将占用较多的存储单元例如快速排序和归并排序算法基数排序就属于这种情况在做算法分析时主要讨论的是时间复杂度。从用户使用体验上看更看重的程序执行的速度。一些缓存产品(redismemcache)和算法基数排序本质就是用空间换时间.
测试代码运行时间
// 创建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]; // 重置minminIndex 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 1if (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(按实际来分) 个元素)步长gapfor (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 后移lif (arr[r] pivot) {l 1;}}// 如果 l r必须lr--否则出现栈溢出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数组// 然后 tiif (arr[i] arr[j]) {temp[t] arr[i];t 1;i 1;} else { // 反之亦然temp[t] arr[j];t 1;j 1;}}// 2、把有剩余数据的一边的数据依次全部填充到tempwhile (i mid) { // 左边的有序序列还有剩余的元素就全部填充到temptemp[t] arr[i];t 1;i 1;}while (j right) { // 右边的有序序列还有剩余的元素就全部填充到temptemp[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.lengthint[][] 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) {// 取出元素放入到arrarr[index] bucket[k][l];}}// 第l轮处理后需要清空每个 bucketElementCounts[k] 的值bucketElementCounts[k] 0;}System.out.println(第 (i 1) 轮排序处理 arr Arrays.toString(arr));}}补充
稳定如果a原本在b前面而ab排序之后a仍然在b的前面不稳定如果a原本在b的前面而ab排序之后a可能会出现在b的后面内排序所有排序操作都在内存中完成外排序由于数据太大因此把数据放在兹盘中而排序通过磁盘和内存的数据传输才能进行时间复杂度一个算法执行所耗费的时间。空间复杂镀运行完一个程序所需内存的大小。n数据规模k“桶”的个数In-place不占用额外内存Out-place占用额外内存 当 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) ↩︎ 代码在执行的时候当它消耗的时间并不随着某个变量的增长而增长那么无论代码多长都可以用 O ( 1 ) O(1) O(1)表示它的时间复杂度 ↩︎
