文档章节

数据结构与算法系列十五(快速排序)

yhhitall
 yhhitall
发布于 04/15 11:28
字数 2781
阅读 71
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

1.引子

1.1.为什么要学习数据结构与算法?

有人说,数据结构与算法,计算机网络,与操作系统都一样,脱离日常开发,除了面试这辈子可能都用不到呀!

有人说,我是做业务开发的,只要熟练API,熟练框架,熟练各种中间件,写的代码不也能“飞”起来吗?

于是问题来了:为什么还要学习数据结构与算法呢?

#理由一:
	面试的时候,千万不要被数据结构与算法拖了后腿
#理由二:
	你真的愿意做一辈子CRUD Boy吗
#理由三:
	不想写出开源框架,中间件的工程师,不是好厨子

1.2.如何系统化学习数据结构与算法?

我想好了,还是需要学习数据结构与算法。但是我有两个困惑:

1.如何着手学习呢?

2.有哪些内容要学习呢?

学习方法推荐:

#学习方法
1.从基础开始,系统化学习
2.多动手,每一种数据结构与算法,都自己用代码实现出来
3.思路更重要:理解实现思想,不要背代码
4.与日常开发结合,对应应用场景

学习内容推荐:

数据结构与算法内容比较多,我们本着实用原则,学习经典的、常用的数据结构、与常用算法

#学习内容:
1.数据结构的定义
2.算法的定义
3.复杂度分析
4.常用数据结构
	数组、链表、栈、队列
	散列表、二叉树、堆
	跳表、图
5.常用算法
	递归、排序、二分查找
	搜索、哈希、贪心、分治
	动态规划、字符串匹配

2.考考你

上一篇:数据结构与算法系列十四(归并排序)中,归并排序利用分治的思想,实现了高效率的排序,时间复杂度是:O(nlogn)。不知道你有没有发现,归并排序有一个不完美的地方?如果你还没有发现,让我们一起来分析一下。

归并排序的核心有两个过程:分解、合并。通过分解函数递归分解子问题;通过合并函数实现排序。那么在合并函数中,我们需要两个临时数组来协助排序:

 public static void merge(Integer[] array,int left,int mid,int right){
        // 左边数组大小
        int[] leftA = new int[mid-left];
        // 右边数组大小
        int[] rightA = new int[right-mid+1];
     
     .................省略其它代码....................
 }

到这里,我想你应该知道归并排序不完美的地方了,归并排序不是原地排序算法,它的空间复杂度是:O(n)

那有没有时间复杂度满足:O(nlogn),又同时空间复杂度是:O(1)的排序算法呢?答案是:有。它就是我们今天的主角:快速排序

#考考你:
1.你知道快速排序的核心思想吗?
2.你能用java实现快速排序吗?
3.你知道快速排序与归并排序的区别与联系吗?

3.案例

3.1.快速排序核心思想

假设有一个待排序序列:[4, 5, 6, 3, 2, 1]。我们需要按照升序进行排序,排序后的序列是这 样的:[1, 2, 3, 4, 5, 6]。

如何通过快速排序实现呢?

快速排序核心思想:

快速排序,与归并排序算法类似,也利用了分而治之的思想,它的排序过程:

1.每一次从待排序序列中,选择一个元素,作为分区元素:pivot

2.比如选择第1个元素,或者最后1个元素

3.将大于pivot的元素放在一边,将小于pivot的元素放在另一边

4.一次分区结束,把待排序序列分成3个部分

#4.1.小于分区元素子序列:<pivot
#4.2.分区元素:=pivot
#4.3.大于分区元素子序列:>pivot

5.将小于分区元素子序列,继续递归分区排序

6.将大于分区元素子序列,继续递归分区排序

7.一直到子分区序列剩下一个元素,即low>=high为止。排序结束(整个序列排好序)

 

3.2.快速排序代码实现

3.2.1.排序入口函数

