快速排序

核心是partition,然后递归

import java.util.*;

public class QuickSort {

    // 我们的算法类不允许产生任何实例
    private QuickSort(){}

    // 对arr[l...r]部分进行partition操作
    // 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
    private static int partition(Comparable[] arr, int l, int r){

        Comparable v = arr[l];

        int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v
        for( int i = l + 1 ; i <= r ; i ++ )
            if( arr[i].compareTo(v) < 0 ){
                j ++;
                swap(arr, j, i);
            }

        swap(arr, l, j);

        return j;
    }

    // 递归使用快速排序,对arr[l...r]的范围进行排序
    private static void sort(Comparable[] arr, int l, int r){

        if( l >= r )
            return;

        int p = partition(arr, l, r);
        sort(arr, l, p-1 );
        sort(arr, p+1, r);
    }

    public static void sort(Comparable[] arr){

        int n = arr.length;
        sort(arr, 0, n-1);
    }

    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

原文链接:https://github.com/liuyubobobo

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 冒泡排序

    用户6404053
  • 归并排序

    复制一个同样的数组aux,3个索引,蓝色剪头为最终的数组中需要跟踪的索引位置,两个红色剪头是已经分别排序好的两个数组当前要考虑的元素

    用户6404053
  • Java8中的接口和抽象类的区别

    今天跑了好远去面试,面试官问了上面这个问题,我是一脸懵比,抽象类我自己没写过,JAVA8对接口有什么修改完全没印象,现在来总结一下,至少下次再遇到这个问题要答上...

    用户6404053
  • JavaScript数组排序总结

    将数组中的相邻两个元素进行比较,将比较大(较小)的数通过两两比较移动到数组末尾(开始),执行一遍内层循环,确定一个最大(最小)的数,外层循环从数组末尾(开始)遍...

    用户4831957
  • 浙大版《C语言程序设计(第3版)》题目集 习题9-5 通讯录排序

    输入n个朋友的信息,包括姓名、生日、电话号码,本题要求编写程序,按照年龄从大到小的顺序依次输出通讯录。题目保证所有人的生日均不相同。

    C you again 的博客
  • PHP四种排序算法(选择排序)

    阿沐
  • PHP四种排序算法(插入排序)

    阿沐
  • 多图养眼!Partition,荷兰国旗问题与随机快排

    Partition的过程:给定一个数组arr,和一个整数num。把小于等于num的数放在数组的左边,大于num的数放在数组的右边。

    行百里er
  • OJ刷题记录:L1-206-学霸递情书(15分)

    题目要求: 李雷和韩梅梅坐前后排。上课想说话怕老师发现,所以改为传小纸条。为了被老师发现他们纸条上说的是啥,他们约定了如下方法传递信息: 将26个英文字母(...

    英雄爱吃土豆片
  • 快速排序

    参考:http://www.cnblogs.com/skywang12345/p/3596746.html  下面上代码: #include<iostream>...

    xcywt

扫码关注云+社区

领取腾讯云代金券