您能否给我我制作的这个新选择排序算法的时间近似值（例如 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) =  Theta(N^2)