Java中的随机数据集快速排序

可能重复：
使用Java中的随机数据库快速排序

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

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("\nAfter partitionaing"); for (int i = 0; i < list.length; i++) { System.out.print(list[i] + " "); } quickSort(list, 0, list.length - 1); System.out.println("\nAfter Sorting"); for (int i = 0; i  low) { while (low < high && list[low] < pivot) { low++; } while (low = 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); } } } 

Answer 1

您可以使用java中的Random类 ：

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

这将从子数组的开头（begin_sub_array）生成一个值到子数组的结尾（end_sub_array）。 您只需要获取变量num ，并在快速排序算法中作为透视图传递。

 int pivot = list[num]; 

Answer 2

使用int rand = (int) (st + (Math.random()*((end-st)+1))); 以下是代码

 private E[] tofind; private int sameCounter=0; private int comparisions; public void quickSort() { quickInnerSort(0, tofind.length-1); System.out.println("jatin"); } /** * * @param st index of the starting point of the array * @param end index of the ending point of the array * @param k rank of the element to be found out */ private void quickInnerSort(int st, int end) { if(st>end) return; //printWithComparisions(); int cut = partition(st,end); //check k lies in which partition quickInnerSort(st,cut-1); quickInnerSort(cut+1,end); } /** * * @param st index of the array from where to partition * @param end index of the array till where to partition * @return index of the random number chosen to calculate */ private int partition(int st, int end) { int rand = (int) (st + (Math.random()*((end-st)+1))); //System.out.println("rand ="+tofind[rand]+" index at "+rand); E x = tofind[rand]; sameCounter=0; swap(end,rand); E x = tofind[end]; int i = st-1; for(int j=st;j<=end-1;j++) { if(tofind[j].compareTo(x)==0) sameCounter++; if(tofind[j].compareTo(x)<0) { i = i+1; swap(i,j); } } swap(i+1,end); return i+1; } 

Answer 3

尝试这样的事情： –

  int pivot = arr[left + rnd.nextInt(right - left)]; //rnd is a class Random object, which you could set as a private static final field. import java.util.Random; public class QuickSort { /** * @param args */ public static void main(String[] args) { int i; int array[] = {10,9,1,2,3,4,100,200,300,400}; System.out.println(" Quick Sort\n\n"); System.out.println("Values Before the sort:\n"); for(i = 0; i < array.length; i++) System.out.print( array[i]+" "); System.out.println(); quickSort(array,0,array.length-1); System.out.print("Values after the sort:\n"); for(i = 0; i  pivot) j--; if (i <= j) { tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; i++; j--; } }; return i; } public static void quickSort(int arr[], int left, int right) { int index = partition(arr, left, right); if (left < index - 1) quickSort(arr, left, index - 1); if (index < right) quickSort(arr, index, right); } }