【剑指offer】快排实现

快速排序算法：

• 实现：先在数组中选择一个数字（默认首位数字），接下来把数组中的数字分为两部分，比选择数字小的移到数组的左边，比选择数字大的移到数组右边。递归进行，知道数组有序。
• 复杂度：平均复杂度O(nlogn) 最坏复杂度O(n^2)，体现在数组基本有序，每次选取最后一个作为比较数字的情况。

代码：

import java.util.Random;

public class Solution {

    public static int Partition1(int[] data, int l, int r) { // 方法1

        int tmp = data[l]; // swap(data[l],data[r])
        data[l] = data[r];
        data[r] = tmp;

        int mid = l - 1;
        for (int index = l; index < r; index++) {
            if (data[index] < data[r]) {
                mid++;
                if (mid != index) {
                    tmp = data[index]; // swap(data[index],data[mid])
                    data[index] = data[mid];
                    data[mid] = tmp;
                }
            }
        }
        mid++;
        tmp = data[mid]; // swap(data[mid],data[r])
        data[mid] = data[r];
        data[r] = tmp;

        return mid;
    }

    public static int Partition2(int[] data, int l, int r) { // 方法2
        int x = data[l];
        while (l < r) {
            while (l < r && data[r] >= x) {
                r--;
            }
            data[l] = data[r];
            while (l < r && data[l] <= x) {
                l++;
            }
            data[r] = data[l];
        }
        data[l] = x;
        return l;
    }


    public static void QuickSort(int[] data, int l, int r) {
        if (l >= r) {
            return;
        }

        int mid = Partition1(data, l, r);
        //int mid = Partition2(data, l, r);
        QuickSort(data, l, mid - 1);
        QuickSort(data, mid + 1, r);
    }

    public static void main(String[] args) {

        int[] data = new int[10];
        Random random = new Random();
        for (int i = 0; i < 10; i++) {
            data[i] = random.nextInt(10);
        }
        System.out.printf("原数组：");
        for (int d : data) {
            System.out.printf("%d ", d);
        }
        QuickSort(data, 0, data.length - 1);
        System.out.println();
        System.out.printf("排序后：");
        for (int d : data) {
            System.out.printf("%d ", d);
        }

    }
}