选择排序算法问题

Question

所以我有这个代码用于我的选择排序：

public static void selectionSort(int[] arrayToSort){
    int smallest;
    for(int i = 0; i < arrayToSort.length; i++){
        smallest = i;
        for(int j = i+1; j < arrayToSort.length; j++){
            if(arrayToSort[j] < arrayToSort[smallest]){
                smallest = j;
            }
            if(smallest != i){
                int temp = arrayToSort[i];
                arrayToSort[i] = arrayToSort[smallest];
                arrayToSort[smallest] = temp;
            }
        }
    }
}

我正在生成一个带有随机数的整数数组。我的选择排序有时对数组进行排序，有时对数组进行 "almost" 排序。除了极少数位于错误位置的数字外，数组大部分都会被排序。我不知道这里出了什么问题，有什么想法吗？

数组未完全排序的部分测试结果：

***NON SORTED***
77
53
27
58
83
***SORTED***
27
53
77
58
83

和

***NON SORTED***
40
87
27
48
82
***SORTED***
27
40
82
48
87

Answer 1

你有一部分代码在内循环中，把它放在循环外；

public static void selectionSort(int[] arrayToSort){
    int smallest;
    for(int i = 0; i < arrayToSort.length; i++){
        smallest = i;
        for(int j = i+1; j < arrayToSort.length; j++){
            if(arrayToSort[j] < arrayToSort[smallest]){
                smallest = j;
            }
        }
        if(smallest != i){
            int temp = arrayToSort[i];
            arrayToSort[i] = arrayToSort[smallest];
            arrayToSort[smallest] = temp;
        }
    }
}

例如 algorithm in Wikipedia。

Answer 2

我在 大学项目 中需要它时就这样做了！

参考资料：selection algoritm with figure

public static void selectionSort(int[] arr){  
        for (int i = 0; i < arr.length - 1; i++)  
        {  
            int index = i;  
            for (int j = i + 1; j < arr.length; j++){  
                if (arr[j] < arr[index]){  
                    index = j;//searching for lowest index  
                }  
            }  
            int smallerNumber = arr[index];   
            arr[index] = arr[i];  
            arr[i] = smallerNumber;  
        }  
    }

Answer 3

在第二个 foor 循环中，如果您发现任何小于 i（或最小）的元素，那么您正在执行此处不需要的交换操作。在选择排序中，您需要从未排序的数组中获取最小的元素并与最左边的元素交换，并且该元素成为已排序数组的一部分。只需将交换保持在第二个内部循环之外，这样它只对最小元素进行交换操作。

for(int i = 0; i < arrayToSort.length; i++){
    smallest = i;
    for(int j = i+1; j < arrayToSort.length; j++){
        if(arrayToSort[j] < arrayToSort[smallest]){
            smallest = j;
        }
    }
    if(smallest != i){
        int temp = arrayToSort[i];
        arrayToSort[i] = arrayToSort[smallest];
        arrayToSort[smallest] = temp;
    }
}

选择排序算法问题

Selection sort algorithm problems

java

arrays

sorting

algorithm

selection-sort