频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
Java排序算法之快速排序
2017-03-15 09:27:00           
收藏   我要投稿

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;
    }
}
点击复制链接 与好友分享!回本站首页
上一篇:快速排序
下一篇:PAT L2-006 二叉树中序后序构造树
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站