數據結構與演算法之非比較排序【Java】

比較排序與非比較排序的對比

　　常見的快速排序、歸併排序、堆排序、冒泡排序等屬於比較排序。在排序的最終結果里，元素之間的次序依賴於它們之間的比較。每個數都必須和其他數進行比較，才能確定自己的位置。在冒泡排序之類的排序中，問題規模為n，又因為需要比較n次，所以平均時間複雜度為O(n²)。在歸併排序、快速排序之類的排序中，問題規模通過分治法消減為logN次，所以時間複雜度平均O(nlogn)。比較排序的優勢是，適用於各種規模的數據，也不在乎數據的分佈，都能進行排序。可以說，比較排序適用於一切需要排序的情況。

計數排序、基數排序、桶排序則屬於非比較排序。非比較排序是通過確定每個元素之前，應該有多少個元素來排序。針對數組arr，計算arr[i]之前有多少個元素，則唯一確定了arr[i]在排序後數組中的位置。

　　非比較排序只要確定每個元素之前的已有的元素個數即可，所有一次遍歷即可解決。演算法時間複雜度O(n)。非比較排序時間複雜度底，但由於非比較排序需要占用空間來確定唯一位置。所以對數據規模和數據分佈有一定的要求。

非比較排序

常見的比較排序主要有以下幾種：基數排序、計數排序、桶排序。

基數排序

1、基本思想：將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。然後，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後,數列就變成一個有序序列。

2、演算法實現

 1 package com.allSorts;
 2 
 3 import java.util.ArrayList;
 4 import java.util.List;
 5 
 6 /**
 7  * Created by Demrystv.
 8  */
 9 public class Ji1Shu {
10     public static void main(String[] args) {
11         int[] a = {23,45,67,88,90,21,42,52,73,61};
12         System.out.println("排序前：");
13         for(int i=0;i<a.length;i++){
14             System.out.print(a[i]+" ");
15         }
16 
17         //基數排序
18         sort(a);
19 
20         System.out.println("");
21         System.out.println("排序後：");
22         for(int i=0;i<a.length;i++){
23             System.out.print(a[i]+" ");
24         }
25     }
26 
27     private static void sort(int[] a){
28 
29         //找到最大值，看最大值有幾位，從而確定要比較幾次，個十百千萬。。。
30         int max = 0;
31         for(int i=0;i<a.length;i++){
32             if(max<a[i]){
33                 max = a[i];
34             }
35         }
36 
37         //找到最大值後，確定要比較幾次
38         int times = 0;
39         while (max>0){
40             max = max/10;
41             times++;
42         }
43 
44         //建立從0到9十個隊列
45         List<ArrayList> list1 = new ArrayList<>();
46         for(int i=0;i<10;i++){
47             ArrayList list2 = new ArrayList();
48             list1.add(list2);
49         }
50 
51         //進行times次分配和收集，不斷的重覆即可。
52         for(int i=0;i<times;i++){
53 
54             //分配,按照比較的所在的位的大小將其放入list1 中，類似於數組鏈表中的鏈表
55             for(int j=0;j<a.length;j++){
56                 int x = a[j] % (int)Math.pow(10,i+1) / (int)Math.pow(10,i);
57                 ArrayList list3 = list1.get(x);
58                 list3.add(a[j]);
59                 list1.set(x,list3);
60             }
61 
62             //收集，然後以此從數組的從左到右，鏈表的從上到下進行收集，將其重新放進一個新的數組中
63             int count = 0 ;
64             for(int j=0;j<10;j++){
65                 while (list1.get(j).size()>0){
66                     ArrayList<Integer> list4 = list1.get(j);
67                     a[count] = list4.get(0);
68                     list4.remove(0);
69                     count++;
70                 }
71             }
72         }
73 
74 
75     }
76 }

3、分析

　　基數排序是穩定的排序演算法。

　　基數排序的時間複雜度為O(k*n)，空間複雜度為O(m)，k為數組中數值的最大位數，m為桶的的個數。

計數排序

 1 package com.allSorts;
 2 
 3 /**
 4  * Created by Demrystv.
 5  */
 6 public class Ji4Shu {
 7     public static void main(String[] args) {
 8         int[] a = {23,42,53,64,63,32,13,52,97,94,26};
 9         System.out.println("排序前：");
10         for(int i=0;i<a.length;i++){
11             System.out.print(a[i]+" ");
12         }
13 
14         //計數排序
15         sort(a);
16 
17         System.out.println("");
18         System.out.println("排序後：");
19         for(int i=0;i<a.length;i++){
20             System.out.print(a[i]+" ");
21         }
22     }
23 
24     private static void sort(int[] a){
25 
26         if(a==null || a.length==0){
27             return;
28         }
29 
30         int max=0,min=0;
31         for(int i=0;i<a.length;i++){
32             max = Math.max(max,a[i]);
33             min = Math.min(min,a[i]);
34         }
35 
36         int[] help = new int[max-min+1];
37         int pos;
38 
39         for(int i=0;i<a.length;i++){
40             pos = a[i]-min;
41             help[pos]++;
42         }
43 
44         int index=0;
45         for(int i=0;i<help.length;i++){
46             while (help[i]>0){
47                 a[index] = i + min;
48                 index++;
49                 help[i]--;
50             }
51         }
52     }
53 }

3、分析

　　計數排序是穩定的排序演算法。

　　計數排序的時間複雜度為O(k+n)，空間複雜度為O(m)，k為數組中最大數與最小數差值，m為桶的的個數。

桶排序

 1 package com.allSorts;
 2 
 3 import java.util.ArrayList;
 4 import java.util.Collections;
 5 
 6 /**
 7  * Created by Demrystv.
 8  */
 9 public class Tong {
10     public static void main(String[] args) {
11         int[] a = {32,45,42,51,53,86,95,53,93,55,59};
12         System.out.println("排序前：");
13         for(int i=0;i<a.length;i++){
14             System.out.print(a[i]+" ");
15         }
16 
17         //桶排序
18         sort(a);
19 
20         System.out.println("");
21         System.out.println("排序後：");
22         for(int i=0;i<a.length;i++){
23             System.out.print(a[i]+" ");
24         }
25     }
26 
27     private static void sort(int[] a){
28 
29         if(a==null || a.length==0){
30             return;
31         }
32 
33         int max=0,min=0;
34         for(int i=0;i<a.length;i++){
35             max = Math.max(max,a[i]);
36             min = Math.min(min,a[i]);
37         }
38 
39         //確定桶數，並且建立一系列的桶
40         int bucketNum = (max-min)/a.length+1;
41         ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
42         for (int i=0;i<bucketNum;i++){
43             bucketArr.add(new ArrayList<Integer>());
44         }
45 
46         //將每個元素放入桶
47         for(int i=0;i<a.length;i++){
48             int num = (a[i]-min)/a.length;
49             bucketArr.get(num).add(a[i]);
50         }
51 
52         //對每個桶進行排序
53         for(int i=0;i<bucketArr.size();i++){
54             Collections.sort(bucketArr.get(i));
55         }
56 
57         int index = 0;
58         for(int i=0;i<bucketArr.size();i++){
59             while (bucketArr.get(i).size()>0){
60                 a[index++] = bucketArr.get(i).get(0);
61                 bucketArr.get(i).remove(0);
62             }
63         }
64     }
65 }

3、分析