在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

，你会得到数组排序按递减顺序，或扭转它增加订单。