計數排序
計數排序是一個非基于比較的排序算法,該算法于1954年由 Harold H. Seward 提出。它的優勢在于在對一定範圍内的整數排序時,它的複雜度為Ο(n+k)(其中k是整數的範圍),快于任何比較排序算法。
算法思想
計數排序對輸入的資料有附加的限制條件: 1、輸入的線性表的元素屬于有限偏序集S; 2、設輸入的線性表的長度為n,|S|=k(表示集合S中元素的總數目為k),則k=O(n)。 在這兩個條件下,計數排序的複雜性為O(n)。 計數排序的基本思想是對于給定的輸入序列中的每一個元素x,确定該序列中值小于x的元素的個數。一旦有了這個資訊,就可以将x直接存放到最終的輸出序列的正确位置上。例如,如果輸入序列中隻有17個元素的值小于x的值,則x可以直接存放在輸出序列的第18個位置上。當然,如果有多個元素具有相同的值時,我們不能将這些元素放在輸出序列的同一個位置上,是以,上述方案還要作适當的修改。 假設輸入的線性表L的長度為n,L=L1,L2,..,Ln;線性表的元素屬于有限偏序集S,|S|=k且k=O(n),S={S1,S2,..Sk};則計數排序可以描述如下: 1、掃描整個集合S,對每一個Si∈S,找到線上性表L中小于等于Si的元素的個數T(Si); 2、掃描整個線性表L,對L中的每一個元素Li,将Li放在輸出線性表的第T(Li)個位置上,并将T(Li)減1。 Java版語言描述:
1 package sort;
2
3
4 public class Main {
5
6 public static void main(String[] args) {
7 // 排序的數組
8 int a[] = { 99, 93, 97, 92, 96 };
9 int b[] = countSort(a);
10 for (int i : b) {
11 System.out.print(i + " ");
12 }
13 System.out.println();
14 }
15
16 public static int[] countSort(int[] a) {
17 int b[] = new int[a.length];
18 int max = a[0];//數組a中的最大值
19 int min = a[0];//數組a中的最小值
20 for (int i : a) {
21 if (i > max) {
22 max = i;
23 }
24 if (i < min) {
25 min = i;
26 }
27 }
28
29 int k = max - min + 1; // 這裡k的大小是要排序的數組中,元素大小的極值差+1
30 int c[] = new int[k]; //此時c[]中的每個元素全是零
31 for (int i = 0; i < a.length; ++i) {
32 c[a[i] - min] += 1; // 數組c下标對應“數組a元素值與數組a最小值的差”,改下标的數組c元素值置1
33 // 優化過的地方,減小了數組c的大小
34 }
35 for (int i = 1; i < c.length; ++i) {
36 c[i] = c[i] + c[i - 1]; //小技巧:數組c的值置成順序值
37 }
38 for (int i = a.length - 1; i >= 0; --i) {
39 int temp = c[a[i] - min] - 1;
40 b[temp] = a[i];// 按存取的方式取出c的元素
41 }
42 return b;
43 }
44
45 }