- 1unity Audio 基础知识二 Audio Mixer_audiomixer
- 2xss漏洞的修复建议/方法_xss漏洞修复
- 3Axure教程-新手入门基础(小白强烈推荐！！！)_axure 使用教程
- 42020大学生网络知识大赛总决赛个人12——18急救包（最后还是肝完了，累~）_有a个程序员和b个程序员激励师。程序员的代码能力可以用一个整数来表示,越大表示
- 5Java中可变长参数的使用及注意事项_java可变参数坑
- 6linux 定位 踩内存_通过系统调用，内核断点方法定位用户进程被内核踩内存的问题...
- 7python selenium-webdriver 通过cookie登陆（十一）_webdriver 跳到新页面的cookie
- 8vue使用element ui 表格el-table-column里面做判断_el-table-column 判断参数是否存在
- 9ip地址、子网掩码及ip地址的相关计算_子网掩码和ip地址的换算
- 10大数据、数据仓库、数据湖、ELT和ETL、数据集成_大数据湖 大数据池
【数据结构——9大基础排序】一文掌握九大经典排序（配有详细图文说明！！！）_数据结构九大排序
赞
踩
插入排序
直接插入排序
- 算法基本思想：（从大到小排序）
在一个非递减的有序数组中，要新增一个元素x，有两个方法：
1.从数组的头部开始向后遍历，寻找第一个比x 大的元素y，从y元素开始的所有元素全部向后移动，最后将x元素插入数组。（×）
2.从数组的尾部开始向后向前遍历，寻找第一个比x小的元素k，从k元素开始，后面每个元素都向后移动，最后将元素x插入数组。（√）
那么我们应该选择哪种方式呢？
其实仔细思考一下，我们很容易会想到选择第2种方式，原因也很简单：在寻找第一个比x小的元素k时，我们可以边把比 x 大的元素往后移动。
因此，我们对一个数组排序时，可以从第2个元素开始，看作是把元素插入一个已经有序的数组中。
具体代码如下：
public static void insertSort1(int[] array) { for(int i = 1; i < array.length; i++) { // 记录 i 下标的元素，防止比 i下标 大的元素向后移动将其覆盖 int tmp = array[i]; // 从下标为 i-1的元素开始遍历， 比 array[i]大的元素都向后移动 int j = i -1; for(; j >= 0; j--) { if(array[j] > tmp) { array[j+1] = array[j]; } else { // 此时array[j] < array[i]，且 j + 1下标 为 array[i] 在已排序元素中的位置 break; } } array[j+1] = tmp; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
时间复杂度：O(n²)。最好情况是数组已经有序，只需比较n-1次，时间复杂度为O(n)；最坏情况是数组为待排序顺序的逆序，需要(n-1)(n-1)…1次，时间复杂度为O(n²)。
空间复杂度：O(1)。记录每次待排序的元素的额外空间。
稳定性：稳定。
适用情况：数组基本有序的情况下。
折半插入排序
-
算法基本思想：（从大到小排序）
折半插入排序的本质也是在一个已经有序的数组的插入一个元素，与直接插入排序的唯一区别是：折半插入排序是利用二分查找找到那个合适的插入位置。 -
二分查找的基本步骤：
将要插入元素跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为0（即 left>right ，数组中不存在指定元素）。
注意事项：
（1）若插入元素在数组不存在（如上图所示情况），则插入元素的下标应为 right+1，因此需要将 right+1 下标 开始的所有元素全部向后移动。
（2）若插入元素与 mid 下标的元素相等，为了操作的统一性，我们可以使 right=mid-1，这样一来，待插入元素的下标也为 right+1 ，接下来同样将 right+1 下标 开始的所有元素全部向后移动。
具体代码实现如下：
public static void binaryInsertSort(int[] array) { for (int i = 1; i < array.length; i++) { int left = 0, right = i - 1; int mid = (left + right) / 2; int target = array[i]; // 待插入的元素 // 1. 找到合适的插入位置 while(left <= right) { mid = (left + right) / 2; if(array[mid] < target) left = mid + 1; // 出现 array[mid] == target,同样进行此操作，可保证 元素插入下标的一致性 else right = mid -1; } // 2. 在已排序好的数组区间中，将mid开始的元素，从后向前依次向后移动 for (int j = i - 1; j >= right + 1; j--) { array[j+1] = array[j]; } // 3. 将 array[i] 插入到 mid 位置 array[right + 1] = target; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
时间复杂度：O(n²)。在平均情况下，折半插入排序 的元素移动次数与 直接插入排序 相同， 仅减少了元素间的比较次数，因此时间复杂度仍为O(n²)。
空间复杂度：O(1)。记录每次待排序的元素的额外空间。
稳定性：稳定。
适用情况：数组基本有序且数组元素较多，可一定程度减少元素间的比较次数。
希尔排序(缩小增量排序)
- 算法基本原理:
希尔排序本质上是一种优化的"插入排序"，其主要思想是“分组”和“缩小增量”。
“分组”即将一个待排序的数组分为多组数据，对每组数据分别进行插入排序，使得当前排序完成后，每个小组的数据变得局部有序，整个数组基本有序，从而达到预排序的效果（以便提高最终直接插入排序的效率）.
“缩小增量”即在整个数组的预排序过程中，逐渐减少分组数量，增大每组的数据量，直到分组数量n=1时，针对之前的预排序结果，进行一次直接插入排序。
关于分组？
对于前面的分组，并不是如下图的“逐段分割”式分组方式。(×)
但事实上，通过上述例子我们可以看出，经过几次“预排序”，似乎并没有达到预期的基本有序的效果，因为 1 和 2 这样较小的数字依然在后面， 12 这个比较大的数子也仍然处于中间的位置，没有加快直接插入排序的速度。
这样的“逐段式”分组方式显然是不够合理的，因此这里正确的分组的方式是：将每间隔距离为“增量”大小 gap 的元素分为一组（如下图）。(√)
这样"跳跃式"的分组的好处是:若较大的元素在前面,通过"跳跃式"分组后,较大的元素有机会通过插入排序直接移动到后面;若较小的元素在后面,通过"跳跃式"分组后,较小的元素有机会通过插入排序直接移动到前面.
关于分组后插入排序的方式？
分组后，并不是依次对每组元素进行插入排序，而是从第一组的第 2 个元素 即下标为 gap 的元素开始，之后的每个元素进行间距为“增量”大小的插入排序。（如下图， gap = 3）
关于 gap 的取值?
gap 的取值有很多种方式,不同取值方式所得到排序时间复杂度有所不同,目前并没有一种确定的最佳增量序列,但唯一确定的是最后一个增量应为 1 。在本文的代码实现中，当待排序排序的元素个数为 n， gap 的初始值为 n/2，随后每次 gap = gap/2， 直到 gap 为1，完成排序。
希尔排序的具体代码实现如下：
public static void shellSort(int[] array){ // 当前数组只有一个元素，不需要进行排序 if(array.length < 2) return; // 保证第一次的 gap = n/2,最后一次排序 gap = 1 int gap = array.length; while(gap > 1) { gap = gap / 2; shell(array, gap); } } private static void shell(int[] array, int gap) { for(int i = gap; i < array.length; i++) { int tmp = array[i]; // 若array[j] > tmp，则该元素向前移动 // j 继续向前移动 gap 个位置，重复上述过程，直到 array[j] <= tmp 或 j < 0 int j = i - gap; for(; j >= 0; j -= gap) { if(array[j] > tmp) { array[j+gap] = array[j]; }else { break; } } array[j+gap] = tmp; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
时间复杂度：O(n ^ 1.25) - O(1.6 * n ^ 1.25)。
空间复杂度：O(1)。
稳定性：不稳定。
适用情况：适合初始记录无序，元素个数 n 较大时的情况。
选择排序
简单选择排序
- 算法基本原理：（从大到小排序）
（若要求从小到大排序）每次从待排序数组的区间中顺序遍历，记录最大元素的下标，然后与待排序数组区间的最后一个元素交换。
具体代码如下：
public static void selectSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
// 需要找 n - 1 次， 每次从第一个元素开始向后遍历
int maxIndex = 0;
for (int j = 1; j < array.length - i; j++) {
if(array[j] > array[maxIndex]) maxIndex = j;
}
swap(array, array.length - 1 - i, maxIndex);
}
}
private static void swap(int[] array, int x, int y) {
int tmp = array[x];
array[x] = array[y];
array[y] = tmp;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
时间复杂度：O(n²)。在任何情况下，第 i 趟寻找最大的元素时，都需要比较 n - i 次，因此n - 1趟排序的时间复杂度为O(n²)。
空间复杂度：O(1)。需要一个额外空间进行元素交换。
稳定性：不稳定（可通过代码改善变得稳定）。
适用情况：无论数组的有序性如何，简单选择排序的时间复杂度都为O(n²)，只适合数据量小的排序，一般不推荐使用。
堆排序
堆的说明：将数组按下标从小到大抽象成为一颗二叉树，再通过一定的调整手段，使该二叉树具有以下特点：每颗树根结点的值 > 其左右子树根结点的值（大根堆） 或者 每颗树根结点的值 < 其左右子树根结点的值（小根堆） 。（如下图所示）
- 算法基本思想：（从大到小排序）
- 把待排序数组调整成一个大根堆，每次将堆顶元素（即根结点）与待排序堆的最后一个元素交换
- 接着将剩下待排序数组重新调整成堆（重新上述步骤，最终完成排序）。（如下图）
那么如何将数组调整成大根堆呢？（以最开始的原数组为例） - 从二叉树的最后一个非终端结点（即度不为0的结点）开始，将它前面的每个结点都进行向上调整。（这里是下标0-2的结点）
- 对每个结点（这里暂且将该结点称作root结点）进行调整时，需把 root结点 值的大小与其左右孩子进行比较，若 root结点 的值较小，则将较大的孩子结点与 root结点 的值交换。（注意：若交换的孩子结点也有孩子，仍需继续将该孩子进行比较和调整，当且仅当 root结点 所在的整颗树都调整成为大根堆，该结点才算调整完成）。
建立大根堆的具体代码如下：
// array为原始数组 private static void createBigHeap(int[] array) { // 最后一个非终端结点下标为(array.length-2) / 2 // 对下标为(array.length-2) / 2 到 下标为0的结点依次进行“向上调整 ” for(int parent = (array.length-2) / 2; parent >= 0; parent-- ) { shiftDown(array,parent, array.length); } } // root表示当前调整的数的根结点下标，len表示待调整的整个数组的长度 private static void shiftDown(int[] array, int root, int len) { int parent = root; int child = root * 2 + 1; // 防止出现需要多次调整的情况 while(child < len) { // child + 1 判断该结点是否有右孩子，有则通过比较选出左右孩子的较大值 if(child + 1 < len && array[child] < array[child+1]) { child = child + 1; } // 判断是否需要交换 if(array[child] > array[parent]) { swap(array,child,parent); parent = child; child = parent * 2 + 1; }else { break; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
经过上述调整的大根堆，就可以正式开始堆排序：
- 把待排序数组调整成一个大根堆，每次将堆顶元素（即根结点）与待排序堆的最后一个元素交换。
- 接着将剩下待排序数组重新调整成堆。（重新1，2步骤）
堆排序具体代码如下：
public static void heapSort2(int[] array) {
// 建立大根堆
createBigHeap(array);
int end = array.length - 1;
while(end > 0) {
// 交换堆顶元素 与 待排序区间的末尾元素
swap(array, 0, end);
// 重新调整将剩下区间调整成大根堆
shiftDown(array, 0, end);
end--;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
时间复杂度：O(nlog₂ n)。最坏情况下的时间时间复杂度为也稳定在O(n * log₂ n)。
空间复杂度：O(1)。需要一个额外空间进行元素交换。
稳定性：不稳定。
适用情况：堆排序是一种较快的排序算法，它与快速排序，归并排序的平均时间都为O(nlog₂ n)，适用于数据量较大时的排序。
交换排序
冒泡排序
-
算法基本思想：（从大到小排序）
通过两两比较相邻记录的关键字，如果后一个元素的值大于前一个元素，则将两个元素进行交换，从而使关键字大的元素如煮开水时的“气泡”一样逐渐向上“漂浮”（右移）。 -
算法步骤：
（1）具有 n 个元素的数组，进行 n-1 趟冒泡排序。
（2）每趟冒泡排序从第一个元素开始向后遍历，相邻两两元素比较，将关键字大的元素交换到后面，直到当前排序区间最大元素到区间末尾，这趟冒泡排序结束。
第一趟的交换过程如下图：（某待排序数组）
当第二趟排序完成后，数组的元素分布情况如下：
不难发现，在第二趟排序结束后，数组已经属于有序状态，很明显进行接下来的几趟排序是“多此一举”的。
因此我们可以对普通的冒泡排序做一个小小的优化：即设置一个标志位 flag = 1，当次轮排序过程发生了元素交换，则将 flag 置为 0，当本趟排序完成后，若 flag == 1，则代表数组已经有序，直接跳出整个循环，完成排序操作。
冒泡排序代码实现如下：
public static void bubbleSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
// 判断是否继续冒泡排序
int flag = 1;
for (int j = 0; j < array.length - 1 - i; j++) {
if(array[j] > array[j+1]) {
swap(array,j,j+1);
flag = 0;
}
}
if(flag == 1) break;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
时间复杂度：O(n²)。即使设置标志位对冒泡排序进行优化，但排序的平均时间复杂度仍为O(n²)。
空间复杂度：O(1)。需要一个额外空间进行元素交换。
稳定性：稳定。
适用情况：适合数据量较小的数据排序，当数据规模较大时，排序效率较低。
快速排序
-
算法基本思想：
快速排序由冒泡排序改进而成。快速排序采用“分治”的思想，即把一个大问题分解成为多个子问题，通过解决每个子问题，从而解决整个大问题。
在每个子问题中，需要选一个元素值 pivot 作为“基准”，通过一定次数的两两元素交换，最终将某个区间区间分为两个区间，左区间的元素全部不大于 pivot，右区间的元素全部不小于 pivot。 -
快速排序区间划分的两个常见方式：
（1） Hoare法（2）“挖坑”法
Hoare法
- 在待排序区间中，选取第一个元素作为基准值 pivotkey ，定义 left 和 right 两个“指针”，其中left 指向待排序区间的第一个元素，right 指向待排序区间的最后一个元素。right 指针向左遍历寻找第一个小于 pivot 的元素，left 指针向右遍历寻找第一个大于 pivot 的元素， 随后交换 left 和 right 所指向的元素。
- 重复上述步骤，直至 left 指针和 right 指针相遇。将 基准元素pivot 与 right（left）指针交换，完成分区操作。
- 将 pivot 左区间和右区间分为两个新的待排序区间，重复1，2步骤，最终完成排序。
具体的排序过程如下图所示：
下面的分区过程省略。
通过以上过程我们不难看出：快速排序是一个采用递归思想的排序过程。
注意：当你也尝试着去模拟上述的过程，你也许会发现：好像将left（right）“指针”指向的元素 与 第一个元素交换后，并不会出现分区的现象。
那么造成这种现象的原因是否与 left“指针” 和 right“指针” 移动的先后顺序有关呢？
答案是肯定的，这种情况是因为在某些数据先移动 left“指针”造成的。因此，在每次寻找符合交换条件的元素时，应先让 right“指针”向左寻找待交换的元素。
注意： left“指针”要寻找比 pivotkey 大的元素，right“指针”要寻找比 pivotkey 小的元素，那循环找元素的条件能否直接写成 array[left] < pivotkey 和 array[right] > pivotkey呢？
答案是否定的。原因是数组可能出现 元素值key == pivotkey 的情况，如果写成上述判断条件，可能会出现排序出差的情况。
Hoare法具体的代码实现如下：
public static void quiackSort(int[] array) { quick(array, 0, array.length - 1); } private static void quick(int[] array, int left, int right) { //代表此时 此时排序区间 只有一个元素 或者 排序区间不存在 if(left >= right) return; // 在 partition方法中，完成分区操作，并返回 pivot的下标 int pivot = partition(array, left, right); // 对 pivot 的左右区间进行递归操作 quick(array,pivot + 1, right); quick(array,left, pivot - 1); } private static int partition(int[] array, int left, int right) { int tmp = array[left]; int i = left; // 记录基准值的下标 while(left < right) { //必须先让 right 去寻找比tmp小的元素， 因为这样可以防止 一个大的元素 被错误地放到 数组的前面 while(left < right && array[right] >= tmp) right--; while(left < right && array[left] <= tmp) left++; //此时 left 和 right 分别指向 大于和小于 tmp的元素 swap(array,left,right); } swap(array, i, right); return right; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
“挖坑”法
- 在待排序区间中，选取第一个元素作为基准值 pivotkey ，用一个临时变量 tmp 存储 pivotkey，同时定义 left 和 right 两个“指针”，其中 left 指向待排序区间的第一个元素，right 指向待排序区间的最后一个元素。
因基准元素 pivot 的值已经用 tmp 存储起来，故挖坑法顾名思义，已经空出来的 pivot 位置就相当于一个“坑”，当 right “指针” 找到比 pivotkey 小的元素时，right 位置的元素可以直接“入坑”，与此同时right 位置就成为了一个新的“坑”；此时 left “指针”开始寻找比 pivotkey 大的元素，同样 left 指向的元素“入到新坑”。 - 重复上述步骤，直到 left 和 right “指针”相遇，将 tmp 的值放入 两“指针” 的相遇位置，此时分区操作完成。
- 将 pivot 左区间和右区间分为两个新的待排序区间，重复1，2步骤，最终完成排序。
具体的排序过程如下图所示：（数组的初始序列为：8，10，0，20，5，1，6，9）
“挖坑”法具体的代码实现如下：
public static void quickSort2(int[] array) { quick2(array, 0, array.length - 1); } private static void quick2(int[] tmpArray, int left, int right) { if(left >= right) return; //代表此时 此时排序区间 只有一个元素 或者 排序区间不存在 // 在 partition方法中，完成分区操作，并返回 pivot的下标 int pivot = partition2(tmpArray, left, right); // 对 pivot 的左右区间进行递归操作 quick2(tmpArray, left, pivot - 1); quick2(tmpArray, pivot + 1, right); } private static int partition2(int[] tmpArray, int left, int right) { int tmp = tmpArray[left]; while(left < right) { //必须先让 right 去寻找比tmp小的元素， 因为这样可以防止 一个大的元素 被错误地放到 数组的前面 while(left < right && tmpArray[right] >= tmp) right--; // right “指针” 入左坑 swap(tmpArray, left, right); while(left < right && tmpArray[left] <= tmp) left++; // left “指针” 入右坑 swap(tmpArray, left, right); } tmpArray[left] = tmp; return left; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
时间复杂度：O(n log n)。在数组原来有序的情况下（非递减或非递增），快速排序的递归过程会变成单分支树的递归，退化成冒泡排序，即最坏情况下时间复杂度为O(n²)；但平均时间复杂度仍为O(n log n)。
空间复杂度：O(1)。需要一个额外空间进行元素交换或值存储。
稳定性：不稳定。
适用情况：虽然快速排序存在退化成冒泡排序的可能性，但绝大多数情况下，数据均为乱序状态，因此快速排序可以称为“内部排序”中最快的排序方法。
归并排序
- 基本算法思想：
将两个或两个以上的有序表合并成一个有序表的过程称为归并排序。将含有 n 个元素的待排序数组，看成是 n 个有序的子序列，每个子序列的长度为1，接着将这 n 个子序列进行两两归并，得到 n/2(n/2+1) 个长度为 2或1 的有序子序列；再将这 n/2 个有序子序列 进行两两归并，得到 n/4 个有序子序列……重复上述步骤，最终得到一个长度为 n 的有序的序列，此时数组排序完成。
具体的排序过程如下图所示：（数组的初始序列为：8，10，20，0，5，1，6）
从上图不难看出，只要知道每次两两归并时，每个子数组的起始下标 start 和终点坐标 end ，我们即可根据学过的合并两个有序列表的方法，最终将整个数组排列成有序序列。
那么如何将含 n 个元素的数组分成 n 个子序列，再进行合并呢？
答案是：”采用“分而治之”的思想。先得到待排序数组中间元素的下标 mid ，将数组第一个元素的下标 start 到 mid 这个区间分为一个区间，将 mid+1 到 数组最后一个元素的下标 end 这个区间分为另一个区间。递归重复上述步骤，直到 start >= end，停止递归操作，开始合并的过程。每次合并的左区间都为 start - mid，右区间为 mid+1 - end。
归并排序具体的代码实现如下：
public static void mergeSort(int[] array) { merge(array, 0 , array.length - 1); } private static void merge(int[] array, int left, int right) { if(left >= right) return; //分解小区间 int mid = (left + right) / 2; merge(array, left, mid); merge(array, mid + 1, right); //合并小区间的有序数组 int start1 = left; int start2 = mid + 1; int[] mergeArray = new int[right - left + 1]; int k = 0; while(start1 <= mid && start2 <= right) { if(array[start1] <= array[start2]) { mergeArray[k++] = array[start1++]; }else { mergeArray[k++] = array[start2++]; } } while(start1 <= mid) { mergeArray[k++] = array[start1++]; } while(start2 <= right) { mergeArray[k++] = array[start2++]; } //将mergeArray数组中的元素 放回到 原来数组的合并区间内 k = 0; while (left <= right) { array[left++] = mergeArray[k++]; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
时间复杂度：O(n log n)。
空间复杂度：O（n）。
基数排序
- 算法基本原理：
基数排序是一种非比较的排序方法，它通过若干次“分配”与“收集”对整个序列进行排序。基数排序利用了“桶”的思想，需要将待排序元素“分解”成若干个关键字，并准备若干个桶，使得桶的范围能够覆盖每次关键字出现的所有可能情况，根据每个元素关键字的值依次放入对应的桶，并将元素按桶的顺序和元素放入的顺序依次取出，进行下次“分配”，直至所有关键字完成“分配”和“收集”。
例如：要对整数类型的数组进行排序，数组中的元素分别为：12，44，8，26，40，99，3，76，60，25。我们可以将每个元素的十位和个位“分解”成2个关键字，因为每个关键字的范围是0~9，因此我们每次需要先准备10个桶，每个桶依次存放关键字为 0 ~ 9 的元素。
接着采用“最低位优先法”，即先匹配个位这个关键字，将元素依次放入对应的桶，按桶的顺序和元素放入的顺序依次取出后，接着“分配”并“收集”十位这个关键字，最终完成排序。（如下图）
计数排序的具体代码实现如下：
public static void radixSort(int[] array) { // 1. 先获得所有元素中的最大位数 int count = 1; // 记录最大位数 int multiple = 10; // 记录当前倍数 for (int x : array) { while (x / multiple > 0) { multiple *= 10; count++; } } // 2. 采用“最低位优先法”进行 count 次“分配”与“收集” multiple = 1; // 描述当前关键字的取值方式 for (int i = 0; i < count; i++) { // 准备 0~9，总共10个桶存放元素 int[][] buckets = new int[10][0]; for (int j = 0; j < 10; j++) { buckets[j] = new int[0]; } // 针对关键字进行“分配” for (int x : array) { int key = x / multiple % 10; int len = buckets[key].length; buckets[key] = Arrays.copyOf(buckets[key], len + 1); buckets[key][len] = x; } // 对元素按顺序收集 int k = 0; for (int j = 0; j < 10; j++) { // 遍历每个桶 for (int x : buckets[j]) { array[k++] = x; } } multiple *= 10; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
时间复杂度：O(d (n+t))。对于 n 个元素的序列（假设每个元素含有 d 个关键字，每个关键字的取值范围有 t 个值），每一趟“分配”的时间复杂度为O(n)，每一趟“收集”的时间复杂度为O(t)，要进行 d 趟“分配”与“收集”,因此总的时间复杂度为O(d (n+t))。
空间复杂度：O(n+d)。
稳定性：稳定。
适用情况：有较为苛刻的要求，需要知道各个关键字的主次关系和每个关键字的所有可能取值范围。
计数排序
- 算法基本思想：
- 遍历待排序数组，记录数组中的最大值 max 和最小值 min。
- 申请一个空间大小为 max-min+1 的计数数组，计数数组的下标通过一定的转换可以代表待排序数组的每个元素大小，键值记录数字中每个元素出现的次数。对待排序数组进行遍历，统计每个元素出现的次数。
- 对计数数组进行顺序遍历，假如数组中某元素的值 n 大于0，通过元素的下标，将 n 个转换后的元素值放入到待排序数组中。待计数数组遍历完毕，最终完成排序操作。
注意：计数数组下标 = array[i] - array[min]
待排序数组与计数数组的关系如下:
具体代码实现如下：
public static void countSort(int[] array) { int minVal = array[0]; int maxVal = array[0]; // 找到数组元素的最大值和最小值 for (int i = 1; i < array.length; i++) { if(array[i] < minVal) minVal = array[i]; if(array[i] > maxVal) maxVal = array[i]; } int[] countArray = new int[maxVal - minVal + 1]; // 记录每个元素出现的次数 count(array, countArray , minVal); //把排序好的数据写回到 tmpArray 数组中 int k = 0; for (int i = 0; i < countArray.length; i++) { while(countArray[i] > 0) { array[k++] = i + minVal; countArray[i]--; } } } private static void count(int[] array, int[] countArray, int minVal) { for (int i = 0; i < array.length; i++) { countArray[array[i] - minVal]++; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
时间复杂度：O(n + k)，计数的时间复杂度不仅数组元素的个数 n 有关，也取决于数组中最大和最小元素的区间 k。
空间复杂度：O(K)。（针对当前代码实现方式）
稳定性：不稳定。（针对当前代码实现方式）
适用情况：当待排序数组数据量较大且数据分布较集中时，计数排序的适用程度较高。当数据分别较分散，差值很大时应使用其他排序算法。
以上就是本篇文章的全部内容了，如果这篇文章对你有些许帮助，你的点赞、收藏和评论就是对我最大的支持。
另外，文章可能存在许多不足之处，也希望你可以给我一点小小的建议，我会努力检查并改进。
