求该改进版选择排序（selectionSort）代码的时间复杂度

你的代码（修正转义后） #

void simpleSort(int arr[], int arrSize){

    /*initial searchSpace bounds*/
    int left = 0;
    int right = arrSize-1;
    
    int maxElem, minElem, maxElemIndex, minElemIndex;

    while(left < right){

        /*setting default value for max and min in the array*/
        maxElem = minElem = arr[left];
        minElemIndex = maxElemIndex = left;

        //1. iterate array to find index of min and max elements
        for(int i = left; i<= right; i++){
            if(arr[i] >= maxElem){
                maxElem = arr[i];
                maxElemIndex = i;
            }
            if(arr[i] <= minElem){
                minElem = arr[i];
                minElemIndex = i;
            }
        }

        //2. swap the min and max elements with leftmost and rightmost elements (for sorting in ascending order)
        if(left == maxElemIndex && right == minElemIndex){
            /*here if we do 2 swaps then both swaps will nullify each other*/
            swap(arr[left], arr[minElemIndex]);
        }
        else if(left == maxElemIndex){
            swap(arr[right], arr[maxElemIndex]);
            swap(arr[left], arr[minElemIndex]);
        }
        else{
            swap(arr[left], arr[minElemIndex]);
            swap(arr[right], arr[maxElemIndex]);
        }

        //3. converging the searchSpace window as the leftmost and rightmost elements are sorted now
        left++;
        right--;
    }
}

时间复杂度分析 #

你的判断是正确的，这个优化版选择排序的时间复杂度仍然是O(n²)，推导如下：

• 外层循环次数：初始left=0，right=arrSize-1，每次循环left+1、right-1，直到left >= right，总共执行⌈n/2⌉次，属于O(n)量级。
• 内层循环遍历次数：
  第一次遍历长度为n，第二次为n-2，第三次为n-4，以此类推，最后一次遍历长度为1（n为奇数）或2（n为偶数）。总遍历次数是等差数列求和：
  • 当n为偶数：n + (n-2) + (n-4) + ... + 2 = (n/2)*(n+2)/2 = (n²+2n)/4
  • 当n为奇数：n + (n-2) + (n-4) + ... + 1 = ((n+1)/2)² = (n²+2n+1)/4
• 大O表示法简化：大O表示只关注最高次项的量级，忽略常数系数和低次项。上述两种情况的最高次项都是n²，因此时间复杂度为O(n²)。

另外，交换操作属于O(1)的常数时间操作，不会影响整体时间复杂度的量级。

内容的提问来源于stack exchange，提问作者VivekPrasad