快速排序Java源代码

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] + " ");
        }
    }


}