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

Question

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

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

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;
}

Answer 1

merge sort是一种著名的递归算法，您可以从中汲取灵感来执行您自己的递归排序算法:

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++;
        }
    }
}