简明快速排序写法

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

已注册用户请登录

这是一个创建于 1566 天前的主题，其中的信息可能已经有所发展或是发生改变。

快速排序代码有几个坑需要注意：
1，partition 的过程比较复杂，很容易出错，某些行数很短的代码很简洁但是不容易看懂，不如采用简单直观的方法：用第一个元素作为轴、partition 结束之后再把轴 swap 到中间
2，选轴如果固定选第一个，可能进入 worst case，复杂度退化为 N2，使用随机选轴来解决这个问题
3，如果有大量重复元素，快速排序同样会陷入 N2，此时需要使用三向快速排序：将数组分为小于、等于、大于轴的三部分，我们可以通过两步 partition 来完成：首先分为小于等于、大于的两部分，然后再进行一次 partition，拆分成三部分。

package com.mocyx.algs.sort;

import java.util.Random;
import java.util.Scanner;

/**
 * @author Administrator
 */
public class FastSort {
    static int[] arrs;
    static void swap(int a, int b) {
        int v = arrs[a];
        arrs[a] = arrs[b];
        arrs[b] = v;
    }

    static Random random = new Random(System.currentTimeMillis());

    static void choosePovit(int s, int e) {
        int m = s + random.nextInt(e - s);
        swap(s, m);
    }

    /**
     * @param s
     * @param e
     * @param leftEqual true 表示把相等的放在左边，false 表示把相等的放在右边
     * @return
     */
    static int partition(int s, int e, boolean leftEqual) {

        int i = s + 1;
        int j = e;
        int pivotValue = arrs[s];
        while (true) {
            if (leftEqual) {
                while (i <= e && arrs[i] <= pivotValue) {
                    i += 1;
                }
                while (j >= s + 1 && arrs[j] > pivotValue) {
                    j -= 1;
                }
            } else {
                while (i <= e && arrs[i] < pivotValue) {
                    i += 1;
                }
                while (j >= s + 1 && arrs[j] >= pivotValue) {
                    j -= 1;
                }
            }
            if (i <= e && j >= s + 1 && i <= j) {
                swap(i, j);
                i += 1;
                j -= 1;
            }else {
                break;
            }
        }
        swap(s, i - 1);
        return i - 1;
    }

    static void sort(int s, int e, int depth) {
        if (s >= e) {
            return;
        }
        //随机选择轴，避免进入 worst case
        choosePovit(s, e);
        //第一次 partition，小于等于轴的置换到轴右边
        int mr = partition(s, e, true);
        //第二次 partition，把等于轴的置换到右侧
        swap(s, mr);
        int ml = partition(s, mr, false);
        //现在数组分为三块：小于轴 等于轴 大于轴的
        sort(s, ml - 1, depth + 1);
        sort(mr + 1, e, depth + 1);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int c = scanner.nextInt();
        arrs = new int[c];
        for (int i = 0; i < c; i++) {
            arrs[i] = scanner.nextInt();
        }
        sort(0, arrs.length - 1, 1);
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < arrs.length; i++) {
            stringBuilder.append(String.format("%d ", arrs[i]));
        }
        System.out.print(stringBuilder.toString());
    }
}

7 条回复 • 2020-01-06 09:43:18 +08:00