在findMin方法的幫助下創建選擇排序方法

Question

我的任務是創建一個由findMin方法協助的選擇排序方法（按升序排列元素）。

我的問題在於，我不確定我應該在選擇排序方法中將findMin方法稱爲哪裏。此外，我懷疑我是否根據評論中的要求正確執行了findMin方法。

public class idk{ 

    // find the minimun valued element 
    // range [start, ar.length - 1] 
    // int indexOfMin= -1; this is incorrect!!! 

    // return indexOfMin; 
    public static int findMin(int [] ar, int start) 
    { 
     int minValue = ar[0]; 
     for (int i = start; i < ar.length; i++) { 
      if (ar[i] < minValue) 
       minValue = ar[i]; 

     } 

     return minValue; 
    } 
    public static void swap(int[] list, int a , int b){ 

     int temp = list[a]; 
     list[a] = list[b]; 
     list[b] = temp; 
    } 
    // 1) make a new array, copy the values from arr 
    // into it and THEN sort res 
    // 2) implement and use in this method 
    // the findMin helper method defined above 

    public static int [] selSort(int[] arr) 
    { 
     int [] res= new int[arr.length]; 
     for (int i = 0; i < arr.length; i++) 
      res[i] = arr[i]; 

     int min = res.length; 
     for (int x =0; x < res.length; x++){ 
      min = x; 
      for (int y = x + 1; y < res.length;y++){ 
       if (res[y] < res[min]) 
        min = y; 
      } 

      swap (res,x, min);   
     } 
     return res; 

    } 

} 

Answer 1

試試這個算法：

1. 將您的陣列到最小堆。
2. 現在，min-heap的最頂層元素是數組中最小的元素。
3. 通過調用findMin（）方法獲取此元素，並將該元素與數組的最後一個元素交換，然後減小最小堆的大小。
4. 堆你最小的堆。這種方法
5. 重複步驟1至4直到堆大小> 1

，你會得到數組排序按遞減順序，或扭轉它增加訂單。