由快速排序到分治思想

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

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

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 条评论
登录 后参与评论

相关文章

来自专栏小詹同学

Leetcode打卡 | No.014 最长公共前缀

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

862
来自专栏移动端开发

swift 可选类型笔记

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

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

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

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

1173
来自专栏陈树义

如何快速学好Shell脚本?

943
来自专栏老马说编程

(19) 接口的本质 / 计算机程序的思维逻辑

数据类型的局限 之前我们一直在说,程序主要就是数据以及对数据的操作,而为了方便操作数据,高级语言引入了数据类型的概念,Java定义了八种基本数据类型,而类相当...

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

zephir-(10)内置函数

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

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

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

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

3448
来自专栏CaiRui

Python之‘数据结构’

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

1838
来自专栏java一日一条

Java中有关Null的9件事

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

582
来自专栏C语言及其他语言

C语言的数据类型

变量与常量数据 在程序的世界中,可以让计算机按照指令做很多事情,如进行数值计算、图像显示、语音对话、视频播放、天文计算、发送邮件、游戏绘图以及任何我们可以想...

3885

扫码关注云+社区