如何檢查一個整數數組是否被排序？

你會有代碼，只是爲你排序，並在其完成排序後，看看是否有任何改變。你會使用某種類型有點像插入排序，選擇或類似的規定如何檢查一個整數數組是否被排序？

int[] arr = {4,1,3,8,9,2,7,0,5,6}; 
System.out.println(Arrays.toString(arr)); 
selectionSort(arr); 

public static void selectionSort (int []arr) { 
    for(int i = 0; i < arr.length; i ++) { 
     //find the ith element 
     int smallest = i; 
     for (int j = i + 1; j <arr.length; j++) { 
      //find the smallest unsorted element 
      if(arr[j] < arr[smallest]) { 
       smallest = j;

所以我想我在正確的軌道上，但我不知道如何整數比較，看看是否有全部的權利訂購。

我需要添加什麼？

來源

2012-02-10 user1186807

爲什麼要排序以確定它是否已排序？只需檢查每個元素，並確認它是> =前一個元素。 – 2012-02-10 06:42:18

如果您只想知道它們是否已排序......從頭開始並遍歷它們以查看。如果你想*他們排序......只需對它們進行排序。沒有理由在事物上添加O（n）。 – 2012-02-10 06:44:49

我只會循環查看，並檢查i + 1是否比我大。沒有理由讓它比需要的更難。除非有，你還沒有告訴我們。 – Justin 2012-02-10 06:43:37

它比這更簡單 - 只是迭代數組，看看每個元素是否比下一個更小。

int[] checkarray = ....; 

boolean sorted = true; 
for(int i = 1; i < checkarray.length; i++) { 
    if(checkarray[i-1] > checkarray[i]){ 
      sorted = false; 
      break; 
    } 
} 

System.out.println("Sorted: " + sorted);

來源

2012-02-10 06:42:17

你將有代碼，只是排序，爲您和後對其做排序看看是否有任何變化

如果您是在作爲輸入陣列的方法，你期望被排序，但不確定是否是，你可以應用插入排序，因爲這對於接近排序的輸入來說是線性複雜的（否則對於大輸入而言是低效的算法）。

只是要清楚。

@Petar的答案是最簡單直接的答案。

我提到這個答案也是爲了完整性，因爲如果你不確定它是否在你的程序的特定時間被排序，那麼排序某些內容並不荒謬。

畢竟，如果它沒有完全排序，你已經完成了O(N)掃描沒有任何好處，你將有頂部O(NlogN)排序的額外的複雜性。

這實際上是大多數排序算法的算法分析提到它們在排序輸入上的性能的原因，因爲它比我們預期的更頻繁發生。
你的情況就是一個例子。

來源

2012-02-11 15:39:39 Cratylus

-1

選擇排序是最簡單的排序技術，它使用線性搜索來掃描列表或數組，但排序和強烈推薦的更好方法是快速排序。快速排序是基於分而治之的理論，我們不斷將一個列表分成各種較小的子列表，然後將它們排序。請閱讀維基百科的快速排序。還需要了解的是，各種排序技術如何根據典型數據（如「所有相同數據」）的發生情況執行，等等。

來源

2014-02-24 12:38:26 rajibdotnet

這是如何回答這個問題的？ – 2014-02-24 12:44:44

//def ArrayList listOfItemsForSorting = ["a", "B", "c"]; 
//def String sortOrder = "ASC" or "DESC" 

def boolean sortItemsWithCollator(ArrayList listOfItemsForSorting, String sortOrder) { 
    Collator myCollator = Collator.getInstance(); 
    // check if the array itself is less than 2 items if so, it's clearly no need for sorting. 
    if (listOfItemsForSorting.size() < 2) { 
     return true; 
    } 
    else if (sortOrder.equals("ASC")){ 
     for (def i = 0; i < listOfItemsForSorting.size() - 1; i++) { 
       if (myCollator.compare(listOfItemsForSorting[i], listOfItemsForSorting[i + 1]) > 0) { 
       return false; 
      } 
     } 
    } 
    else{ 
     for (def i = 0; i < listOfItemsForSorting.size() - 1; i++) { 
       if (myCollator.compare(listOfItemsForSorting[i], listOfItemsForSorting[i +1]) < 0) { 
       return false; 
      } 
     } 
    } 
    return true; 
}

此方法返回s布爾值。

來源

2015-10-30 15:31:28

如何檢查一個整數數組是否被排序？

回答

相關問題