java 编写整数数组的递归排序算法

Writing a recursive sorting algorithm of an array of integers

提问by Q Zhao-Liu

I am trying to write a recursive sorting algorithm for an array of integers. The following codes prints to the console: 3, 5, 2, 1, 1, 2, 6, 7, 8, 10, 20

我正在尝试为整数数组编写递归排序算法。以下代码打印到控制台：3, 5, 2, 1, 1, 2, 6, 7, 8, 10, 20

The output should be sorted but somehow "it doesn't work".

输出应该被排序，但不知何故“它不起作用”。

public static void main(String[] args)
{
    int[] unsortedList = {20, 3, 1, 2, 1, 2, 6, 8, 10, 5, 7};
    duplexSelectionSort(unsortedList, 0, unsortedList.length-1);

    for (int i = 0; i < unsortedList.length; i++)
    {
        System.out.println(unsortedList[i]);
    }
}


public static void duplexSelectionSort(
    int[] unsortedNumbers,
    int startIndex,
    int stopIndex)
{
    int minimumIndex = 0;
    int maximumIndex = 0;

    if (startIndex < stopIndex)
    {
        int index = 0;
        while (index <= stopIndex)
        {
            if (unsortedNumbers[index] < unsortedNumbers[minimumIndex])
            {
                minimumIndex = index;
            }
            if (unsortedNumbers[index] > unsortedNumbers[maximumIndex])
            {
                maximumIndex = index;
            }
            index++;
        }
        swapEdges(unsortedNumbers, startIndex, stopIndex, minimumIndex, maximumIndex);
        duplexSelectionSort(unsortedNumbers, startIndex + 1, stopIndex - 1);
    }
}


public static void swapEdges(
    int[] listOfIntegers,
    int startIndex,
    int stopIndex,
    int minimumIndex,
    int maximumIndex)
{
    if ((minimumIndex == stopIndex) && (maximumIndex == startIndex))
    {
        swap(listOfIntegers, startIndex, stopIndex);
    }
    else
    {
        if (maximumIndex == startIndex)
        {
            swap(listOfIntegers, maximumIndex, stopIndex);
            swap(listOfIntegers, minimumIndex, startIndex);
        }
        else
        {
            swap(listOfIntegers, minimumIndex, startIndex);
            swap(listOfIntegers, maximumIndex, stopIndex);
        }
    }
}

public static void swap(int[] listOfIntegers,
    int index1,
    int index2)
{
    int savedElementAtIndex1 = listOfIntegers[index1];
    listOfIntegers[index1] = listOfIntegers[index2];
    listOfIntegers[index2] = savedElementAtIndex1;
}

采纳答案by dreamcrash

The merge sortis an well-known recursive algorithm that you can take ideas from to do your own recursive sort algorithm:

该合并排序是一个众所周知的递归算法，您可以采取的想法从做自己的递归排序算法：

public void mergeSort(int[] data) {
    if(data.length <= 1) return;               // Base case: just 1 elt

    int[] a = new int[data.length / 2];        // Split array into two
    int[] b = new int[data.length - a.length]; //   halves, a and b
    for(int i = 0; i < data.length; i++) {
        if(i < a.length) a[i] = data[i];
        else             b[i - a.length] = data[i];
    }

    mergeSort(a);                              // Recursively sort first
    mergeSort(b);                              //   and second half.

    int ai = 0;                                // Merge halves: ai, bi
    int bi = 0;                                //   track position in
    while(ai + bi < data.length) {             //   in each half.
        if(bi >= b.length || (ai < a.length && a[ai] < b[bi])) {
            data[ai + bi] = a[ai]; // (copy element of first array over)
            ai++;
        } else {
            data[ai + bi] = b[bi]; // (copy element of second array over)
            bi++;
        }
    }
}

回答by Patricia Shanahan

You need to remember when initializing variables in your recursive method that you are working on the startIndex through stopIndex slice of the array, not the whole array, and you should not be touching anything outside that slice.

您需要记住在递归方法中初始化变量时，您正在处理 startIndex 到数组的 stopIndex 切片，而不是整个数组，并且您不应该触及该切片之外的任何内容。

Take another look at the initialization of index, minimumIndex, and maximumIndex in your duplexSelectionSort method.

再看一下 duplexSelectionSort 方法中 index、minimumIndex 和 maximumIndex 的初始化。

回答by Deepak

This is one type of recursive sorting that I tried. Hope this helps. On similar lines to your code, but I feel a bit less complicated.

这是我尝试过的一种递归排序。希望这可以帮助。与您的代码类似，但我觉得不那么复杂。

public static void main(String[] args)
{
int [] array = {5,9,2,3,10,20,1,7};
int len = array.length-1;
sort(array, 0, len);
for(int i=0;i<=len;i++)
{
  System.out.println(array[i]);
}
}

public static void sort(int[] array, int start, int end)
{
if (start < end)
{
  sort(array, start+1, end);
  if(array[start]<=array[end])
  {
    sort(array, start, end-1);
  }
  else if(array[start]>array[end])
  {
    int temp = array[start];
    array[start] = array[end];
    array[end] = temp;
    sort(array, start, end-1);
  }
}
else if(start == end)
  return;
}

回答by Donggun Jung

You can also use selection sort method.

您也可以使用选择排序方法。

It is good algorithm to apply recursive style.

应用递归风格是一种很好的算法。

public static int FindMinIndex(int[] data, int x, int y){

    int mini;

    if(x==y){
        mini=x;
    }

    else{
        int tempmini=FindMinIndex(data, x+1, y);
        if (data[tempmini]<data[x]){
            mini=tempmini;
        }
        else{
            mini=x;
        }
    }
    return mini;
}

//Do selection sort between data[x]~data[y]
public static void SelectionSort(int[] data, int x, int y){

    if (x==y){
        return;
    }

    else{
        int index=FindMinIndex(data, x, y);

        int temp=data[index];
        data[index]=data[x];
        data[x]=temp;

        SelectionSort(data,x+1,y);
    }

}

回答by Bohemian

To sort an array from smallest the largest, do this:

要从最小到最大对数组进行排序，请执行以下操作：

Arrays.sort(array);