/**
* 快速排序入口
* @param array  待排序数组
* @param n     数据规模
*/
public static void sort(Integer[] array,int n){
  // 如果数据规模小于等于1,不需要排序
  if(n <= 1){
     return;
  }

   // 快速排序(递归函数)
   quickSort(array,0,n-1);
}

3.2.2.递归函数

/**
* 快速排序(递归函数)
* @param array
* @param low
* @param high
*/
public static void quickSort(Integer[] array,int low,int high){
   // 终止条件
   if(low >= high){
      return;
   }

   // 分区函数寻找:pivot
   int mid = partition(array,low,high);

   // 低位递归排序
   quickSort(array,low,mid-1);

   // 高位递归排序
   quickSort(array,mid+1,high);

}

3.2.3.分区函数

/**
* 分区函数
* @param array
* @param low
* @param high
* @return
*/
public static int partition(Integer[] array,int low,int high){

   // 定义两个临时变量,方便输出数组(它们与排序无关)
   int tmpLow = low;
   int tmpHigh = high;

   // 选取第一个元素作为pivot(分区点)
   int pivot = array[low];

   System.out.println("2.1.本次分区:low="+low+"&high="+high+",待排序序列:"+printArray(array,tmpLow,tmpHigh)+",选择分区元素pivot:array["+low+"]="+pivot);

   // 循环处理low<high
   System.out.println("2.2.循环操作low<high:从右往左,将小于pivot的数据,放入左边.pivot="+pivot);
   System.out.println("2.3.循环操作low<high:从左往右,将大于pivot的数据,放入右边.pivot="+pivot);
  while (low<high){

     // 从右往左,将小于pivot的数据,放入左边
     while(low<high && array[high]>=pivot){
         high -=1;
     }
     array[low] = array[high];
     System.out.println("2.2.1.本次循环结束,low="+low+"&high="+high+",待排序序列:"+printArray(array,tmpLow,tmpHigh));

     // 从左往右,将大于pivot的数据,放入右边
     while(low<high && array[low]<=pivot){
          low +=1;
     }
     array[high]=array[low];
     System.out.println("2.3.1.本次循环结束,low="+low+"&high="+high+",待排序序列:"+printArray(array,tmpLow,tmpHigh));

    }

   // 找到分区点low,并返回
   array[low] = pivot;
   System.out.println("2.4.本次分区结束pivot:array["+low+"]="+pivot+"后,待排序序列:"+printArray(array,tmpLow,tmpHigh));
   System.out.println("2.5.-------------------------华丽丽分割线-------------------------");
      return low;
 }

分区函数中数组输出辅助函数:

/**
* 根据数组起始位置,结束位置输出数组内容
* @param array
* @param start
* @param end
* @return
*/
public static String printArray(Integer [] array,int start,int end){
     StringBuilder builder = new StringBuilder();
     builder.append("[");
     for(int i = start; i <= end;i++){
         builder.append(array[i]).append(",");
     }

     // 去掉最后一个:,
     String substring = builder.substring(0, builder.length() - 1);
     substring += "]";

      return substring;
}

3.3.测试代码

public static void main(String[] args) {
   // 初始化测试数组
   Integer[] array = {4,5,6,3,2,1};
   // 1.排序前
   System.out.println("1.排序前数组:" + Arrays.deepToString(array));

   // 排序
   System.out.println("2.开始排序-------------------------------");
   sort(array,array.length);

   // 3排序后
   System.out.println("3.排序后数组:" + Arrays.deepToString(array));
}

测试结果:

D:\02teach\01soft\jdk8\bin\java 
    com.anan.algorithm.sort.QuickSort
