选择排序但每次迭代只切换一次

Question

我写了一个选择排序算法，它由两个 for 循环组成。截至目前，内部循环可能会在递增外部循环之前多次交换数字。但是，我现在的目标是让内部循环恰好交换数字一次，然后返回到外部 for 循环并重复此操作，直到对数组进行排序。我已经用 break 语句试过了，但是它没有正确地对整个事情进行排序。

    private static void selectionSort(int[] array) {        //Array wird sortiert
        
        for(int i = 0; i < array.length - 1; i++) {
            
            for(int a = i + 1; a < array.length; a++) {
                
                if(array[i] > array[a]) {
                    
                    int temporaer = array[i];
                    array[i] = array[a];
                    array[a] = temporaer;
                    break;
                    
                }
                
            }
                    
        }
        
    }

你们能帮帮我吗？

Answer 1

选择排序的工作原理是在外循环的第 i 次迭代中找到第 i 个最小的元素，然后将该元素交换到位置 i。当外层循环完成第 i 次迭代后，整个数组应该从位置 0 到 i 排序。内部循环通过遍历数组的整个未排序部分并找到其中的最小元素来找到第 i 个最小元素。所以它应该看起来像这样：

    private static void selectionSort(int[] array) {        //Array wird sortiert
        
        for(int i = 0; i < array.length - 1; i++) {
            // das Minimum finden
            int min = array[i];
            int minIdx = i;
            for(int a = i + 1; a < array.length; a++) {
                if(array[a] < min) {
                    min = array[a];
                    minIdx = a;  
                }   
            }
            // Austauschen
            int temp = array[i];
            array[i] = min;
            array[minIdx] = temp;          
        } 
    }

如果没有 break 语句，您仍然可以有效地将最小元素放入位置 i，只是不必执行那么多交换即可。只需使用局部变量来跟踪您找到的最小值 is/where，并在最后进行一次交换。

选择排序但每次迭代只切换一次

Selection Sort but just one switch each iteration

java

arrays

sorting

selection-sort