如何检查一个整数数组是否被排序？

问题描述：

你会有代码，只是为你排序，并在其完成排序后，看看是否有任何改变。你会使用某种类型有点像插入排序，选择或类似的规定如何检查一个整数数组是否被排序？

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 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);

答

你将有代码，只是排序，为您和后对其做排序看看是否有任何变化

如果您是在作为输入阵列的方法，你期望被排序，但不确定是否是，你可以应用插入排序，因为这对于接近排序的输入来说是线性复杂的（否则对于大输入而言是低效的算法）。

只是要清楚。

@Petar的答案是最简单直接的答案。

我提到这个答案也是为了完整性，因为如果你不确定它是否在你的程序的特定时间被排序，那么排序某些内容并不荒谬。

毕竟，如果它没有完全排序，你已经完成了O(N)扫描没有任何好处，你将有顶部O(NlogN)排序的额外的复杂性。

这实际上是大多数排序算法的算法分析提到它们在排序输入上的性能的原因，因为它比我们预期的更频繁发生。
你的情况就是一个例子。

答

选择排序是最简单的排序技术，它使用线性搜索来扫描列表或数组，但排序和强烈推荐的更好方法是快速排序。快速排序是基于分而治之的理论，我们不断将一个列表分成各种较小的子列表，然后将它们排序。请阅读*的快速排序。还需要了解的是，各种排序技术如何根据典型数据（如“所有相同数据”）的发生情况执行，等等。

这是如何回答这个问题的？ – 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布尔值。

如何检查一个整数数组是否被排序？

相关推荐