由快速排序到分治思想

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

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

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

相关文章

来自专栏CDA数据分析师

Python面试中8个必考问题

1、下面这段代码的输出结果是什么?请解释。 ? 怎样修改extendList的定义能够产生以下预期的行为? 上面代码输出结果将是: ? 很多人都会误认为list...

17810
来自专栏测试开发架构之路

总结了一些指针易出错的常见问题(二)

4.指针与数组    一些常见的错误观点是数组和指针是完全可以互换的。尽管数组名字有时候可以当指针来使用,但是数组的名字不是指针。 数组是能用索引访问的同质元...

3317
来自专栏Crossin的编程教室

【Python 第52课】 元组

上一次pygame的课中有这样一行代码: x, y = pygame.mouse.get_pos() 这个函数返回的其实是一个“元组”,今天我们来讲讲这个东西。...

3197
来自专栏Java技术栈

Java中的宏变量,宏替换详解。

群友在微信群讨论的一个话题,有点意思,特拿出来分享一下。 ? 输出true false 来看下面这段程序,和群友分享的大致一样。 public static ...

3465
来自专栏韦弦的微信小程序

Swift 旋转数组 - LeetCode

例如,如果 n = 7 , k = 3,给定数组 [1,2,3,4,5,6,7] ,向右旋转后的结果为 [5,6,7,1,2,3,4]。

735
来自专栏GreenLeaves

JavaScript之apply()和call()的区别

我 在一开始看到javascript的函数apply和call时,非常的模糊,看也看不懂,最近在网上看到一些文章对apply方法和call的一些示 例,总算是看...

1757
来自专栏编程

浅谈Go语言中闭包的使用

闭包(Closure),又称词法闭包(Lexical Closure)或函数闭包(function closures),是引用了自由变量的函数。这个被引用的自由...

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

聊聊C语言-编程世界的容器

上一篇聊聊C语言-存储世界的奥秘,我们介绍了计算机的整个存储体系设计,了解了我们的数据在计算机中是怎么被存储的。然而在我们的编程中我们的代码也是按照这个结构被计...

3327
来自专栏aCloudDeveloper

指向函数的指针

Author: bakari   Date: 2012.8.8 做好总结我觉得是把知识学扎实必不可少的实践环节。这个知识点是当初自己在学习这一块做的一些笔记,现...

1746
来自专栏zhisheng

运算优先级、结合性、求值顺序、副作用和顺序点

标题中这几个概念,是很多C/C++程序员在表达式上容易出问题或不清楚的地方,虽然这些概念在很多语言都有体现,但C里面特别明显,所以就以C语言为例子总结下 运算...

4087

扫描关注云+社区