时间戳

首页 > 解决方案 > 你能给我这个由我制作的新选择排序算法的时间近似值吗（如 n^2 ， n*2 ， nlogn ）

java - 你能给我这个由我制作的新选择排序算法的时间近似值吗（如 n^2 ， n*2 ， nlogn ）

问题描述

新修改的选择排序算法（在某些情况下优于插入排序）与标准选择排序算法类似，但它仅在 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 , MilanDomonji@yahoo.com*/

    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;

}

算法始终正确排序。

标签： javaarraysalgorithm

解决方案

如果你需要总和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)

推荐阅读