关键词:
2.1.1 游戏规则
1. 排序成本模型:在研究排序算法时,我们需要计算比较和交换的数量。对于不交换元素的算法,我们会计算访问数组的次数。
2.
· 原地排序算法:除了函数调用所需的栈和固定数目的实例变量之外无需额外内存的原地排序算法;
· 其他排序算法:需要额外内存空间来储存另一份数组副本。
2.2.2 选择排序
public class Selection { public static void sort(Comparable[] a) { // 将a[]按升序排列 int N = a.length; // 数组长度 for (int i = 0; i < N; i++) { // 将a[i]和a[i+1..N]中最小的元素交换 int min = i; for (int j = i + 1; j < N; j++) if (less(a[j], a[min])) min = j; exch(a, i, min); } } private static boolean less(Comparable v, Comparable w) { return v.compareTo(w) < 0; } private static void exch(Comparable[] a, int i, int j) { Comparable t = a[i]; a[i] = a[j]; a[j] = t; } private static void show(Comparable[] a) { // 在单行中打印数组 for (int i = 0; i < a.length; i++) StdOut.print(a[i] + " "); StdOut.println(); } public static boolean isSorted(Comparable[] a) { // 测试数组元素是否有序 for (int i = 1; i < a.length; i++) if (less(a[i], a[i - 1])) return false; return true; } public static void main(String[] args) { // 从标准输入读取字符串,将它们排序并输出 String[] a = In.readStrings(); sort(a); assert isSorted(a); show(a); } }
1. 定义:首先,找到数组中最小的那个元素,其次,将它和数组的第一个元素交换位置(如果第一个元素就是最小元素那么它就和自己交换)。再次,在剩下的元素中找到最小的元素,将它与数组的第二个元素交换位置。如此往复,直到将整个数组排序。
2. 对于长度为N的数组,选择排序需要大约N^2/2次比较和N次交换。
3. 选择排序有两个很鲜明的特点:
· 运行时间和输入无关(一个已经有序的数组或主键全部相等的数组和一个元素随机排列的数组所用的排序时间竟然一样长);
· 数据移动是最少的(选择排序用了N次交换--线性级别,大部分其他算法的交换次数--线性对数或是平方级别)。
2.2.3 插入排序
public class Insertion { public static void sort(Comparable[] a) { // 将a[]按升序排列 int N = a.length; for (int i = 1; i < N; i++) { // 将a[i]插入到a[i-1]、a[i-2]、a[i-3]...之中 for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) exch(a, j, j - 1); } } private static boolean less(Comparable v, Comparable w) { return v.compareTo(w) < 0; } private static void exch(Comparable[] a, int i, int j) { Comparable t = a[i]; a[i] = a[j]; a[j] = t; } private static void show(Comparable[] a) { // 在单行中打印数组 for (int i = 0; i < a.length; i++) StdOut.print(a[i] + " "); StdOut.println(); } public static boolean isSorted(Comparable[] a) { // 测试数组元素是否有序 for (int i = 1; i < a.length; i++) if (less(a[i], a[i - 1])) return false; return true; } public static void main(String[] args) { // 从标准输入读取字符串,将它们排序并输出 String[] a = In.readStrings(); sort(a); assert isSorted(a); show(a); } }
1. 与冒泡排序的区别:
· 插入排序:将每一个元素插入到其他已经有序的元素中的适当位置;
· 冒泡排序:每次将剩余最大的元素向右边推过去。
2. 插入排序所需的时间取决于输入中元素的初始顺序。
3. 对于随机排序的长度为N且主键不重复的数组,插入排序:
· 平均情况下需要~N^2/4次比较以及~N^2/4次交换
· 最坏情况下需要~N^2/2次比较以及~N^2/2次交换
· 最好情况下需要N-1次比较和0次交换
4. 下面是几种典型的部分有序的数组:
· 数组中每个元素距离它的最终位置都不远
· 一个有序的大数组接一个小数组
· 数组中只有几个元素的位置不正确
插入排序对这样的数组很有效,而选择排序则不然。
2.1.4 排序算法的可视化
1. 插入排序所需的比较次数平均只有选择排序的一半。
2.1.5 比较两种排序算法
public class SortCompare { public static double time(String alg, Double[] a) { Stopwatch timer = new Stopwatch(); if (alg.equals("Insertion")) Insertion.sort(a); if (alg.equals("Selection")) Selection.sort(a); // if (alg.equals("Shell")) Shell.sort(a); // if (alg.equals("Merge")) Merge.sort(a); // if (alg.equals("Quick")) Quick.sort(a); // if (alg.equals("Heap")) Heap.sort(a); return timer.elapsedTime(); } public static double timeRandomInput(String alg, int N, int T) { // 使用算法alg将T个长度为N的数组排序 double total = 0.0; Double[] a = new Double[N]; for (int t = 0; t < T; t++) { // 进行一次测试(生成一个数组并排序) for (int i = 0; i < N; i++) a[i] = StdRandom.uniform(); total += time(alg, a); } return total; } public static void main(String[] args) { String alg1 = args[0]; String alg2 = args[1]; int N = Integer.parseInt(args[2]); int T = Integer.parseInt(args[3]); double t1 = timeRandomInput(alg1, N, T); // 算法1的总时间 double t2 = timeRandomInput(alg2, N, T); // 算法2的总时间 StdOut.printf("For %d random Doubles\n %s is", N, alg1); StdOut.printf(" %.1f times faster than %s\n", t2 / t1, alg2); } } /* java SortCompare Insertion Selection 1000 100 For 1000 random Doubles Insertion is 1.7 times faster than Selection */
这个用例会运行由前两个命令行参数指定的排序算法,对长度为N(由第三个参数指定)的
1. 对于随机排序的无重复主键的数组,插入排序和选择排序的运行时间是平方级别的,两者之比应该是一个较小的常数。
2.1.6 希尔排序
public class Shell { public static void sort(Comparable[] a) { // 将a[]按升序排列 int N = a.length; int h = 1; while (h < N / 3) h = 3 * h + 1; // 1, 4, 13, 40, 121, 364, 1093, ... while (h >= 1) { // 将数组变为h有序 for (int i = h; i < N; i++) { // 将a[i]插入到a[i-h],a[i-2*h],a[i-3*h]...之中 for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) exch(a, j, j - h); } h = h / 3; } } private static boolean less(Comparable v, Comparable w) { return v.compareTo(w) < 0; } private static void exch(Comparable[] a, int i, int j) { Comparable t = a[i]; a[i] = a[j]; a[j] = t; } private static void show(Comparable[] a) { // 在单行中打印数组 for (int i = 0; i < a.length; i++) StdOut.print(a[i] + " "); StdOut.println(); } public static boolean isSorted(Comparable[] a) { // 测试数组元素是否有序 for (int i = 1; i < a.length; i++) if (less(a[i], a[i - 1])) return false; return true; } public static void main(String[] args) { // 从标准输入读取字符串,将它们排序并输出 String[] a = In.readStrings(); sort(a); assert isSorted(a); show(a); } }
1. 思想:使数组中任意间隔为h的元素都是有序的。
2. 通过提升速度来解决其他方式无法解决的问题是研究算法的设计和性能的主要原因之一。
3. 希尔排序的运行时间达不到平方级别。例如,已知在最坏的情况下算法2.3的比较次数和N^(3/2)成正比。
4. 希尔排序对于中等大小的数组它的运行时间是可以接受的。它的代码量很小,且不需要使用额外的内存空间。
5.如果你需要解决一个排序问题而又没有系统排序函数可用(例如直接接触硬件或是运行于嵌入式系统中的代码),可以先用希尔排序,然后再考虑是否值得将它替换为更加复杂的排序算法。
算法(第4版)-2.4优先队列
定义:一种支持删除最大元素和插入元素的数据结构。经典实现:基于二叉堆数据结构。 2.4.1API 1.只要我们能够高效地实现insert()和delMin(),下面的优先队列用例中调用了MinPQ的TopM就能使用优先队列解决这个问题。&nbs... 查看详情
算法(第4版)
第1章基础第2章排序第3章查找第4章图第5章字符串 第1章基础 第2章排序 第3章查找 第4章图 第5章字符串 ------------------------------------------------------------------------------------------ 查看详情
算法(第4版)-2.5应用
...序、快速排序、堆排序 2.5.2我应该使用哪种排序算法 1.快速排序是最快的通用排序算法。 2.将原始类型数据排序:跳过引用可以为我们节省储存所有引用所 查看详情
算法(第4版)-2.3快速排序
publicclassQuick{publicstaticvoidsort(Comparable[]a){StdRandom.shuffle(a);//消除对输入的依赖sort(a,0,a.length-1);}privatestaticvoidsort(Comparable[]a,intlo,inthi){if(hi<=lo)return;intj=partition(a,lo,hi);/ 查看详情
算法(第4版)-2.2归并排序
...将两个有序的数组归并成一个更大的有序数组。 归并算法:先(递归地)将它分为两半分别排序,然后将结果归并起来。·优点:保证将任意长度为N的数组排序所需时间和NlogN成正比;·缺点:所需的额外空间和N成正比。&nbs... 查看详情
高效(初级算法)大纲
一、算法分析初步1、渐进时间复杂度2、上界3、分治4、正确对待算法分析结果 二、再谈排序与检索1、归并排序2、快速排序3、二分查找 三、递归与分治 四、贪心1、背包2、区间3、huffman编码 五、算法设计方法1、... 查看详情
初级排序算法之选择排序(代码片段)
初级排序算法本质是对要排序的数组进行嵌套循环,内层循环负责局部的排序,外层循环负责剩余的无序元素的递减。所以你只要理解嵌套循环和比较大小就能很快的掌握初级排序算法。选择排序一个无序的数组a=[0,4,6,3,8,2,3,9],... 查看详情
《图灵程序设计丛书算法》第4版.pdf
《图灵程序设计丛书:算法(第4版)》是Sedgewick之巨著,与高德纳TAOCP一脉相承,是算法领域经典的参考书,涵盖所有程序员必须掌握的50种算法,全面介绍了关于算法和数据结构的必备知识,并特别针对排序、搜... 查看详情
图灵程序设计丛书算法(第4版)pdf
...介 · · · · · ·本书全面讲述算法和数据结构的必备知识,具有以下几大特色。?算法领域的经典参考书Sedgewick畅销著作的最新版,反映了经过几十年演化而成的算法核心知识体系?内容全面全面论述排... 查看详情
排序算法模板
算法第4版publicclassexample publicstaticvoidsort(Comparable[]a)/*排序算法*/ privatestaticbooleanless(Comparablev,Comparablew) returnv.Comparable(w)<0; privatestaticvoidexch(Comparable[]a,inti,intj) C 查看详情
力扣_初级算法_树_4~5题_和_排序和搜索_2题_和动态规划_1~4题(代码片段)
C++小白所作...单纯记录一下自己刷力扣的学习心得 树_第4题:二叉树的层序遍历题目描述:给你一个二叉树,请你返回其按 层序遍历 得到的节点值。(即逐层地,从左到右访问所有节点)。举例:示例:二叉树:[3,9,2... 查看详情
算法第四版学习笔记之快速排序quicksort
软件:DrJava参考书:算法(第四版)章节:2.3快速排序(以下截图是算法配套视频所讲内容截图)1:快速排序2: 查看详情
初级排序算法1-定义排序规则(代码片段)
初级排序算法-定义排序规则排序就是将一组对象按照某种逻辑序列重新排列的过程.Tableofcontents介绍为什么学它排序算法类的模板验证性能评估介绍现在计算机的广泛使用使得数据无处不在,而整理数据的第一步通常就是进行排序... 查看详情
排序算法——选择排序
选择排序是排序方法中最简单效率最低的算法该方法会遍历(N2)/2:每次抽一位最小数或者最大数放在数组头部。再遍历抽取剩下的数组最小数如下所示:原数组:9,8,7,6,5,4,3,2,1第一轮:1,8,7,6,5,4,3,2,9第... 查看详情
初级算法java(代码片段)
初级算法1数组1.1删除排序数组中的重复项2字符串3链表4树5排序和搜索6动态规划7设计问题8数学9其他1数组1.1删除排序数组中的重复项给你一个有序数组nums,请你原地删除重复出现的元素,使每个元素只出现一次,返回删除后数... 查看详情
写给大家看的算法
第1章什么是算法第2章变量和数组第3章数据结构第4章学习算法基础第5章排序算法第6章搜索算法第7章其他算法第8章算法和计算机 第1章什么是算法 1.1算法其实就在身边 1.2算法是人类智慧的结晶 1.3了解算法对玩游... 查看详情
算法导论第2章参考答案与编程题选
系列地址:算法导论(CLRS)参考答案与配套编程题选2.1插入排序练习2.1-1原题为\(A=<31,41,59,26,41,58>\),每一次排序后变化如下:为了演示效果,所有值统一减\(10\).下面演示对\(A=<21,31,49,16,31,48>\)的排序过程:练习2.1-2重写... 查看详情
算法(algorithms)第4版练习2.1.4
EASYQUESTIONAESYQUESTIONAESYQUESTIONAESYQUESTIONAEQSYUESTIONAEQSUYESTIONAEEQSUYSTIONAEEQSSUYTIONAEEQSSTUYIONAEEIQSSTUYONAEEIOQSSTUYNAEEINOQSSTUYAEEINOQSSTUY 查看详情