按數字順序排序N個數字

Question

給定N個數字範圍E.g. [1至100]按數字順序對數字排序（即）對於數字1至100，排序的輸出傷口爲 1 10 100 11 12 13。 。 。 19 2 20 21 ..... 99

這就像基數排序，但只是數字按相反的順序排序，以正常的基數排序完成。

我嘗試將每個數字中的所有數字都作爲鏈接列表存儲，以便更快地操作，但這會導致較大的空間複雜度。

我需要一個工作算法的問題。

從所有的答案，「轉換爲字符串」是一個選項，但是沒有其他辦法可以做到嗎？ 也可以給出如上所述的排序字符串的算法。

Answer 1

使用任何你喜歡的排序算法，但比較數字作爲字符串，而不是數字。這基本上是對常規數字進行的加法排序。這裏的C中的例子侏儒排序：

#include <stdlib.h> 
#include <string.h> 

void sort(int* array, int length) { 
    int* iter = array; 
    char buf1[12], buf2[12]; 
    while(iter++ < array+length) { 
     if(iter == array || (strcmp(itoa(*iter, &buf1, 10), itoa(*(iter-1), &buf2, 10) >= 0) { 
      iter++; 
     } else { 
      *iter ^= *(iter+1); 
      *(iter+1) ^= *iter; 
      *iter ^= *(iter+1); 
      iter--; 
     } 
    } 
} 

當然，這需要非標準itoa函數存在於stdlib.h。更標準的選擇是使用sprintf，但這會使代碼更加混亂。你可能會更好地將整個數組轉換爲字符串，然後進行排序，然後將其轉換回來。

編輯：作爲參考，這裏的相關位是strcmp(itoa(*iter, &buf1, 10), itoa(*(iter-1), &buf2, 10) >= 0，它取代*iter >= *(iter-1)。

Answer 2

我想如果您將數字轉換爲字符串，您可以使用字符串比較來對它們進行排序。 你可以使用anny爲它排序alghorighm。

「1」 <「10」 <「100」 <「11」 ......

Answer 3

我有一個解決方案，但不是完全的算法。所有你需要做的是所有的數字轉換爲字符串&將它們排序爲字符串..

Answer 4

編輯：我錯過了它是一個連續的範圍。既然如此，所有關於對數組進行排序的答案都是錯誤的（包括你的想法在問題中陳述它就像一個基數類型），True Soft的答案是正確的。

就像基數排序，但只是數字以相反的順序排序

那麼看準:-)如果你真的這樣做的，有趣的是，這就是所謂的MSD基數排序。

http://en.wikipedia.org/wiki/Radix_sort#Most_significant_digit_radix_sorts

你可以實現一個非常簡單地，或者有很多高科技和大張旗鼓的。在大多數編程語言中，您的特定示例面臨一些困難。從一個整數的自然存儲格式中提取十進制數字不是一個特別快的操作。您可以忽略它並查看最終結束時間（推薦），或者您可以在排序前將所有數字轉換爲十進制字符串以增加更多的誇張聲音。

當然，您不必將其實現爲基數排序：您可以使用比較排序算法和適當的比較器。例如，在C，以下是適用於快速排序使用（除非我搞砸了）：

int lex_compare(void *a, void *b) { 
    char a_str[12]; // assuming 32bit int 
    char b_str[12]; 
    sprintf(a_str, "%d", *(int*)a); 
    sprintf(b_str, "%d", *(int*)b); 
    return strcmp(a_str,b_str); 
} 

不是非常有效，因爲它做了很多重複勞動，而是直截了當的。

Answer 5

這裏是你如何可以用遞歸函數來完成它（代碼是在Java中）：

void doOperation(List<Integer> list, int prefix, int minimum, int maximum) { 
    for (int i = 0; i <= 9; i++) { 
     int newNumber = prefix * 10 + i; 
     if (newNumber >= minimum && newNumber <= maximum) { 
      list.add(newNumber); 
     } 
     if (newNumber > 0 && newNumber <= maximum) { 
      doOperation(list, newNumber, minimum, maximum); 
     } 
    } 
} 

你這樣稱呼它：

List<Integer> numberList = new ArrayList<Integer>(); 
int min=1, max =100; 
doOperation(numberList, 0, min, max); 
System.out.println(numberList.toString()); 

---

編輯：

我翻譯了我的代碼在C++ here：

#include <stdio.h> 

void doOperation(int list[], int &index, int prefix, int minimum, int maximum) { 
    for (int i = 0; i <= 9; i++) { 
     int newNumber = prefix * 10 + i; 
     if (newNumber >= minimum && newNumber <= maximum) { 
      list[index++] = newNumber; 
     } 
     if (newNumber > 0 && newNumber <= maximum) { 
      doOperation(list, index, newNumber, minimum, maximum); 
     } 
    } 
} 

int main(void) { 
     int min=1, max =100; 
     int* numberList = new int[max-min+1]; 
     int index = 0; 
     doOperation(numberList, index, 0, min, max); 
     printf("["); 
     for(int i=0; i<max-min+1; i++) { 
       printf("%d ", numberList[i]); 
     } 
     printf("]"); 
     return 0; 
} 

基本上，這個想法是：對於每個數字（0-9），如果它在minimum和maximum之間，我將它添加到數組中。然後，我用這個數字作爲前綴調用相同的函數。它也是這樣做的：對於每個數字，它將其添加到前綴（prefix * 10 + i），並且如果它在限制之間，則將其添加到數組中。它在newNumber大於最大值時停止。

Answer 6

如果您不想將它們轉換爲字符串，但有足夠的空間來存儲列表的額外副本，我將存儲比副本中的元素少十倍的最大功率。這可能是最容易做到的一個循環。現在請撥打您的原始數組x和十個y的冪。

int findPower(int x) { 
    int y = 1; 
    while (y * 10 < x) { 
     y = y * 10; 
    } 
    return y; 
} 

你也可以計算出它們直接

y = exp10(floor(log10(x))); 

但我懷疑迭代可能比轉換和從浮點速度更快。

爲了將i日和j th元素

比較

bool compare(int i, int j) { 
    if (y[i] < y[j]) { 
    int ti = x[i] * (y[j]/y[i]); 
    if (ti == x[j]) { 
     return (y[i] < y[j]); // the compiler will optimize this 
    } else { 
     return (ti < x[j]); 
    } 
    } else if (y[i] > y[j]) { 
    int tj = x[j] * (y[i]/y[j]); 
    if (x[i] == tj) { 
     return (y[i] < y[j]); // the compiler will optimize this 
    } else { 
     return (x[i] < tj); 
    } 
    } else { 
    return (x[i] < x[j]; 
    } 
} 

這裏正在做的是我們被十合適的電源，使兩個數字有相同數量的倍增數量較少數字，然後比較它們。如果兩個修改的數字相等，則比較數字長度。

如果你沒有空間來存儲y數組，你可以在每次比較時計算它們。

通常，使用預優化的數字轉換例程可能會更好。

Answer 7

優化您存儲數字的方式：使用允許簡單訪問特定數字的binary-coded decimal (BCD)類型。然後，您可以使用您當前的算法，其中Steve Jessop正確識別爲most significant digit radix sort。

我想所有的數字每個號碼存儲在 爲 更快的操作一個鏈表，但它會導致 大空間複雜。

存儲在鏈表浪費空間的每個數字兩種不同的方式：

1. 一個數字（0-9）只需要內存來存儲4位，但你可能在任何地方使用從8位到64位。 A char或short類型需要8位，並且int可能需要多達64位。這比最佳解決方案使用2倍至16倍的內存！
2. 鏈接列表添加額外的不必要的內存開銷。對於每個數字，您需要額外的32到64位來存儲下一個鏈接的內存地址。同樣，這將每個數字所需的內存增加8倍到16倍。

甲內存更有效的解決方案存儲BCD數字連續存儲：

1. BCD僅使用每數位4位。
2. 將數字存儲在連續的內存塊中，如數組。這消除了存儲內存地址的需要。你不需要鏈接列表的能力，輕鬆地插入/從中間刪除。如果您需要將數字增長到未知長度的能力，還有其他抽象數據類型可以讓這些數據的開銷更小。例如，一個vector。

一個選項，如果其他操作如加法/乘法不重要，則分配足夠的內存來存儲每個BCD數字加一個BCD終止符。 BCD終止符可以是4位的任何組合，不用於表示BCD數字（如二進制1111）。不過，以這種方式存儲會使其他操作如加法和乘法更加棘手。

請注意，這與轉換爲字符串和按字典順序排列這些字符串的想法非常相似。整數在內部存儲爲二進制（基2）在計算機中。以BCD存儲更像是基數10（實際上基數爲16，但忽略6種組合），字符串類似於基數256.字符串將使用大約兩倍的內存，但已經有效的函數被寫入對字符串進行排序。 BCD可能需要爲您的需求開發一種自定義BCD類型。