import java.util.Random;
public class QuickSort {
// 功能:交换顺序表l中子表left~right的记录,使枢轴记录到位,并返回其所在位
// 置,此时,在它之前(后)的记录均不大(小)于它。
private static int partition(int[] a, int left, int right) {
// 用子表的第一个记录作枢轴记录
int pivot = a[left];
while (left < right) {
// 先从后面开始找小于枢轴的元素
while (left < right && a[right] >= pivot) right --;
if (left < right) a[left++] = a[right];
// 然后再从前面往后找大于枢轴的元素
while (left < right && a[left] <= pivot) left ++;
if (left < right) a[right--] = a[left];
}
a[left] = pivot;
return left;
}
public static void quickSort(int[] a, int left, int right) {
if (a.length == 0) return;
if (left > right) return;
int pivot = partition(a, left, right);
quickSort(a, left, pivot -1);
quickSort(a, pivot + 1, right);
}
public static void main(String[] args) {
// 随机生成10个100以内的数并进行快速排序
int n = 10;
int[] a = new int[n];
Random random = new Random(100);
for (int i = 0; i < n; i++) {
a[i] = (int)(Math.random() * 100);
}
System.out.println("Original numbers: ");
for (int i = 0; i < n; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
quickSort(a, 0, a.length -1);
System.out.println("Sorted numbers: ");
for (int i = 0; i < n; i++) {
System.out.print(a[i] + " ");
}
}
}
网友评论