Java中的随机枢轴快速排序

本文介绍了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];