如何排序N長度數組中的第一個M元素？

我有一些關於在C＃中對數組進行排序的任務。我一直在想我能想到的一切 - 沒有運氣。如何排序N長度數組中的第一個M元素？

任務是通過已知的排序算法（插入，選擇，泡泡，快速）對整數數組進行排序。事情是，我必須排序只有最小的M元素。

示例：我有一個由7個元素組成的數組2 9 8 3 4 15 11，我需要對最小的3個元素進行排序，以便我的數組變成2 3 4 9 8 15 11。

請幫助，我似乎無法在SO中找到任何東西，也無法通過Google找到任何東西。我不要求爲我做所有的算法，我只需要其中的一個來抓住這種可能性。 E：謝謝你的想法。我查看了所有的建議，並已經完成，使插入排序這樣的：

static int[] insertSort(int[] arr, out int swaps, out int checks) { 
    int step = 0; 
    swaps = 0; 
    checks = 0; 
    for (int i = 0; i < arr.Length; i++) { 
     int min = arr[i], minind = i; 
     for (int j = i + 1; j < arr.Length; j++) { 
      checks++; 
      if (arr[j] < min) { 
       min = arr[j]; 
       minind = j; 
      } 
     } 
     int temp = arr[minind]; 
     if (step < M) { 
      for (int j = minind; j > i; j--) { 
       swaps++; 
       arr[j] = arr[j - 1]; 
      } 
      arr[i] = temp; 
      swaps++; 
      step++; 
     } 
    } 
    return arr; 
}

互換和支票 - 我的應用需求。

P.S.我已經看過很多次，所以不喜歡爲某人做作業。這就是爲什麼我沒有要求代碼，我只是想了解如何實現這一點。

再次感謝那些幫助過我的人。

來源

2012-11-26 YOhan

功課可能會導致問題.... – flindeberg

爲什麼會這樣呢？難？你只是假裝數組比實際短並對其進行分類。 – Earlz

@Earlz再次閱讀問題...... –

由於沒有效率的侷限性：

我設置爲0
外觀爲未排序的元素中最小的。
將它插入位置i，移動陣列。
增量i。
重複M次。

複雜性是O（N * M）。

來源

2012-11-26 15:55:57 Andrei

這是插入排序。他列舉了他需要使用的幾個排序實現;這是其中之一。 – Servy

@Servy我也只是要求其中一種算法來了解它的可能性。我**不需要**每種方法的解釋:) 我現在就試試這個。 – YOhan

作爲氣泡提示，在第一遍時，您還可以掃描最低的M個元素，在列表或數組中記住它們，並在任何進一步掃描中只在至少一個被交換的元素處於該清單。這應該只是一個實現，知道它是在沒有交換執行交換時完成的。 – KeithS

沒有看到您的實施，這很難回答。有很多方法可以做到這一點，而且大多數是直截了當的。

這裏有一些想法，但：

創建一個「臨時」陣列，只有持有數量進行排序，排序，然後替換原始數組（可能是一個次優解）
使用循環迭代你需要的次數（3或者其他）。這可能是最好的解決方案
將你的代碼發佈在SO上，一些天真的人可能會給你一個解決方案，所以你不必自己做功課。（這是一個懶惰和不好的解決方案）

來源

2012-11-26 15:53:11 HackyStack

你想看看你需要使用什麼排序算法。舉例來說，我們正在使用一個使用for循環的程序。大多數情況下，你會看到這樣的事情

的for（int i = 0;我< arrayName.length（）;我++） {}

在你的情況，只是改變的參數for循環

對（INT I = 0;我<米;我++） {}

其中M是小於arrayName.length（）;並且是您想要排序的起始位置的數量。

未改動的陣列的其餘部分應保持不變。

來源

2012-11-26 15:54:11

如果你看看這個例子，它不是說源數組的前N個項目是排序的，它應該正確排序完全排序數組的前N個項目。 – Chris

這不符合要求。 OP想要排列數組中的M *個最小*元素，而不是M * first *。 –

@Chris＆Konrad。對於插入排序，冒泡排序和選擇排序，它們是相同的。循環的每次迭代都將一個項目移動到數組的前面。儘管這對於快速排序來說不太合適，但它會有所不同。顯然這在一般情況下不起作用;它只是*發生*幾乎適用於所有OP的情況。 – Servy

夫婦的事情。大多數排序算法使用array.length作爲最大範圍。你可不可以只用m？即

for (int i = 0; i < m; i++)

此外，您可以使用前m個字符的臨時數組，然後重新分配它。

int[] temp; 
for (int i = 0; i < m; i++) 
{ 
    temp[i] = realArray[i]; 
} 
//sort, then 
for (int i = 0; i < m; i++) 
{ 
    realArray[i] = temp[i]; 
}

來源

2012-11-26 15:57:36

-2

使用LINQ的任何處方？

int a[] = new int[] {2, 9, 8, 3, 4, 15, 11}; 
const int M = 5; 
a = a.Take(M).OrderBy(e => e).ToArray(); // EDIT: Added .ToArray()

來源

2012-11-26 16:02:21

這是騙人的heh – Earlz

@Earlz，是的，但使用SO也是。並感謝upvote，我剛爆發9000. –

嘗試執行此操作;它不會產生所需的輸出。 – Servy

我想這裏是你在找什麼，這是一個基於特定指數排序數組升序的例子。

 int startIndex=2; 
     int endIndex=5; 
     int[] elements=new int[7]; 
     elements[0]=2; 
     elements[1]=9; 
     elements[2]=8; 
     elements[3]=3; 
     elements[4]=4; 
     elements[5]=15; 
     elements[6]=11; 
     for (int a=startIndex-1;a<endIndex;a++){ 
      for(int b=startIndex-1;b<endIndex;b++){ 
       if (elements[a]<elements[b]){ 
        int temp =elements[a]; 
        elements[a]=elements[b]; 
        elements[b]=temp; 
       } 
      } 
     } 
     for (int c=0;c<elements.Length;c++){ 
      Console.Write(elements[c]+","); 
     }

只要改變「<」到「>」，如果你想對它進行排序遞減。

來源

2012-11-26 16:16:13 Godfre

我會排序整個數組，並將其放入另一個。

截斷新數組只保留最小的x個元素。從該數組中獲取最大數字（在您的示例中，4）。

循環遍歷初始數組並追加所有更高的數字。

輸入：2 9 8 3 4 15 11
排序所有：2 3 4 8 9 11 15
截斷：2 3 4

從這個數組獲取最高值（4）
通過原始數組循環並追加

是2高於4嗎？沒有
是9高於4嗎？是的，追加（我們現在有：2 3 4 9）
是8高於4嗎？是的，追加（我們現在有：2 3 4 9 8）
是3高於4？沒有
是4高於4嗎？沒有
是15高於4嗎？是的，追加（我們現在有：2 3 4 9 8 15）
是11高於4嗎？是的，追加（我們現在有：2 3 4 9 8 11）

*這是不是最有效的方法，如果您有重複號碼

來源

2012-11-26 16:27:07

如何排序N長度數組中的第一個M元素？

回答

相關問題