使用选择排序算法对数组进行排序时存在的问题

6pp0gazn 于 2022-10-01 发布在 Java

关注(0)|答案(2)|浏览(143)

当在选择函数中传递数组时，我只为正实数获得了所需的排序数组，但对于负数，它无法做到这一点。

static void selection(int[] array) {
            for (int i = 0; i < array.length; i++) {
                int last = array.length - i - 1;
                int max= getMaxIndex(array, 0, last);
                swap(array, max, last);
            }
       }
        static void swap(int[] arr, int first, int second) {
            int temp = arr[first];
            arr[first] = arr[second];
            arr[second] = temp;
        }
        static int getMaxIndex(int[] arr, int start, int last) {
            int max = start;
            for (int i = 0; i < last; i++) {
                if (arr[max] < arr[i]) {
                    max = i;
                }
            }
            return max;
        }

Java

来源：https://stackoverflow.com/questions/73912474/problem-in-sorting-array-using-selection-sort-algorithm

2条答案

按热度按时间

smtd7mpg1#

您没有说明您是否尝试以升序或降序的方式进行排序，但我继续进行并假定为升序。问题是，您正在对数组进行反向排序，因此您的方法：

static int getMaxIndex(int[] arr, int start, int last) {
        int max = start;
        for (int i = 0; i < last; i++) {
            if (arr[max] < arr[i]) {
                max = i;
            }
        }
        return max;
    }

返回错误的值。它应该是：

static int getMaxIndex(int[] arr, int last) {
    int max = last;
    for (int i = 0; i < last; i++) {
        if (arr[max] < arr[i]) {
            max = i;
        }
    }
    return max;
}

您的实现中不需要Start参数。Max应该从我们正在排序的当前索引开始。

然而，您的解决方案相当复杂。当正常进行选择排序时，我们想要搜索从i+1位置到数组末尾的下一个最低值，如果它较小，则与数组第i个位置的值交换。这个实现对我来说更有意义：

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

赞(0）回复(0）举报 2022-10-01

7kjnsjlb2#

当初始数组的最后几个索引接近它们在最终排序数组中的应有位置时，您的算法也会失败。

这里的问题是，您正确地计算了子数组的最后一个索引，但是在getMaxIndex内部，您循环到last-1(i<last)，这意味着实际上没有检查子数组的最后一个索引，看它是否是最大索引。将getMaxIndex循环条件更改为I<=last可以修复该问题。

赞(0）回复(0）举报 2022-10-01