另一种快速排序
博客专区 > 兔之 的博客 > 博客详情
另一种快速排序
兔之 发表于2年前
另一种快速排序
  • 发表于 2年前
  • 阅读 31
  • 收藏 1
  • 点赞 1
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

之前 http://my.oschina.net/lvyi/blog/324551 写过一种快速排序,下面是另外一种稍微不同的方法。它分别寻找比中心值 k 小和 k 大的两个元素再进行交换,逻辑更加清晰。

public class QuickSort
{
    private static void swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static int partition(int[] a, int lo, int hi)
    {
        int i = lo, j = hi + 1;
        while(true)
        {
            while (a[++i] < a[lo])
                if (i == hi) break;

            while (a[lo] < a[--j])
                if (j == lo) break;

            if (i >= j) break;
            swap(a, i, j);
        }

        swap(a, lo, j);
        return j;
    }

    public static void sort(int[] a)
    {
        // StdRandom.shuffle(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);
    }

    public static void main(String[] argv)
    {
        int[] arr = {6, 7, 9, 0, 5, 1, 8, 12};
        sort(arr, 0, 7);

        for(int i: arr)
            System.out.println(i);
    }
}

参考

https://class.coursera.org/algs4partI-010/lecture/35

共有 人打赏支持
粉丝 67
博文 243
码字总数 95254
作品 7
×
兔之
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: