一種算法，其中找到最小值和最大值元素值，然後在刪除這些元素後再次執行它

Question

我有找到最小值和最大值的方法，也可以將它們放在需要的位置。我也有一個方法來調用這些方法，並縮小到一個子數組。問題是，即使它正在排序，一旦移入子數組，我無法打印數組。請幫忙，這裏有一個更好的方法，我現在已經把我的頭撞到了牆上。

package mySort; 
import java.util.Arrays; 
public class MyAlg { 
    public static int findSmall(int[] input){ 
     int sm = input[0]; 
     for(int i = 0; i <= input.length - 1; i++){ 
      if(sm < input[i]) 
       sm = input[i]; 
     } 
     input[0] = sm; 
     return sm; 
    } 
    public static int findLarge(int[] input){ 
     int lg = input[input.length -1]; 
     for(int i = 0; i <= input.length - 1; i++){ 
      if(input[i] > lg) 
       lg = input[i]; 
     } 
     input[input.length -1] = lg; 
     return lg; 
    } 
    public static int[] sort(int[] input){ 
     findSmall(input); 
     findLarge(input); 
     for(int i = 0; i<= (input.length - 1)/2; i++){ 
      int[] tmp = Arrays.copyOfRange(input, i + 1, input.length - 2); 
      findSmall(tmp); 
      findLarge(tmp); 
     } 
    } 
} 

Answer 1

我不知道，如果你需要使用一個數組或沒有，但如果你可以隨意使用任何數據結構，你想我會建議TreeSet。這個數據結構實現了SortedSet，這意味着在添加對象時，它們已經爲你排序。然後你可以使用的方法，如

• 第一（） - 返回最低值
• 最後（） - 返回最高值

然後，你可以刪除這些最高和最低的元素或使用

• 天花板後，這些方法（INT） - 最高數量超過給定的int
• 地板下邊（INT） - 最小號高個給定int

如果您需要更多幫助或只需要數組的實現，則需要Lmk。

Answer 2

不幸的是你的代碼是相當有缺陷的，所以我只是重寫了一切。下面的代碼將通過將最小的int放置在新數組的最左邊未填充位置的輸入數組中，並將最大值放置在新數組的最右邊未填充的位置，直到新數組被排序輸入數組的版本。享受

private static int[] sort(int[] input) { 

    //create an empty array the same size as input 
    int[] sorted = new int[input.length]; 

    //create another empty array the same size as input 
    int[] temp = new int[input.length]; 

    // copy input into temp 
    for (int i = 0; i <= (input.length - 1); i++) { 
     temp[i] = input[i]; 
    } 

    //create variables to tell where to put big and small 
    //in the sorted array 
    int leftIndex = 0; 
    int rightIndex = sorted.length - 1; 

    //create variables to hold the biggest and smallest values in 
    //input. For now we'll give them the values of the first element 
    //in input, they'll change 
    int big = input[0]; 
    int small = input[0]; 

    // sort 

    //sort the array as you described 
    while (temp.length != 0) { 
     //find the biggest and smallest value in temp 
     big = findBig(temp); 
     small = findSmall(temp); 

     //place the biggest at the end of the sorted array 
     //and place the smallest at the beginning of the sorted array 
     sorted[leftIndex] = small; 
     sorted[rightIndex] = big; 

     //move the left index of the sorted array up, so we don't over write 
     //the element we put in on the next iteration, same for the right index to, 
     //but down 
     leftIndex++; 
     rightIndex--; 

     if(temp.length != 1){ 
     //remove the biggest and smallest values from the temp array 
     temp = removeElement(temp, big); 
     temp = removeElement(temp, small); 
     }else{ 
      //only remove one element in the event the array size is odd 
      //also not at this point leftIndex == rightIndex as it will be the last 
      //element 
      temp = removeElement(temp, big); 
     } 

     //repeat, until the temp array is empty 

    } 

    // print out the content of the sorted array 
    for (int i = 0; i <= (sorted.length - 1); i++) { 
     System.out.println("Index " + i + ": " + sorted[i]); 
    } 

    //return the sorted array 
    return sorted; 
} 

//find the smallest number in an int array and return it's value 
private static int findSmall(int[] input) { 

    int smallest = input[0]; 

    for (int i = 0; i <= (input.length - 1); i++) { 
     if (smallest > input[i]) { 
      smallest = input[i]; 
     } 
    } 
    return smallest; 
} 

//find the biggest value in an int array and return it's value 
private static int findBig(int[] input) { 

    int biggest = input[0]; 

    for (int i = 0; i <= (input.length - 1); i++) { 
     if (biggest < input[i]) { 
      biggest = input[i]; 
     } 
    } 
    return biggest; 
} 

//remove an element from an int array, based on it's value 
private static int[] removeElement(int[] input, int elementValue) { 

    //create a temp array of size input - 1, because there will be one less element 
    int[] temp = new int[input.length - 1]; 

    //create variable to tell which index to remove, set to 0 to start 
    //will change unless it is right 
    int indexToRemove = 0; 

    //find out what the index of the element you want to remove is 
    for (int i = 0; i <= (input.length - 1); i++) { 
     if (input[i] == elementValue) { 
      //assign the value to 
      indexToRemove = i; 
      break; 
     } 
    } 

    //variable that says if we've hit the index we want to remove 
    boolean removeFound = false; 

    for (int i = 0; i <= (input.length - 1); i++) { 

     //check if we are at the index we want to remove 
     if (indexToRemove == i) { 
      //if we are say so 
      removeFound = true; 
     } 

     //done if we aren't at the index we want to remove 
     if (i != indexToRemove && removeFound == false) { 
      //copy input to temp as normal 
      temp[i] = input[i]; 
     } 

     //done if we've hit the index we want to remove 
     if (i != indexToRemove && removeFound == true) { 
      //note the -1, as we've skipped one and need the to decrement 
      //note input isn't decremented, as we need the value as normal 
      //note we skipped the element we wanted to delete 
      temp[i - 1] = input[i]; 
     } 

    } 

    //return the modified array that doesn't contain the element we removed 
    //and it is 1 index smaller than the input array 
    return temp; 
} 

} 

而且，我把所有的這些方法分爲一類排序，但我寫它以這種方式來模仿你寫你的代碼在一定程度上的方式。這將需要你創建一個getSorted方法，並且如果它被放置在類Sort中，我也會將sort方法更改爲構造方法。

Answer 3

我寫了一個算法來解決你的這個問題。使用分治我們可以有效地解決這個問題。將每個值與每個值進行比較，可以找到最小值和最大值。在關閉第一個（最小）和最後一個（最大）值之後，將使用相同的算法處理新的未排序數組，以找到最小值和最大值。

你可以看到我在[GitHub的]算法（https://github.com/jabedhossain/SortingProblem/）

雖然它用C++寫的，註釋應該足以通過帶領你。