老四开始浅析数据结构相关的知识了，由于大学的时候没有好好学习这门课程，现在虽然说后悔不已，但是我更觉得只要认真，什么时候都不晚。所以开这个菜单栏也采取随学随用随写的模式，不按照顺序来，之前已经浅析过合并排序相关的知识，可以参考一下《浅析数据结构排序篇之归并排序Merge sort》这篇文章。接下来少啰嗦，开始。
开始之前老四推荐一个app-中文名《算法动画图解》，该app是由两个日本友人开发设计，支持iOS和安卓。软件官网: Algorithms。安卓版本请在Google Play(谷歌应用商店)中下载。下载链接: 算法动画图解谷歌应用商店安卓版本下载。该app将所有的算法通过动画图解的方式来讲述，由浅入深，简单易懂，学习完之后还可以不断的进行测试训练，非常好用。注意: 软件部分算法需要付费购买才能解锁全部算法，18元左右，感觉好的话可以支持一下。
接下来，需要先简单的复习一下数据结构中两个重要的表达式:空间复杂度和时间复杂度。
算法时间复杂度的定义:
在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作: T(n)=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。这样用大写O()来体现算法时间复杂度的记法，我们称之为大O记法。一般情况下，随着n的增大，T(n)增长最慢的算法为最优算法。由此算法时间复杂度的定义可知，我们常用的时间复杂度分别为O(n)，O(1)，O(n^2)。我们分别给它们取了非官方的名称，O(1)叫常数阶、O(n)叫线性阶、O(n^2)叫平方阶，当然，还有其他的一些阶。
如何推导大O阶:
- 用常数1取代运行时间中的所有加法常数。
- 在修改后的运行次数函数中，只保留最高阶项。
- 如果最高阶项存在且不是1，则去除与这个项相乘的常数。
常用的大O阶:
- 常数阶: 执行时间恒定的算法，我们称之为具有O(1)的时间复杂度，又叫常数阶。注意：不管这个常数是多少，我们都记作O(1)，而不能是O(3)、O(12)等其他任何数字。
- 线性阶: 代码中的循环体要执行n次，每次时间复杂度O(1)，所以线性阶的时间复杂度O(n)。
- 对数阶: 在循环体中，循环索引按照几何级别指数新增并接近循环的最大值n。形如while(count < n) { count = count * 2 };由2^x=n得出x=log(2为底n的对数)，简作O(logn)。
- 平方阶: 一般都是循环的嵌套，总结可以得出平方阶是循环的时间复杂度等于循环体的复杂度乘该循环运行的次数。
常用的时间复杂度所耗费的时间从小到大依次是:
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n);
算法空间复杂度:
我们经常会碰到用空间换时间的例子，比如说List中的LinkedList的查询就是利用了双向链表的特性，如果index离链表表头比较近，就从节点头部遍历。否则就从节点尾部开始便利，从而牺牲空间(双向链表)来换取时间。再比如老四之前在文章《Java十道由浅入深的面试题第一期(上) 详细解析》中提及到的关于判断某年是不是闰年的思路以及解决办法也提及到了利用空间换时间。算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作: S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。一般情况下，一个程序在机器上执行时，除了需要存储程序本身的指令、常数、变量和输入数据外，还需要存储对数据操作的存储单元。若输入数据所占空间只取决于问题本身，和算法无关，这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为O(1)。通常，我们都使用”时间复杂度”来指运行时间的需求，使用”空间复杂度”指空间需求。当不用限定词地使用”复杂度”时，通常都是指时间复杂度。
我们开始步入正题，快速排序算法被列为20世纪十大算法之一，上世纪最伟大的计算机科学家由图灵奖获得者TonyHoare设计。与其他算法相比，它的特点是数字的比较和交换次数少，在许多情况下可以高速的进行排序。附20世纪十大算法:
- 蒙特卡洛方法
- 单纯形法
- Krylov子空间迭代法
- 矩阵计算的分解方法
- 优化的Fortran编译器
- 计算矩阵特征值的QR算法
- 快速排序算法
- 快速傅立叶变换
- 整数关系检测算法
- 快速多极算法
快速排序的基本思想:
通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序的目的。
快速排序属于不稳定排序，时间空间复杂度均为O(logn);
感谢老四的同事”菠菜”同学为本篇文章提供的快速排序动画学习教程以及快速排序动画图解，让我们对快速排序有了更加清晰直观的感受，深刻的印象。
快速排序动画学习教程:
快速排序动画图解:
下面看一下基本的快速排序代码示例:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
package com.glorze.sort; import java.util.Arrays; /** * 基本的快速排序 * @ClassName QuickSort * @author: glorze.com * @since: 2018年9月14日 下午4:33:09 */ public class QuickSort { /** * * 将大于pivot放在右边，针对左右两个子序列重复此过程 * 直到序列为空或者只有一个元素。 * @param arr * @return */ /** * 第一个操作的对象是数列中所有的数字，选择一个数字作为排序的基准。 * 这个数字被称作pivot(中枢点)，为了方便起见，我们选择最左边的数字作为pivot。 * @Title: quickSort * @param arr 要排序的数列 * @return int[] * @author: 高老四博客 * @since: 2018年9月14日 下午4:36:01 */ public static int[] quickSort(int arr[]){ return qsort(arr，0，arr.length-1); } public static int[] qsort(int arr[]，int low，int high){ // 0个或1个元素，返回 if(low>=high){ return arr; } // 选取左端点为枢轴 int pivot=arr[low]; int tmp; int idx=low; for(int i=low+1;i<=high;i++){ // 小于枢轴的放到左边 if(arr[i]<pivot){ tmp=arr[++idx]; arr[idx]=arr[i]; arr[i]=tmp; } } System.out.println(low); // 交换左端点和枢轴位置 tmp=arr[low]; arr[low]=arr[idx]; arr[idx]=tmp; qsort(arr， low， idx-1); qsort(arr， idx+1， high); return arr; } public static void main(String[] args) { int arr[]={1，3，22，29，11，5，7，9，2，4，6，8}; arr=QuickSort.quickSort(arr); System.out.println("基本快速排序: "+Arrays.toString(arr)); } } |
以上属于基本的快速排序实现，在此基础上我们可以对其进行代码以及思路上的优化，包括但不限于:
-
优化选取枢轴(三数取中、九数取中): 所谓的三数取中其实是为了优化基本有序的数列，中枢点的选取对排序的性能影响很大，而随机选取也总不能保证碰撞成功，于是经过前人的实验，弄出了三数取中，即随机取三个数(但是一般都取最左、最右以及中间位置)排列好将中间数作为枢轴。
-
优化不必要的交换(两个索引，在两个索引的的过程中如果等于枢轴集中放在两端，最后放入到中间也是一种优化，叫fat-partion)
-
优化小数组时的排序方案(大小大于40的数组使用median-of-nine(九数取中)选择pivot，大小在7到40之间的数组使用median-of-three选择中数，大小等于7的数组直接选择中数，大小小于7的数组则直接使用插入排序)
-
优化递归操作(尾递归:在函数返回的时候，调用自身本身，并且return语句不能包含表达式。这样.编译器或者解释器就可以把尾递归做优化.使递归本身无论调用多少次.都只占用一个栈帧.会出现栈溢出的情况。)
老四针对以上优化又写了几个例子，分别是:
- 随机数作为pivot
- 快速排序随机数作pivot双索引实现(这个就是动画中体现的一个pivot加双索引的实现，只不过是随机数作pivot)
- 快速排序随机数作为枢轴双索引短数组插入排序(一)
- 快速排序随机数作为枢轴短数组插入排序另一种写法(二)
- 快速排序三数取中九数取中做枢轴双索引尾递归
老四这里限于篇幅的原因只给出快速排序三数取中(九数取中)做枢轴pivot双索引尾递归的代码，其余代码放到工程文件之中，需要参考的文末自助获取下载即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 |
package com.glorze.sort; import java.util.Arrays; /** * 快速排序三数取中九数取中做枢轴双索引尾递归 * @ClassName QuickSortWithInserSortAndMoT * @author: glorze.com * @since: 2018年9月25日 下午2:19:51 */ public class QuickSortWithInserSortAndMoT { /** * 选择一个pivot(中轴点)，将小于pivot放在左边 将大于pivot放在右边，针对左右两个子序列重复此过程 直到序列为空或者只有一个元素。 * @param arr * @return int[] * @author: 高老四博客 * @since: 2018年9月25日 下午3:02:25 */ public static int[] quickSortWithInserSortAndMoT(int arr[]) { return qsort(arr， 0， arr.length - 1); } public static int[] qsort(int arr[]， int low， int high) { // 0个或1个元素，返回 if (low >= high) { return arr; } // 计算数组长度 int seven = 7; int forty = 40; int len = high - low + 1; // 在数组大小小于7的情况下使用快速排序 if (len < seven) { arr = InsertSort.insertSort(arr); return arr; } // 求出中点，大小等于7的数组直接选择中数 int m = low + (len >> 1); // 大小大于7 if (len > seven) { int l = low; int n = low + len - 1; // 大数组采取九数取中 if (len > forty) { int s = len / 8; // 取样左边三个数 然后三数取中 l = med3(arr， l， l + s， l + 2 * s); // 取样重点三个数 三数取中 m = med3(arr， m - s， m， m + s); // 取样右边三数 三数区中 n = med3(arr， l， m， n); } // 中数中的三数取中 m = med3(arr， l， m， n); } // 选取随机数作为枢轴 int tmp; tmp = arr[low]; arr[low] = arr[m]; arr[m] = tmp; // 从左索引i指向左端点 m = low; // 从右索引j初始指向右端点 int j = high + 1; int pivot = arr[low]; while (true) { // 查找比枢轴大于等于的位置 do { m++; } while (m <= high && arr[m] < pivot); // 查找比枢轴小于等于的位置 do { j--; } while (arr[j] > pivot); if (j < m) { break; } tmp = arr[m]; arr[m] = arr[j]; arr[j] = tmp; } // 交换左端点和枢轴位置 tmp = arr[low]; arr[low] = arr[j]; arr[j] = tmp; qsort(arr， low， j - 1); // 尾递归 low = pivot + 1; // 最后对整个数组进行插入排序 if (low == 0 && high == arr.length - 1) { arr = InsertSort.insertSort(arr); return arr; } return arr; } public static int med3(int x[]， int a， int b， int c) { return x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a) : x[b] > x[c] ? b : x[a] > x[c] ? c : a; } public static void main(String[] args) { int arr[] = { 1， 3， 22， 29， 11， 5， 7， 9， 46， 2， 4， 6， 8 }; arr = QuickSortWithInserSortAndMoT.quickSortWithInserSortAndMoT(arr); System.out.println("快速排序三数取中九数取中做枢轴双索引尾递归:" + Arrays.toString(arr)); } } |
这里再说一下关于递归和递归的一点基础知识和浅析:
递归的定义: 栈有一个重要应用是在程序设计语言中实现递归.一个直接调用自己或者通过一系列的调用语句间接地调用自己的函数，称作递归函数。
尾递归的定义: 在函数返回的时候，调用自身本身，并且return语句不能包含表达式。这样.编译器或者解释器就可以把尾递归做优化.使递归本身无论调用多少次.都只占用一个栈帧.不会出现栈溢出的情况。
- 调用同一个方法
- 尾递归的形式&编译器对尾递归的优化(重复利用同一个栈帧)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
#普通递归 def recsum(x): if x == 1: return x else: return x + recsum(x - 1) #尾递归 def tailrecsum(x， running_total=0): if x == 0: return running_total else: return tailrecsum(x - 1， running_total + x) |
内存泄露: 指程序中动态分配内存给一些临时对象，但是对象不会被GC所回收，它始终占用内存。即被分配的对象可达但已无用。
- JVM中的栈记录了线程的方法调用。每个线程拥有一个栈。在某个线程的运行过程中，如果有新的方法调用，那么该线程对应的栈就会增加一个存储单元，即栈帧 (frame)。在frame中，保存有该方法调用的参数、局部变量和返回地址。
- Java的参数和局部变量只能是基本类型的变量(比如int)，或者对象的引用(reference) 。因此，在栈中，只保存有基本类型的变量和对象引用。而引用所指向的对象保存在堆中。
- 解决了所有情况下的内存泄露的问题，但还可以由于其他原因内存溢出
- 针对内存中的堆空间
- 正在运行的方法中的堆中的对象是不会被管理的，因为还有引用(栈帧没有被清空)
- 一般简单的自动垃圾回收机制是采用引用计数 (reference counting)的机制。每个对象包含一个计数器。当有新的指向该对象的引用时，计数器加1。当引用移除时，计数器减 1，当计数器为0时，认为该对象可以进行垃圾回收。
- 优化了递归调用时的内存溢出问题
- 针对内存中的堆空间和栈空间
- 只在递归调用的时候使用，而且只能对于写成尾递归形式的递归进行优化
- 正在运行的方法的堆和栈空间正是优化的目标
更博不易，如果觉得文章对你有帮助并且有能力的老铁烦请赞助盒烟钱，点我去赞助。或者扫描文章下面的微信/支付宝二维码打赏任意金额，老四这里抱拳了。赞助时请备注姓名或者昵称，因为您的署名会出现在赞赏列表页面，您的赞赏钱财也会被用于小站的服务器运维上面，再次抱拳。
资源下载
隐藏内容：******，购买后可见！
下载价格：0 G币
您需要先登录后，才能购买资源
欢迎访问高老四博客(glorze.com),本站技术文章代码均为老四亲自编写或者借鉴整合,其余资源多为网络收集,如涉及版权问题请与站长联系。如非特殊说明,本站所有资源解压密码均为:glorze.com。
