由快速排序到分治思想

算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第一篇《由快速排序到分治思想》,非常赞!希望对大家有帮助,大家会喜欢!

快速排序是一种基于分治思想的排序算法 它主要分为以下几步

1、一个数组按切分元素分成两个数组,一个数组是大于切分元素的,另一个数组是小于切分元素的,

2、然后将这两个部分按上面的思路独立排序。

3、并将有序的子数组归并 得到一个完整的数组。

这中间的关键就在于切分。

代码实现

public class Quick {
       private static void sort(Comparable[] a, int l0, int l1) {
              // TODO Auto-generated method stub
              if(l0 > l1) return;   //做基本的判断
              int l2=partition(a,l0,l1);  //调用方法实现按切分 得到最终a所在位置
              sort(a,l0,l2-1);   //排序比a小的数组
              sort(a,l2+1,l1);   //排序比a大的数组
       }
       private static int partition(Comparable[] a, int l0, int l1) {  //定义切分方法
              int i=l0;   int j=l1+1; //定义左右指针
              Comparable  v=a[0];  //获得切分元素
              while(true){   扫描左右
                     while(less(a[++i],v))  if(i==l1)  break;
//调用 less方法做判断a[i] 和v 直到a[i]大于v时 或者 i 到数组末尾时才停止
                     while(less(v,a[j--])) if(j==l0)  break;
//调用 less方法做判断a[j] 和v 直到a[j]小于v时 或者 i 到数组头时才停止
                     if(i>j)  break;   //做判断  如果作为切分调出循环
                     exch(a,i,j);   调用exch()方法来吧a[i]和a[j] 交换位置
              }
              exch(a,l0,j);   //调用exch()方法 将v放入正确的位置
              return j;
       }
}

快速排序的特性

复杂度 NlgN 空间复杂度 lgN 其运行效率与切分元素值有关 一把在排序之前先随机整个数组。 快速排序也是最快的通用排序算法。

分治思想理念

分治,字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题。所以他有三个要点

1、划分步:把输入的问题划分为k个子问题,并尽量使这k个子问题的规模大致相同

2、治理步:调用处理方法来处理问题。

3、组合步:组合步把各个子问题的解组合起来。

从快速排序到分治

在快速排序中将一个数组按切分元素分成两个数组就是在不同的划分步。然后将这两个部分按上面的思路独立排序 这就是治理步。 最后将所有的子数组归并到一个数组 就是组合步。

原文发布于微信公众号 - 大数据和云计算技术(jiezhu2007)

原文发表时间:2018-01-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏MyBlog

Effective.Java 读书笔记(8)关于equals方法

重写equals看上去十分简单对吧,但是我觉得很多时候重写equals可能会招致一些问题,这些问题有时可能会特别严重,当然了不重写不就完事了吗?但是这只适用于那...

924
来自专栏Java学习网

Java中有关Null的9问题

Java中有关Null的9问题 对于Java程序员来说,null是令人头痛的东西。时常会受到空指针异常(NPE)的骚扰。连Java的发明者都承认...

2315
来自专栏移动端开发

swift 可选类型笔记

       晚上十一点半了,看书累了,原本想睡了的,想了想,还是把刚看的总结一下,把这篇笔记写了吧。广州下雨,真特么的冷。。好了,废话不说了,说正题说说Swi...

19610
来自专栏程序员互动联盟

【面试宝典】写一个函数将两个数交换

没有参加过面试的同学可能会很忐忑,面试都会出些什么题呢?其实一般情况下,大部分的面试题都是比较基础的。关于如何交换两个数字,应该是非常简单的问题了。看下面几个函...

3548
来自专栏信数据得永生

JavaScript 编程精解 中文第三版 三、函数

3347
来自专栏黑泽君的专栏

Java中方法重写的应用

  当子类需要父类的功能,而功能的主体子类还有自己特有的内容时,可以重写父类中的方法,这样,即沿袭了父类的功能,又定义了子类自己特有的内容。

2092
来自专栏CaiRui

Python之‘数据结构’

简介 数据结构基本上就是--它们是可以处理一些数据的结构。或者说,它们是用来存储一组相关数据的。在Python里面有三种内建的数据结构--列表、元组和字典。 一...

2078
来自专栏微信公众号:Java团长

Java提高篇——对象克隆(复制)

不仅仅是int类型,其它七种原始数据类型(boolean,char,byte,short,float,double.long)同样适用于该类情况。

1433
来自专栏喵了个咪的博客空间

zephir-(10)内置函数

#zephir-内置函数# ? ##前言## 先在这里感谢各位zephir开源技术提供者 嗨!大家好呀,今天要和大家一同学习zephir的内置函数,学过PHP的...

3708
来自专栏java一日一条

Java中有关Null的9件事

对于Java程序员来说,null是令人头痛的东西。时常会受到空指针异常(NPE)的骚扰。连Java的发明者都承认这是他的一项巨大失误。Java为 什么要保留nu...

972

扫码关注云+社区

领取腾讯云代金券