Java中的随机枢轴快速排序 [英] Random pivot quicksort in Java

问题描述

可能重复:
在Java中使用随机枢轴进行快速排序

下面编写的快速排序代码使用数组的第一个元素作为枢轴，然后对数组进行排序.现在我想随机选择枢轴而不是第一个，然后对数组进行排序，我卡住了，请告诉我我可以在下面的代码中进行哪些更改以获得完美的结果.

The below written code of the Quicksort uses the first element of the array as the pivot and then sorts the array. Now I want to randomly pick up the pivot instead of first one and then sort the array and I am stuck please tell me what changes I can make in the below code to get the perfect results.

import java.util.*;
import javax.swing.JOptionPane;

public class Quicksort {

public static void main(String[] args) {
    String arraylength = JOptionPane.showInputDialog("Enter the length of the array.");

    int a = Integer.parseInt(arraylength);
    if (a == 0) {
        System.out.println("Null Length");
    } else {
        int[] list = new int[a];


        for (int i = 0; i < a; i++) {
            String input = JOptionPane.showInputDialog("Input the number.");
            int c = Integer.parseInt(input);
            list[i] = c;
        }

        System.out.println("Before");
        for (int i = 0; i < list.length; i++) {
            System.out.print(list[i] + " ");
        }
        partition(list, 0, list.length - 1);


        System.out.println("
After partitionaing");
        for (int i = 0; i < list.length; i++) {
            System.out.print(list[i] + " ");
        }
        quickSort(list, 0, list.length - 1);

        System.out.println("
After Sorting");
        for (int i = 0; i < list.length; i++) {
            System.out.print(list[i] + " ");
        }
    }
}

private static int partition(int[] list, int first, int last) {
    int pivot = list[first];
    int low = first + 1;
    int high = last;

    while (high > low) {

        while (low < high && list[low] < pivot) {
            low++;
        }


        while (low < high && list[high] >= pivot) {
            high--;
        }


        if (high > low) {
            int temp = list[high];
            list[high] = list[low];
            list[low] = temp;
        }
    }
    while (high > first && list[high] >= pivot) {
        high--;
    }

    if (pivot > list[high]) {
        list[first] = list[high];
        list[high] = pivot;
        return high;
    } else {
        return first;
    }

}

private static void quickSort(int[] list, int first, int last) {
    if (last > first) {
        int pivotIndex = partition(list, first, last);
        quickSort(list, first, pivotIndex - 1);
        quickSort(list, pivotIndex + 1, last);
    }
}
}

推荐答案

你可以使用随机类来自java:

You can use the Random class from java:

Random rand = new Random();
int num = begin_sub_array + rand.nextInt(end_sub_array - begin_sub_array);

这将生成一个从子数组开头 (begin_sub_array) 到子数组结尾 (end_sub_array) 的值.您只需要获取变量 num，并将其作为快速排序算法中的枢轴传递.

This will generate a value from beginning of the sub array (begin_sub_array) to end of the sub array (end_sub_array). You just have to take the variable num, and pass as the pivot in your quicksort algorithm.

int pivot = list[num];

这篇关于Java中的随机枢轴快速排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！