vlambda博客
学习文章列表

ComparisonCountingSort (A[0..n-1])
//用比较计数法对数组排序
//输入：可排序数组A[0..n-1]
//输出：将A中元素按照升序排列的数组S[0..n-1]
for i←0 to n-1 do Count[i]←0
for i←0 to n-2 do
 for j←i+1 to n-1 do
 if A[i]>A[j]
 Count[i]←Count[i]+1
 else Count[j]←Count[j]+1
for i←0 to n-1 do S[Count[i]]←A[i]
return S

/** * Project: Algorithm * Date: 2020/02/02 * Time: 20:20 * author: Eric * Description: TODO 计数排序 */public class CountingSort { /** * 用比较计数算法对数组排序 * * @param array 待排序数组 * @return 升序排列的结果数组 */ public static int[] comparisonCountingSort(int[] array) { int n = array.length; int[] count = new int[n]; //count初始化为0，记录小于该元素的元素个数 int[] result = new int[n]; //存放排序结果的数组 for (int i = 0; i < n - 1; ++i) { for (int j = i + 1; j < n; ++j) { if (array[i] < array[j]) { count[j] += 1; } else { count[i] += 1; } } } for (int i = 0; i < n; ++i) { result[count[i]] = array[i]; } return result; }
 /** * 在控制台输出显示数组内容 *  * @param array 待显示的数组 */ private static void showArray(int[] array){ for(int element:array){ System.out.print(element+" "); } System.out.println(); }
 //主方法（测试） public static void main(String[] args) { int[] array = {34, 62, 28, 73, 51, 46}; int[] rs = comparisonCountingSort(array); System.out.println("原数组array："); showArray(array); System.out.println("利用比较计数排序后数组array："); showArray(rs); }}

DistributionCountingSort(A[0..n-1], low, high)
//用分布计数算法，对来自于有限范围整数的一个数组进行排序
//输入：数组A[0..n-1]，数组中的整数位于low和high之间（low≤high）
//输出：A中元素构成的非降序数组S[0..n-1]
for i←0 to high-low do D[i]←0 // 初始化频率数组
for i←0 to n-1 do D[A[i]-low]←D[A[i]-low]+1 // 计算频率值
for i←1 to high-low do D[i]←D[i-1]+D[i] // 计算分布值
for i←n-1 downto 0 do // 从右往左扫描数组
 j=A[i]-low
 S[D[j]-1]←A[i] // 排序数组的下标比分布值要小1
 D[j]←D[j]-1 // 相应的分布值减1
return S

/** * Project: Algorithm * Date: 2019/11/11 * Time: 20:32 * author: Eric * Description: TODO 计数排序 */public class CountingSort { /** * 用分布计数法，对来自有限范围整数的一个数组进行排序 * * @param array 可排序数组，数组整数值为有限范围 * @param lo 整数的下界 * @param hi 整数的上界 * @return 非降序数组 */ public static int[] distributionCountingSort(int[] array, int lo, int hi) { int n = array.length; int[] result = new int[n]; int[] distribution = new int[hi - lo + 1]; //初始化分布值数组为0 //计算频率值 for (int i = 0; i < n; ++i) { distribution[array[i] - lo] += 1; } //计算分布值 for (int i = 1; i < distribution.length; ++i) { distribution[i] += distribution[i - 1]; } //从后往前扫描array数组利用分布值排序 for (int i = n - 1; i >= 0; --i) { int index = array[i] - lo; //分布值数组中的下标 //把array中元素放到结果数组中的合适位置 result[distribution[index] - 1] = array[i]; distribution[index] -= 1;//相应的分布值减1 } return result; }
 /** * 在控制台输出显示数组内容 * * @param array 待显示的数组 */ private static void showArray(int[] array){ for(int element:array){ System.out.print(element+" "); } System.out.println(); }  //主方法（测试） public static void main(String[] args) { int[] array = {13, 11, 12, 13, 12, 12}; int[] rs = distributionCountingSort(array, 11, 13); System.out.println("原数组array："); showArray(array); System.out.println("利用比较计数排序后数组array："); showArray(rs); }}