1.排序前数组:[4, 5, 6, 3, 2, 1]
2.开始排序-------------------------------
2.1.本次分区:low=0&high=5,待排序序列:[4,5,6,3,2,1],选择分区元素pivot:array[0]=4
2.2.循环操作low<high:从右往左,将小于pivot的数据,放入左边.pivot=4
2.3.循环操作low<high:从左往右,将大于pivot的数据,放入右边.pivot=4
2.2.1.本次循环结束,low=0&high=5,待排序序列:[1,5,6,3,2,1]
2.3.1.本次循环结束,low=1&high=5,待排序序列:[1,5,6,3,2,5]
2.2.1.本次循环结束,low=1&high=4,待排序序列:[1,2,6,3,2,5]
2.3.1.本次循环结束,low=2&high=4,待排序序列:[1,2,6,3,6,5]
2.2.1.本次循环结束,low=2&high=3,待排序序列:[1,2,3,3,6,5]
2.3.1.本次循环结束,low=3&high=3,待排序序列:[1,2,3,3,6,5]
2.4.本次分区结束pivot:array[3]=4后,待排序序列:[1,2,3,4,6,5]
2.5.-------------------------华丽丽分割线-------------------------
2.1.本次分区:low=0&high=2,待排序序列:[1,2,3],选择分区元素pivot:array[0]=1
2.2.循环操作low<high:从右往左,将小于pivot的数据,放入左边.pivot=1
2.3.循环操作low<high:从左往右,将大于pivot的数据,放入右边.pivot=1
2.2.1.本次循环结束,low=0&high=0,待排序序列:[1,2,3]
2.3.1.本次循环结束,low=0&high=0,待排序序列:[1,2,3]
2.4.本次分区结束pivot:array[0]=1后,待排序序列:[1,2,3]
2.5.-------------------------华丽丽分割线-------------------------
2.1.本次分区:low=1&high=2,待排序序列:[2,3],选择分区元素pivot:array[1]=2
2.2.循环操作low<high:从右往左,将小于pivot的数据,放入左边.pivot=2
2.3.循环操作low<high:从左往右,将大于pivot的数据,放入右边.pivot=2
2.2.1.本次循环结束,low=1&high=1,待排序序列:[2,3]
2.3.1.本次循环结束,low=1&high=1,待排序序列:[2,3]
2.4.本次分区结束pivot:array[1]=2后,待排序序列:[2,3]
2.5.-------------------------华丽丽分割线-------------------------
2.1.本次分区:low=4&high=5,待排序序列:[6,5],选择分区元素pivot:array[4]=6
2.2.循环操作low<high:从右往左,将小于pivot的数据,放入左边.pivot=6
2.3.循环操作low<high:从左往右,将大于pivot的数据,放入右边.pivot=6
2.2.1.本次循环结束,low=4&high=5,待排序序列:[5,5]
2.3.1.本次循环结束,low=5&high=5,待排序序列:[5,5]
2.4.本次分区结束pivot:array[5]=6后,待排序序列:[5,6]
2.5.-------------------------华丽丽分割线-------------------------
3.排序后数组:[1, 2, 3, 4, 5, 6]

Process finished with exit code 0

4.讨论分享

#考考你答案:
1.你知道快速排序的核心思想吗?
  1.1.快速排序,应用了分而治之的思想
  1.2.每一次从待排序序列中,选择一个分区元素:pivot
  1.3.将小于pivot的元素放在一边,将大于pivot的元素放在另一边
  1.4.每一次分区结束,待排序序列分为三个部分:
    a.小于分区元素pivot的子序列
    b.分区元素
    c.大于分区元素pivot的子序列
  1.5.递归分区排序,小于分区元素子序列
  1.6.递归分区排序,大于分区元素子序列
  1.7.直到待排序分区元素子序列,剩下一个元素,即满足数组下标:low>=high
  1.8.那么整个排序结束

2.你能用java实现快速排序吗?
  2.1.参考【3.2】节代码实现
  
