L'écriture d'un récursif algorithme de tri d'un tableau d'entiers

Je suis en train d'écrire un récursif algorithme de tri d'un tableau d'entiers. Les codes suivants s'imprime dans la console: 3, 5, 2, 1, 1, 2, 6, 7, 8, 10, 20

La sortie doit être triés, mais en quelque sorte "ça ne fonctionne pas".

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;
}
Et la question est...?
Ce n'est pas de tri le tableau de la plus petite à la plus grande

OriginalL'auteur Q Liu | 2012-11-19

  1. 2

    La fusion de tri est un bien connu algorithme récursif que vous pouvez prendre des idées de faire votre propre récursif algorithme de tri:

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

    OriginalL'auteur dreamcrash

  2. 1

    Vous avez besoin de se rappeler lors de l'initialisation des variables dans votre méthode récursive que vous travaillez sur le startIndex par stopIndex tranche de la matrice, et non pas l'ensemble du tableau, et vous ne devriez pas toucher quoi que ce soit en dehors de cette tranche.

    Prendre un autre regard sur l'initialisation de l'indice, minimumIndex, et maximumIndex dans votre duplexSelectionSort méthode.

    OriginalL'auteur Patricia Shanahan

  3. 0

    C'est un type de récursive de tri que j'ai essayé. Espérons que cette aide.
    Sur les mêmes lignes de code, mais je me sens un peu moins compliqué.

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

    OriginalL'auteur Deepak

  4. 0

    Vous pouvez également utiliser la sélection de la méthode de tri.

    Il est bon algorithme à appliquer récursive 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);
}
}

    OriginalL'auteur Donggun Jung

  5. -2

    Pour trier un tableau de la plus petite à la plus grande, ce faire:

    Arrays.sort(array);
    Il semble que son objectif est plus d'écrire une sorte lui-même, plutôt que de simplement à l'aide de pré-faites la code.

    OriginalL'auteur Bohemian