Java选择排序

Question

我在排序以检查每个索引时遇到问题。它跳过 j 的第三个索引，因为它从 i[0]、j[2] 到 i[0]、j[4] 我不知道为什么要这样做？另外，我在实际交换号码方面遇到了麻烦。有人知道我的错误在哪里吗？

static void selectionSort(int[] arr) {
    final long startTime = System.nanoTime(); // starts timer
    System.out.println("Selection Sort");
    //************** Code For Sorting *****************//
    //*************************************************//
    int counter = 0;
    int first = 0;
    int second = 0;
    
    // Copies unsorted array to new array
    //int[] sorted = Arrays.copyOf(arr, arr.length);
    
    // sorts unsorted array for comparison later on
    //Arrays.sort(sorted);
    
    // comparing the first index value to
    // the rest of the values in the array
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;

        // representing the next index value 
        // to the original and comparing it
        for (int j = 1; j < arr.length - 1; j++) {
            int nextIndex = j;

            if (arr[minIndex] < arr[nextIndex]) {
                System.out.println("i: " + i);
                System.out.println("j: " + j);
                System.out.println("Checking next index");
            }
            if (arr[minIndex] > arr[nextIndex]) {
                System.out.println("i: " + i);
                System.out.println("j: " + j);
                //counter = j; // getting array index
                first = arr[minIndex];
                second = arr[nextIndex];
                minIndex = second;
                arr[minIndex] = second;
                System.out.println("first:" + first);
                System.out.println("second:" + second);
                System.out.println("minIndex:" + minIndex);
                System.out.println("arr[minIndex]:" + arr[minIndex]);
                System.out.println("Possible lowest unsorted value");
            }
            //Swap here
            if (arr[arr.length - 1] == arr[j]) {
                arr[0] = second;
                arr[counter] = first;
                counter = 0;
                //minIndex= i+1;
            }
        }
        for (int k = 0; k < arr.length; k++) {
            System.out.print(arr[k] + ", ");
        }
        System.out.println();
    }
}

Answer 1

您犯的第一个错误是在您的嵌套 for 中环形。内部循环的起始索引 ( j ) 应始终从 i + 1 开始(索引器 i 前面的一位)对于外部 for 的每次迭代循环不 j = 1就像你所做的那样。

其次，满足条件 j < arr.length-1您将始终排除数组中的最后一个元素。

更改此:

for(int j = 1; j < arr.length-1; j++)

对此:

for(int j = i + 1; j < arr.length; j++)

继续，您的算法似乎存在几个问题，包括您的 swap功能如此，让我们重新开始。

选择排序是一种基于就地比较的算法，该算法将数组分为两部分，已排序部分位于左端，未排序部分位于右端。最初，已排序部分为空，未排序部分是整个数组。

从未排序的数组中选择最小的元素并与最左边的元素交换，该元素成为排序数组的一部分。此过程继续将未排序的数组边界向右移动一个元素。

考虑到这一点，现在我们可以开始算法了。

public static void selectionSort(int[] arr){
    for(int i = 0; i < arr.length-1; i++){
        int minIndex = i;  // smallest element index
        for(int j = i + 1; j < arr.length; j++){
            if(arr[j] < arr[i]){  // find smallest element
                if(arr[j] < arr[minIndex])
                minIndex = j; // update smallest element index
            }
        }

        if(i != minIndex){  // swap
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
    // print the result
    Arrays.stream(arr).forEach(System.out::println); 
}

作为旁注，选择排序的复杂度为 Ο(N2) ，其中N是数组中元素的数量。