使用递归方法对数组进行排序

Question

我正在尝试编写一个程序，其中用户将输入 6 个字符串，然后它将使用递归方法按逆字母顺序对数组进行排序。尽管有多个视频、阅读和尝试，但这是我不理解的一个概念。非常感谢任何支持和见解。谢谢你。import java.util.Arrays;import java.util.Scanner;public class SRecusion {    public static void sort2 (String[] sort2) {        int i;        int min = 0;        int max;        for (i = 0; i <sort2.length -1; i++) {            if (sort2[i].charAt(0)> sort2[i=1].charAt(0)) {                sort2[i] = sort2[min];            }            else {                min = (sort2(sort2[i-1]));            }        }    }    public static void main(String[] args) {        // TODO Auto-generated method stub        String [] test = new String[6];        Scanner scnr = new Scanner(System.in);        String userEntry = "";        for(int i = 0; i <= test.length - 1; i++) {            System.out.println("Please enter a word:");            test[i] = scnr.nextLine();        }        sort2(test);            System.out.println("your list is" + Arrays.asList(test));            System.out.println();        }}

Answer 1

排序是一个非常广泛的主题，因为有许多不同的排序方法（快速排序、归并排序等）。但是，冒泡排序是一个非常基本且简单的排序方法。虽然它不是最快的，但使用递归很容易理解和编码。

本质上，冒泡排序会迭代成对 2 的元素，如果两个元素的顺序错误，则交换它们。

例如，让我们使用冒泡排序对 (3, 2, 5, 4, 1) 进行排序。

( 2, 3 , 5, 4, 1) 首先，它会查看前两个元素是否需要交换它们。由于 3 大于 2，它会交换它们。

(2, 3, 5 , 4, 1) 接下来看 3 和 5。因为 3 小于 5，所以不需要交换

(2, 3, 4, 5 , 1) 现在查看 5 和 4 并交换它们。

(2, 3, 4, 1, 5 ) 最后，它查看 5 和 1 并将它们交换。

现在从头开始，重复整个过程。如果在迭代期间恰好进行了 0 次交换，则排序结束。

如果您仍然有点困惑，请尝试观看有关冒泡排序的教程或访问此链接。

Answer 2

所以从我上面问的为什么你需要递归排序算法这里我将尝试解释递归排序是如何工作的。我花了一些时间才弄明白，因为我相信大多数第一次接触它的人都会这样做。

public static void Qsort(int[] array, int start, int end)

{

    //find the current center of the whole or parital array part I am working on.

    int center = (start+end)/2;

    ///System.out.println("\n This is the center : " + center);

    int pivot, i, pivotplace;

    i = 0;

    pivot = 0;

    pivotplace = 0;

    //if start = end then we are at a single element.  just return to the previous iterative call.

    if(start == end)

    {

       // System.out.println("\n Inside base case return :");

        return;

    }

    //find the pivot value we are using.  using a 3 prong selection we are assured to at least get some type of median value and avoid the N^2 worst case.

    pivot = getpivot(array[start], array[center], array[end]); //gets median value of start, center and end values in the array.

   // System.out.println("\n pivotvalue is  : " + pivot);

    //find where the current pivot is located and swap it with the last element in the current portion of the array.

    if(array[start] == pivot)

    {

        //System.out.print("\n Inside pivot at start");

        swap(array, start, end);

    }

    else

    {

        if(array[center] == pivot)

        {

            //System.out.print("\n Inside pivot at center");

            swap(array, center, end);

        }

    }

    //due to iteration the pivot place needs to start at the passed in value of 'start' and not 0.

    pivotplace = start;

    //due to iteration the loop needs to go from the passed in value of start and not 0 and needs to go 

    //until it reaches the end value passed in.

    for(i = start; i < end; i++)

    {

        //if the current slot of the array is less than then pivot swap it with the current pivotplace holder

        //since the pivotplace keeps getting iterated up be each swap the final place of pivot place

        //is where the pivot will actually be swapped back to after the loop cpompletes.

        if(array[i] < pivot)

        {

            //System.out.print("\n Swapping");

            swap(array, i, pivotplace);

            pivotplace++;

        }

    }

    //loop is finished, swap the pivot into the spot it belongs in.

    swap(array, pivotplace, end);

//there are 2 cases for recursive iteration.

//The first is from the start to the slot before the pivot

if(start < pivotplace){Qsort(array, start, pivotplace-1);}

//the second is from the slot after the pivot to the end.

if(pivotplace+1 < end){Qsort(array, pivotplace+1, end);}

}

public static int getpivot(int a, int b, int c)

{

    if((a > b)  && (a < c))

    {

        return a;

    }

    if((b > a)  && (b < c))

    {

        return b;

    }

    return c;

}

public static void swap(int[] array, int posa, int posb)

{

    int temp;

    temp = array[posa];

    array[posa] = array[posb];

    array[posb] = temp;

}

这是我在编程课程中编写的基本快速排序或递归排序。在处理一小组字符串时，您可能不需要使用 getpivot 代码，但是如果您进行一些研究，您会发现使用可能的 3 个样本大大加快了递归速度，因为递归树的工作负载均衡.