您能否给我我制作的这个新选择排序算法的时间近似值（例如 n^2 ， n*2 ， nlogn ）

Question

新的修改选择排序算法（在某些情况下优于插入排序）与标准选择排序算法类似，但它只在 Array 中搜索最小值，而是在一次迭代中搜索最小值和最大值。然后它将最小值交换到数组的开头，将最大值交换到数组的末尾。递增start_pointer、递减end_pointer，然后再次迭代。我认为对 N 大小的数组进行排序所需的时间复杂度是：N + (N-2) + (N-4) + (N-6) + ... + 1。有人可以给我这个公式的近似值吗？我将不胜感激。

public static void DoubleSelectionSort(int[] Array, int startpos, int endpos) {

    /*Double Selection Sort Algorithm , made by Milan Domonji 1986 , [e-mail]*/

    while(startpos < endpos) {

        int min = Integer.MAX_VALUE;

        int max = Integer.MIN_VALUE;

        int minpos = startpos;

        int maxpos = endpos;

        for(int i = startpos; i <= endpos; i++) {

            //main loop that finds minimum and maximum from an Array

            if (Array[i] <= min) {

                min = Array[i];

                minpos = i;

            }

            if (Array[i] >= max) {

                max = Array[i];

                maxpos = i;

            }   

        }

        /* I added missing part of algorithm so it works now (Edited) */

        if (maxpos==startpos && minpos==endpos) {

            Swap(Array, minpos, maxpos);

        }else {

             if (maxpos==startpos) {

                Swap(Array,minpos,startpos);

                Swap(Array,minpos,endpos);              

             }else {

               Swap(Array,minpos,startpos);

               Swap(Array,maxpos,endpos);

          }

        }

        startpos++;

        endpos--;

  }

}

private static void Swap(int[] Array, int A, int B) {

    int tmp = Array[A];

    Array[A] = Array[B];

    Array[B] = tmp;

}

算法对所有时间进行正确排序。

Answer 1

如果您需要总和S = N + (N-2) + (N-4) + ... + (N - (N-2))（例如N是偶数），则它等于S = 2 + 4 + ... + N = 2 ( 1 + 2 + 3 + ... + N/2) = 2 * N/2 * (N/2 + 1)/2 = N/2 * (N/2 +1) = &nbsp;Theta(N^2)