修改后的选择排序代码的时间复杂度是多少？

Question

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--;
    }
}

在这里，我尝试通过在每次传递期间查找最小和最大元素，然后将它们与搜索空间的最右边和最左边的元素交换来改进选择排序算法。搜索空间最初等于输入数组的大小，并且当我们在每次传递中对 2 个元素进行排序时，搜索空间在每次传递后都会减少 2。

由于我使用了嵌套循环，我认为其时间复杂度为 O(n^2)。

Answer 1

此实现在 O 表示法中的时间复杂度为 O(n^2)，因为省略了 O 表示法中的常数。

如果想大幅降低计算复杂度，我建议使用归并排序，其复杂度为O(n*log(n))。算法原理如下所示：归并排序