排序算法（三）

Myth丶恋晨 2023-07-12 14:57 24阅读 0赞

# 1.计数排序 #

## 核心思想： ##

对于输入的数据x存入标记为x的数组中，并统计x的个数。  
适用于数据范围小，数据量大的情况。  
算法的步骤如下：  
1.找出待排序的数组中最大和最小的元素  
2.统计数组中每个值为i的元素出现的次数，存入数组C的第i项  
3.对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）  
4.反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个 元素就将C(i)减去1

public class Counting { 
     public static int[] sort(int[] arr) { 
     if(arr == null || arr.length < 2) return arr;
     int n = arr.length;
     int min = arr[0];
     int max = arr[0];
     // 寻找数组的最⼤值与最⼩值
     for (int i = 1; i < n; i++) { 
     if(max < arr[i])
     max = arr[i];
     if(min > arr[i])
     min = arr[i];
     }
     int d = max - min + 1;
     //创建⼤⼩为max的临时数组
     int[] temp = new int[d];
     //统计元素i出现的次数
     for (int i = 0; i < n; i++) { 
     temp[arr[i] - min]++;
     }
     int k = 0;
     //把临时数组统计好的数据汇总到原数组
     for (int i = 0; i < d; i++) { 
     for (int j = temp[i]; j > 0; j--) { 
     arr[k++] = i + min;
     }
     }
     return arr;
     }
    }

[文章][Link 1]

# 2.基数排序 #

## 核心思想： ##

分配+收集  
基数排序又称为“桶子法”，从低位开始将待排序的数按照这一位的值放到相应的编号为0~9的桶中。等到低位排完得到一个子序列，再将这个序列按照次低位的大小进入相应的桶中，一直排到最高位为止，数组排序完成。  
算法执行步骤：  
(1)遍历序列找出最大的数(为的是确定最大的数是几位数)；  
(2)开辟一个与数组大小相同的临时数组tmp；  
(3)用一个count数组统计原数组中某一位(从低位向高位统计)相同的数据出现的次数；  
(4)用一个start数组计算原数组中某一位(从最低位向最高位计算)相同数据出现的位置；  
(5)将桶中数据从小到大用tmp数组收集起来；  
(6)重复(3)(4)(5)直到所有位都被统计并计算过，用tmp收集起来；  
(7)将tmp数组拷回到原数组中；  
[文章][Link 2]

# 3.桶排序 #

## 核心思想： ##

将数据划分多个范围相同的区间，每个区间排序，最后合并。  
[文章][Link 3]

[Link 1]: https://blog.csdn.net/gaoruxue918/article/details/61467416?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task
[Link 2]: https://blog.csdn.net/double_happiness/article/details/72452243?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task
[Link 3]: https://blog.csdn.net/qq_37186247/article/details/100834916