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; 
     //int[] sorted = Arrays.copyOf(arr, arr.length); // Copies unsorted array to new array 
     //Arrays.sort(sorted); // sorts unsorted array for compairison later on 
     for(int i = 0; i < arr.length-1; i++) // comparing the first index value to the rest of the values in the array 
     { 
      int minIndex = i; 

      for(int j = 1; j < arr.length-1; j++) // representing the next index value to the original and comparing it 
      { 
       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是阵列中的元素的数量。