??? 對(duì)于常見(jiàn)的排序算法，很難做到在O(n)時(shí)間內(nèi)排序，并且空間復(fù)雜度為O(1)，這里提供了一種方法可以達(dá)到要求。

? ? 可以使用哈希排序的思想，也就是將所有的數(shù)哈希到哈希表中，實(shí)現(xiàn)排序。具體的算法思想是，求出這組數(shù)據(jù)的最大值和最小值，分三種情況討論：

? ? ? ? ? ? ?1、如果最小值為負(fù)數(shù)，在哈希的時(shí)候把每個(gè)數(shù)都加上最小值的相反數(shù)，作為數(shù)組的下標(biāo)值。

? ? ? ? ? ? ?2、如果最小值為0，則直接將每個(gè)數(shù)作為下標(biāo)值

? ? ? ? ? ? ?3、如果最小值為正數(shù)，則將每個(gè)數(shù)減去最小值作為下標(biāo)值

? ? ? ? ? ? ?綜合三種情況，可以歸結(jié)為一個(gè)方法，就是令每個(gè)數(shù)減去最小值即可。

? ? ? ? ? 這樣就可以建立一個(gè)數(shù)組，下標(biāo)作為key，數(shù)組值作為value，初始化每個(gè)value為0，表示不存在對(duì)應(yīng)的key值，當(dāng)出現(xiàn)對(duì)應(yīng)的key值時(shí)，就令其value值加1，如果存在重復(fù)的值，就將下標(biāo)對(duì)應(yīng)的value值重復(fù)加1計(jì)數(shù)，最后打印輸出的時(shí)候，從頭開(kāi)始掃描數(shù)組，當(dāng)value不為0時(shí)，將對(duì)應(yīng)的key值加上或減去最小值輸出即可，如果value大于1，就重復(fù)輸出。

? ? ? ? ? ?JAVA代碼實(shí)現(xiàn)如下：

1 public class HeapSort { 2 3 public static void heapsort(int[] array){ 4 int n=array.length; //求出原數(shù)組長(zhǎng)度 5 if(n<=0)return; //如果數(shù)組長(zhǎng)度為0，直接退出 6 7 int min=array[0],max=array[0]; 8 System.out.print("排序前："); 9 for(int i=0;i<n;i++) //輸出排序前的數(shù)組，并求出最大值和最小值 10 { 11 if(min>array[i])min=array[i]; 12 if(max<array[i])max=array[i]; 13 System.out.print(array[i]+" , "); 14 } 15 System.out.println(); 16 17 int[] H=new int[max-min+1]; //哈希表 18 for(int i=0;i<H.length;i++) //初始化哈希表 19 H[i]=0; 20 21 for(int i=0;i<n;i++) //哈希排序 22 H[array[i]-min]++; 23 24 System.out.print("排序后："); //輸出排序后的數(shù)組 25 for(int i=0;i<H.length;i++) 26 for(int j=1;j<=H[i];j++) 27 System.out.print(i+min+" , "); 28 } 29 30 public static void main(String[] args) { 31 int[] array={-5,6,9,15,-3,9}; 32 heapsort(array); //調(diào)用哈希排序 33 } 34 35 } View Code

?

程序輸出結(jié)果為：

排序前：-5 , 6 , 9 , 15 , -3 , 9 ,?

排序后：-5 , -3 , 6 , 9 , 9 , 15 ,?

轉(zhuǎn)載于:https://www.cnblogs.com/guozhenqiang/p/5424441.html

總結(jié)

以上是生活随笔為你收集整理的如何实现在O(n)时间内排序，并且空间复杂度为O(1)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。