前言：
作者：神的孩子在歌唱
大家好，我叫運智
計數排序（Counting Sort）
計數排序于1954年由Harold H. Seward提出，適合對一定范圍內的整數進行排序
-
冒泡、選擇、插入、歸并、快速、希爾、堆排序，都是基于比較的排序，平均時間復雜度目前最低是
O(nlogn) -
計數排序、桶排序、基數排序，都不是基于比較的排序，它們是典型的用空間換時間，在某些時候，平均時間復雜度可以比
O nlogn更低 -
計數排序的核心思想：統計每個整數在序列中出現的次數，進而推匯出每個整數在有序序列中的索引
計數排序 – 最簡單的實作
- 統計陣列資料次數
- 最后輸出到原來陣列中覆寫就可以了
- 代碼實作：找到最大值，開辟空間，統計次數，根據次數進行排序
package com.chengyunzhi;
public class 計數排序 {
static int[] array= {7,3,5,8,6,7,4,5};
public static void main(String args[]) {
sort();
}
public static void sort() {
// 找出最大值
int max=0;
for(int arr:array) {
max=Math.max(max, arr);
}//O(n)
// 開辟記憶體空間,存每個整數出現的次數
int[] counts=new int[max+1];
// 統計出現次數
for(int arr:array) {
counts[arr]++;
}//O(n)
// 根據次數進行排序
int index=0;
for(int i=0;i<counts.length;i++) {
while(counts[i]-->0) {
array[index++]=i;
}
}//O(n)
for(int i=0;i<array.length;i++) {
System.out.print(array[i]+"_");
}
}
}
輸出: 3_4_5_5_6_7_7_8_
時間復雜度O(n)這個版本的實作存在以下問題，無法對負整數進行排序，極其浪費記憶體空間，是個不穩定的排序
計數排序 – 改進思路
- 在{7,3,5,8,6,7,4,5}找到最大最小值,依次存入次數,就可以節省空間，并且可以對負整數進行排序
-
每個次數累加上其前面的所有次數得到的就是元素在有序序列中的位置資訊，比如元素8的次數是8=7+1，說明他前面還有七個，八的索引就是7.
通過上面的方法知道下標就可以依次排序了
-
每個元素累加上其前面的所有元素得到的就是元素在有序序列中的位置資訊
- 每個元素累加上其前面的所有元素得到的就是元素在有序序列中的位置資訊
本人csdn博客：https://blog.csdn.net/weixin_46654114
轉載說明：跟我說明，務必注明來源，附帶本人博客連接，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/302779.html
標籤：其他