随机快排

import java.util.Random;
public class QuickSort {
    private int[] arr;
    public QuickSort(int[] a) {
        this.arr = a.clone();
    }
    public void sort() {
        _sort(0, arr.length - 1);
    }
    private void _sort(int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = partition(left, right);
        _sort(left, mid - 1);
        _sort(mid + 1, right);
    }
    /**
     * 随机找出一个数mid作为中间值
     * 将arr中下标范围[left, right]内的元素分为两部分
     * 左侧均比不大于mid, 右侧均不小于mid
     *
     * @param left  起始下标
     * @param right 终止下标
     * @return 中间值mid的下标
     */
    private int partition(int left, int right) {
        int index = new Random().nextInt(right - left + 1) + left;
        int temp = arr[index];
        arr[index] = arr[left];
        arr[left] = temp;
        int mid = arr[left];
        while (left < right) {
            while ((left < right) && (arr[right] >= mid)) {
                --right;
            }
            arr[left] = arr[right];
            while ((left < right) && (arr[left] <= mid)) {
                ++left;
            }
            arr[right] = arr[left];
        }
        arr[left] = mid;
        return left;
    }
    public void print() {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        QuickSort q = new QuickSort(new int[]{56, 645, 43, 343, 55, 546, 43, 65, 6, 43, 5, 64, 4, 35, 6});
        q.sort();
        q.print();
    }
}

第k小的数

import java.util.*;
public class Finder {
    private final int SCOPE = 128;
    public int findKth(int[] a, int n, int K) {
        return maxK(a, 0, n - 1, K);
    }
    /**
     * 在数组arr下标范围[left, right]之间找到第k大的数
     *
     * @param arr   数组
     * @param left  起始下标
     * @param right 终止下标
     * @param k     索引值, 从1开始
     * @return
     */
    private int maxK(int[] arr, int left, int right, int k) {
        if (left > right) {
            return -1;
        }
        // 小范围可以不再分治, 直接排序
        if (right - left + 1 <= SCOPE) {
            Arrays.sort(arr, left, right + 1);
            return arr[left + k - 1];
        }
        int mid = partition(arr, left, right);
        int index = mid - left + 1;
        if (index > k) {
            return maxK(arr, left, mid - 1, k);
        } else if (index < k) {
            return maxK(arr, mid + 1, right, k - index);
        }
        return arr[mid];
    }
    /**
     * 随机找出一个数mid作为中间值
     * 将arr中下标范围[left, right]内的元素分为两部分
     * 左侧均比不大于mid, 右侧均不小于mid
     *
     * @param arr   数组
     * @param left  起始下标
     * @param right 终止下标
     * @return 中间值mid的下标
     */
    private int partition(int[] arr, int left, int right) {
        int index = new Random().nextInt(right - left + 1) + left;
        int temp = arr[index];
        arr[index] = arr[left];
        arr[left] = temp;
        int mid = arr[left];
        while (left < right) {
            while ((left < right) && (arr[right] <= mid)) {
                --right;
            }
            arr[left] = arr[right];
            while ((left < right) && (arr[left] >= mid)) {
                ++left;
            }
            arr[right] = arr[left];
        }
        arr[left] = mid;
        return left;
    }
    public static void main(String[] args) {
        Finder finder = new Finder();
        System.out.println(finder.findKth(new int[]{3, 4, 5, 6, 2, 1, 7, 8, 9}, 9, 2));
    }
}

相关题目