首页 / 算法 / 常见排序算法汇总（下）
常见排序算法汇总（下）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了常见排序算法汇总（下），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6454字，纯文字阅读大概需要10分钟。
内容图文
开篇问题：如何根据年龄给100万用户数据排序
以下几种排序就比较适用这种数据量比较大的场景。
桶排序
核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
如果每个桶的数据分布不均匀，可以在数据比较多的桶里继续划分数据。
桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。
容器版
public static void bucketSort2(int[] arr){
int max = arr[0];
int 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;
List<List<Integer>> bucketArr = new ArrayList<>(bucketNum);
for (int i = 0; i < bucketNum; i++) {
bucketArr.add(new ArrayList<>());
}
//将每个元素放入桶内
for (int i = 0; i < arr.length; i++) {
int index = (arr[i] - min) / arr.length;
bucketArr.get(index).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);
index++;
}
}
}二维数组版（支持自动扩容）
public static void bucketSort(int[] arr,int bucketSize){
if (arr.length < 2){
return;
}
int minValue = arr[0];
int maxValue = arr[0];
for (int i = 0; i < arr.length; i++) {
if (arr[i] > maxValue){
maxValue = arr[i];
}
if (arr[i] < minValue){
minValue = arr[i];
}
}
//桶数量
int bucketCount = (maxValue - minValue) / bucketSize + 1;
int[][] buckets = new int[bucketCount][bucketSize];
int[] indexArr = new int[bucketCount];
//将数值分配到各个桶中
for (int i = 0; i < arr.length; i++) {
int bucketIndex = (arr[i] - minValue) / bucketSize;
if (indexArr[bucketIndex] == buckets[bucketIndex].length){
//扩容
ensureCapacity(buckets,bucketIndex);
}
buckets[bucketIndex][indexArr[bucketIndex]++] = arr[i];
}
//对每个桶进行排序，使用快速排序
int k = 0;
for (int i = 0; i < buckets.length; i++) {
if (indexArr[i] == 0){
continue;
}
//快速排序
quickSort(buckets[i],0,indexArr[i] - 1);
//赋值到原数组
for (int j = 0; j < indexArr[i]; j++) {
arr[k++] = buckets[i][j];
}
}
}
/**
* 数组扩容
* @param buckets 数组
* @param bucketIndex 下标
*/
private static void ensureCapacity(int[][] buckets,int bucketIndex){
int[] tempArr = buckets[bucketIndex];
int[] newArr = new int[tempArr.length * 2];
for (int i = 0; i < tempArr.length; i++) {
newArr[i] = tempArr[i];
}
buckets[bucketIndex] = newArr;
}
/**
* 快速排序
* @param arr 数组
* @param p 分区点左边
* @param r 分区点右边
*/
private static void quickSort(int[] arr,int p,int r){
if (p >= r){
return;
}
//分区点
int q = partition(arr,p,r);
//往左边继续分区
quickSort(arr,p,q - 1);
//往右遍继续分区
quickSort(arr,q + 1,r);
}
private static int partition(int[] arr, int p,int r){
//分区点
int pivot = arr[r];
int i = p;
for (int j = p; j < r; j++) {
//小于分区点的放左边
if (arr[j] <= pivot){
swap(arr,i,j);
i++;
}
}
swap(arr,i,r);
return i;
}
private static void swap(int[] arr,int i,int j){
if (i == j){
return;
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
计数排序
我们都经历过高考，高考查分数系统你还记得吗？我们查分数的时候，系统会显示我们的成绩以及所在省的排名。如果你所在的省有50万考生，如何通过成绩快速排序得出名次呢？
考生的满分是900分，最小是0分，这个数据的范围很小，所以我们可以分成901个桶，对应分数从0分到900分。根据考生的成绩，我们将这50万考生划分到这901个桶里。桶内的数据都是分数相同的考生，所以并不需要再进行排序。我们只需要依次扫描每个桶，将桶内的考生依次输出到一个数组中，就实现了50万考生的排序。因为只涉及扫描遍历操作，所以时间复杂度是O(n)。
当要排序的n个数据，所处的范围并不大的时候，比如最大值是k，我们就可以把数据划分成k个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。
我们对C[6]数组顺序求和，C[6]存储的数据就变成了下面这样子。C[k]里存储小于等于分数k的考生个数。通过这样，就能直接知道每个数的排名了。
最后将这些数据依次放入数组R中，即排序成功。
从后到前依次扫描数组A。比如，当扫描到3时，我们可以从数组C中取出下标为3的值7，也就是说，到目前为止，包括自己在内，分数小于等于3的考生有7个，也就是说3是数组R中的第7个元素（也就是数组R中下标为6的位置）。
当3放入到数组R中后，小于等于3的元素就只剩下了6个了，所以相应的C[3]要减1，变成6。
代码实现：
public static void countingSort(int[] arr){
int min = arr[0];
int max = arr[0];
for (int i = 0; i < arr.length; i++) {
max = Math.max(max,arr[i]);
min = Math.min(min,arr[i]);
}
int[] bucket = new int[max - min + 1];
for (int i = 0; i < arr.length; i++) {
//减去min是为了防止array[i]小于0，
// 数组索引不能小于0，相当于做了个偏移。++是为了记录次数
bucket[arr[i] - min]++;
}
int index = 0;
for (int i = 0; i < bucket.length; i++) {
while (bucket[i]-- > 0){
arr[index++] = i + min;
}
}
}基数排序
假设我们有10万个手机号码，希望将这10万个手机号码从小到大排序，你有什么比较快速的排序方法呢？
桶排序、计数排序能派上用场吗？手机号码有11位，范围太大，显然不适合用这两种排序算法。
这种情况下就要用到基数排序：
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。
手机号码稍微有点长，画图比较不容易看清楚，可以用字符串排序来模拟一下
可以借助相同的处理思路，先按照最后一位来排序手机号码，然后，再按照倒数第二位重新排序，以此类推，最后按照第一位重新排序。经过11次排序之后，手机号码就都有序了。
根据每一位来排序，用桶排序或者计数排序，时间复杂度可以做到O(n)。如果要排序的数据有k位，那我们就需要k次桶排序或者计数排序，总的时间复杂度是O(k*n)。当k不大的时候，比如手机号码排序的例子，k最大就是11，所以基数排序的时间复杂度就近似于O(n)。
代码实现：
public static void randixSort(int[] arr){
int max = arr[0];
//找到最大值
for (int i = 0; i < arr.length; i++) {
if (arr[i] > max){
max = arr[i];
}
}
// 从个位开始，对数组arr按“指数”进行排序
for (int exp = 1;max / exp > 0;exp *= 10){
countingSort(arr,exp);
}
}
private static void countingSort(int[] arr,int exp){
if (arr.length <= 1){
return;
}
//计算每个元素的个数
int[] c = new int[10];
for (int i = 0; i < arr.length; i++) {
c[(arr[i] / exp) % 10]++;
}
//计算排序后的位置
for (int i = 1; i < c.length; i++) {
c[i] += c[i - 1];
}
//临时数组temp，存储排序之后的结果
int[] temp = new int[arr.length];
for (int i = arr.length - 1; i >= 0; i--) {
temp[c[(arr[i] / exp) % 10] - 1] = arr[i];
c[(arr[i] / exp) % 10]--;
}
//将临时数组的值赋值到原数组中
for (int i = 0; i < arr.length; i++) {
arr[i] = temp[i];
}
}问题解答
最后我们来看下一开始的问题，如何根据年龄给100万用户排序？
我们假设人大年龄为150，最小1岁，我们可以遍历这100万个用户将其年龄放入150个有序桶中，然后按顺序取出即可。
喜欢本文的话，可以关注一下公众号，每天定时更新一篇学习日记，让我们一起成长！
内容总结
以上是互联网集市为您收集整理的常见排序算法汇总（下）全部内容，希望文章能够帮你解决常见排序算法汇总（下）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。