使用时间复杂度为 0(1) 的选择算法对已排序数组进行排序

Question

如果数组已经排序，那么如何停止排序。时间复杂度0（1）对于选择排序的排序数组。

static void sort(int a[]){
   int min;
     for(int i=0;i<a.length-1;i++){
         min=i;
         for(int j=i+1;j<a.length;j++)
         {

             if(a[j]<a[min])
                 min=j;

         }
         if(min==0){
             System.out.print("min" + min);
             break;
         }
         int temp=a[min];
         a[min]=a[i];
         a[i]=temp;

     }
    System.out.print(Arrays.toString(a) );

 }

Answer 1

你有一个 Selection sort，当数组排序时，它不适合 "early out"。

想想它在做什么：

找到数组中的最小项并将其放在位置 0。
找到最小的剩余项目并将其放在位置 1。
重复，找到第 k 个最小的项目并将其放在位置 k，直到 k = n。

该算法不进行任何比较以查看数组的其余部分是否有序。

我想你可以添加这样的东西：

static void sort(int a[]) {
   for(int i=0;i<a.length-1;i++){
       Boolean isSorted = true;
       Boolean didExchange = false;
       int min=i;
       for(int j=i+1;j<a.length;j++)
       {
           if(a[j]<a[min])
           {
               min=j;
           }
           if (a[j] < a[j-1])
           {
               // if at any point an item is smaller than its predecessor,
               // then the array is not sorted.
               isSorted = false;
           }
       }
       if (min != i)
       {
           didExchange = true;
           int temp=a[min];
           a[min]=a[i];
           a[i]=temp;
       }
       // If no exchange was made, and isSorted is still true,
       // then the array is sorted.
       if (isSorted && !didExchange)
       {
           break;
       }
   }
   System.out.print(Arrays.toString(a) );

}

这会产生一些混乱的代码。选择排序是标准 O(n^2) 排序算法中效率最低的一种。 Bubble sort and Insertion sort 都具有更好的实际性能，并且都更容易修改以检测已排序的数组。事实上，你根本不需要修改插入排序； "early out" 只是基本算法的一部分。

顺便说一句，即使对数组进行排序，这也需要O(n)。您无法确定数组是否在 O(1) 中排序，因为您必须检查所有 n 项。

使用时间复杂度为 0(1) 的选择算法对已排序数组进行排序

sorting the sorted array with selection algorithm with time complexity 0(1)

sorting

algorithm

selection-sort