3.你知道快速排序与归并排序的联系与区别吗?
  3.1.联系
    a.都应用了分而治之的思想
    b.都是高效的排序算法,时间复杂度都是:O(nlogn)
    
  3.2.区别
    a.【归并排序】不是原地排序算法,空间复杂度:O(n)
    b.【快速排序】通过设计分区函数:partition,可以在原地排序,空间复杂度:O(1)
    c.【归并排序】是稳定的排序算法,如果有相同值的元素,排序后顺序保持不变
    d.【快速排序】不是稳定的排序算法,存在元素的交换操作,如果有相同值的元素,排序后顺序会发生改变

 

yhhitall
粉丝 0
博文 37
码字总数 60294
作品 0
梅州
架构师
私信 提问
加载中
请先登录后再评论。
访问安全控制解决方案

本文是《轻量级 Java Web 框架架构设计》的系列博文。 今天想和大家简单的分享一下,在 Smart 中是如何做到访问安全控制的。也就是说,当没有登录或 Session 过期时所做的操作,会自动退回到...

黄勇
2013/11/03
3.3K
6
代码生成器--Codgen

Codgen是一个基于数据库元数据模型,使用freemarker模板引擎来构建输出的代码生成器。freemarker的数据模型结构通常来说都是一个Map树状结构模型,codgen也不例外,它的数据模型这棵树的根节...

黄天政
2013/01/29
1.4W
2
C++模板库--C++ B-tree

这是一个google开源的C++模板库,实现了基于B-tree数据结构的有序内存容器。类似于STL的map、set、multimap和multiset模板,C++ B-tree也提供了btreemap、btreeset、btreemultimap和btreemu...

匿名
2013/02/05
3.2K
1
漏洞检测工具--Peach Fuzzer

Peach是一种用Python编写的 Fuzzer。这种工具有助于发现并公开许多漏洞,并认为是黑客和安全团体中最流行的工具之一。为了利用Peach框架,必须创建Phthon脚本,脚本 中包含了在服务器上执行的...

匿名
2013/02/06
8.7K
1
开源数据访问组件--Smark.Data

Smark.Data是基于Ado.net实现的数据访问组件,提供基于强类型的查询表达式进行灵活的数据查询,统计,修改和删除等操作;采用基于条件驱动的操作模式,使数据操作更简单轻松;内部通过标准SQL...

泥水佬
2013/03/12
2.5K
0

没有更多内容

加载失败,请刷新页面

加载更多

低代码平台,让企业开发不再是难事

近几年,企业面临数字化转型带来的压力,为了快速适应行业变化和赶超竞争对手,在高级技术人才缺乏的情况下,低代码开发获得了企业的青睐。 何为低代码开发,低代码开发平台(LCDP)是无需编...

osc_veyfyz58
22分钟前
4
0
【科创人独家】华旦天使张洁:风口是创业者的造物,投资本质是件农活

在投资界活跃着一批乘风破浪的姐姐们,江湖人敬称一声“花姐”的华旦天使投资创始人张洁是个中代表:言谈飒爽,举止利落,洞察力十足。 技术背景创业者 宜:创新、洞察 忌:轴、轻视销售 科创...

osc_lc4icfkt
23分钟前
7
0
霍尼韦尔(中国)推出数字化劳动力管理解决方案套件,以支持健康合规性和远程操作

休斯敦霍尼韦尔(中国)近期宣布了一个完整的模块化软件解决方案,以帮助工业公司在员工返回工作场所时强制遵守关键的健康和安全要求,包括体温检查和自动进入管理流程,更多信息尽在振工链。...

osc_ju8o7gji
24分钟前
0
0
萤石云摄像头调整码流,画面模糊的处理

近期在将萤石云合并到监控主机时发现画面只有750左右,原以为是海康威视主机的问题,必竟两个产品系列,后我又购买了萤石云主机进行测试还是一样。经过与售后沟通他们给出了调整画面的方案,...

osc_5h5udyht
26分钟前
9
0
Oracle 锁排查SQL

查询锁SQL或ASH报告 select sql_text from v$sql where hash_value in (select sql_hash_value from v$session where sid in (select session_id from v$locked_object)); 查询TX锁 set line......

osc_qgfjs4a5
26分钟前
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部