Java 排序算法之快速排序:按照 a[lo] 的值 v 切分,指针 i 和 j 相遇时主循环退出;a[i] 小于 v 时,i+1,a[j] 大于 v 时,j-1。
交换 a[i], a[j] 保证 i 左侧均小于等于 v,j 右侧均大于等于等于 v。当指针相遇时交换 a[lo], a[hi], 切分结束。切分值留在 a[j] 中。
速度快,非稳定排序
时间复杂度是 nlogn,空间复杂度 logn
Java 实现
- public class Sort {
- public static void main(String[] args) {
- int[] arr = {
- 5,
- 1,
- 9,
- 3,
- 7,
- 4,
- 8,
- 6,
- 2
- };
- System.out.println("排序之前:");
- for (int i = 0; i < arr.length; i++) {
- System.out.print(arr[i] + " ");
- }
- sort(arr);
- System.out.println();
- System.out.println("排序之后:");
- for (int i = 0; i < arr.length; i++) {
- System.out.print(arr[i] + " ");
- }
- }
- /** * 快速排序 * @param a */
- public static void sort(int[] a) {
- sort(a, 0, a.length - 1);
- }
- private static void sort(int[] a, int lo, int hi) {
- if (hi <= lo) return;
- int j = partition(a, lo, hi); // 切分,排序的核心 sort(a, lo, j - 1); // 左半部分排序 sort(a, j + 1, hi); // 右半部分排序 } private static int partition(int[] a, int lo, int hi) { int i = lo, j = hi + 1; int v = a[lo]; while (true) { while (a[++i] < v) // 找到左侧大于v的第一个值的下标i if (i == hi) break; while (a[--j] > v) // 找到右侧小于v的第一个值的下标j if (j == lo) break; if (i >= j) // i,j两指针相遇时主循环退出 break; exch(a, i, j); // 交换a[i],a[j] } exch(a, lo, j); // 切分结束,切分值留在a[j] return j; } private static void exch(int[] a, int lo, int hi) { int temp = a[lo]; a[lo] = a[hi]; a[hi] = temp; }}
就爱阅读 www.92to.com 网友整理上传, 为您提供最全的知识大全, 期待您的分享,转载请注明出处。
来源: http://www.92to.com/bangong/2017/04-18/20606884.html