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

选择排序的算法如下所示：

public static void selectionSort(int[] arr) {
    // iterate over all subsets of the array
    // (0-last, 1-last, 2-last, 3-last, ...)
    for (int i = 0; i < arr.length; i++) {
        // assume the min is
        // the first element
        int min = arr[i];
        // index of the
        // min element
        int min_i = i;
        // check the elements
        // after i to find
        // the smallest
        for (int j = i + 1; j < arr.length; j++) {
            // if this element
            // is less, then it
            // is the new min
            if (arr[j] < min) {
                min = arr[j];
                min_i = j;
            }
        }
        // if min element is not
        // equal to the current
        // one, then swap them
        if (i != min_i) {
            int temp = arr[i];
            arr[i] = arr[min_i];
            arr[min_i] = temp;
        }
    }
}

public static void main(String[] args) {
    int[] arr = {5, 34, 1, 15, 3, 8, 9, 2, 7, 6, 43, 4};
    selectionSort(arr);
    System.out.println(Arrays.toString(arr));
    // [1, 2, 3, 4, 5, 6, 7, 8, 9, 15, 34, 43]
}

Answer 2

您犯的第一个错误是在嵌套的for循环中。内部循环的起始索引（j）应始终从i 1开始（索引器i之前的一个位置），对于外部循环的每次迭代，而不是像您所做的那样，j=1。

其次，通过条件j

更改此：

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

对此：

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

接下来，您的算法似乎存在一些问题，包括您的交换功能，因此，让我们重新开始。

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

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

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

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是数组内的元素数。