选择排序实现，我一直在计算交换次数的时间复杂度

Question

static int count = 0;
for (int i = 0; i < arr.length; i++) {
    for (int j = i + 1; j < arr.length; j++) {
        if (arr[i] > arr[j]) {
            swap(arr, i, j);
            count++;
        }
    }
}

这是选择排序的正确实现吗？使用此实现，我不会得到 O(n-1) 的交换复杂度。

Answer 1

Is this the correct implementation for selection sort?

这取决于，逻辑上你做的是正确的。它使用 "find the max/min value in the array" 排序。但是，在选择排序中，通常在一次迭代中不需要多次交换。您只需将 max/min 值保存在数组中，然后在最后将其与 i-th 元素

交换

I am not getting O(n-1) complexity for swaps

你是说n-1次swap吗？是的，它发生是因为你每次交换都会找到一个更大的值，而不仅仅是最大值。您可以尝试像这样重写您的代码：

static int count=0;
static int maximum=0;
for(int i=0;i<arr.length-1;i++){
    maximum = i;
    for(int j=i+1;j<arr.length;j++){
        if(arr[j] > arr[maximum]){
            maximum = j;
        }
    }
    swap(arr[maximum],arr[i]);
    count++;
}

另外，如果你想精确交换 n-1 次，你的 i 迭代也应该改变。

选择排序实现，我一直在计算交换次数的时间复杂度

Selection sort implementation, I am stuck at calculating time complexity for number of swaps

time-complexity

selection-sort