`

【编程珠玑】第十一章 排序 (插入排序和快速排序的深度优化)

 
阅读更多

一,概述

1)插入排序

要找到合适的位置,需要判断前一个元素比t小而后一个元素比t大。然后将t插入正确位置。

比较a[j-1] 跟 a[j] 的关系很关键


isort1: 没有到达最终位置,就交换该元素和它前面的元素

#include <algorithm>

  isort2:将库函数替换


isort3:减少移动次数



 2)快速排序
  qsort1:O(nlog(n)时间和O(logn)的栈空间


qsort2:双向划分避免所有元素都相等时候的最坏情况



思路:n个相同元素组成的数组,插入排序性能最好(每个元素需要移动的距离都为0),时间复杂度为o(n)。 快速排序的性能则很糟糕,n-1次划分每次划分都需要0(n)的时间来去掉一个元素,所以时间复杂度为O(n*n) 采取的对策是:采取两个内循环,第一个向右移过小元素,遇到大元素停止,第二个左移,遇到小元素停止。然后交换。 当遇到相同的元素时,停止扫描,交换a[i] 和 a[j]的值。最坏时间复杂度O(nlogn)


 qsort3:利用随机位置的数做轴,会使数组的快速排序得到优化。

【知识点】产生某个范围随机数方法:
  比如要产生 [60-99]的随机数.
  使用rand()函数产生的随机数是从0(包括0)开始的
  我们思考:

  [ 0,?] + 60 =[60,99]
  很明显,?应该是39.产生[0, 39]的随机数可以这样做:rand() % 40 得解.




rand()%(end-start)+start;


注意:因为rand()函数是按指定的顺序来产生整数,因此每次执行上面的语句都打印相同的值,所以说C语言的随机并不是真正意义上的随机,有时候也叫伪随机数


二,习题
     2)Lomuto的快速排序算法如下
       
      采用哨兵优化后算法:(减少了内循环测试)

      
        5)没完全理解题意
        
        6)选择排序
          希尔排序:选择排序的优化

        9)线性时间寻找第k小元素
          思路:快速排序选择一个pivot对数组进行划分,左边小于pivot,右边大于等于pivot,所以我们计算左边小于pivot(加上pivot)的个数count总共有多少,如果等于k,正是我们所要的,如果大于k,说明第k小的数在左边,那就在左边进行我们的递归;否则,在右边,那么说明右边的第k-count小的数就是我们所要的,在右边进行我们的递归。
          算法实现一:

算法实现二:


14)算法实现如下:









分享到:
评论

相关推荐

    编程珠玑 编程珠玑 编程珠玑 编程

    书中涵盖了一系列实用的编程问题和解决方案,这些“珠玑”般的编程智慧,无论对于初学者还是经验丰富的开发者,都有着极高的参考价值。 编程珠玑的核心概念之一是数据结构与算法的选择和设计。书中的例子多以实际...

    编程珠玑源码下载编程珠玑书后源代码

    《编程珠玑》是计算机科学领域的一本经典之作,由Jon Bentley 编著,它以其深入浅出的方式探讨了程序设计的问题和解决方案,尤其在数据结构、算法优化以及问题解决策略方面有着独到的见解。这本书的源代码是作者为了...

    编程珠玑之位图排序

    输入:一个最多包含n个正整数的文件,每个数都小于n,其中n=10^7,。如果在输入文件中有任何整数重复出现就是致命错误。没有其他数据与该整数关联。 输出:按升序排列的输入整数列表。 约束:最多有(大约)1MB的...

    编程珠玑 编程珠玑续

    《编程珠玑》和其续篇是两部深受程序员喜爱的经典著作,主要涵盖了程序设计、算法分析和数据结构等核心编程领域。这两本书以其深入浅出的讲解方式和丰富的实例,帮助读者提升编程技巧和解决问题的能力。 在《编程...

    编程珠玑 第2版(修订版)_编程珠玑修订_资料_

    《编程珠玑》一书将这些技巧和经验整理成章,涵盖了算法、数据结构、性能优化、代码质量等多个方面,是程序员自我提升的重要参考资料。书中强调的问题求解策略和程序设计思想,对于初学者和资深开发者都有很大的启发...

    编程珠玑.pdf

    第11章 图形化输出 103 11.1 实例研究 103 11.2 显示结果取样 105 11.3 原理 107 11.4 习题 108 11.5 深入阅读 110 11.6 拿破仑远征莫斯科(边栏) 110 第12章 对调查的研究 113 12.1 有关民意调查的问题 113 12.2 ...

    编程珠玑(PDF带目录)

    目录通常包括各个章节的标题,可能包括:引言、基础算法(如冒泡排序、插入排序、快速排序)、高级数据结构(如堆、树、图)、搜索算法(如二分查找、广度优先搜索、深度优先搜索)、动态规划、贪心算法等。...

    编程珠玑源代码

    2. 算法:源代码中包含排序算法(如冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序)、查找算法(如顺序查找、二分查找、哈希查找)以及图算法(如深度优先搜索、广度优先搜索)。这些算法是解决问题的...

    编程珠玑pdf+源代码

    1. **排序与搜索算法**:《编程珠玑》详细讲解了各种排序算法,如插入排序、选择排序、快速排序、归并排序以及堆排序,以及它们的性能分析。同时,书中也涉及到了查找算法,如二分查找和哈希表的应用,这些都是面试...

    编程珠玑之第二章questionC 测试数据

    在编程领域,"编程珠玑"是一本深受程序员喜爱的经典著作,它深入浅出地探讨了计算机科学中的算法和设计技巧。"第二章questionC"提及的问题是关于"求变位词",这是一个常见的字符串处理问题,涉及到字符统计、排序...

    编程珠玑(第二版)答案

    根据提供的标题“编程珠玑(第二版)答案”和描述“编程珠玑(第二版)答案”,我们可以推测出这是关于《编程珠玑》这本书的相关解答资料。《编程珠玑》是一本经典的计算机科学书籍,作者为Jon Bentley。本书旨在...

    编程珠玑(续)

    《编程珠玑(续)》是计算机...书中涵盖了程序员操纵程序的技术、程序员取舍的技巧、输入和输出设计以及算法示例,这些内容组成一个有机的整体,如一串串珠玑展示给程序员。  《编程珠玑(续)》适合各级程序员阅读参考。

    《编程珠玑》(Programming Pearls)课本和习题代码实现

    5. **column11.cpp**: 第十一章可能涵盖了数据压缩和编码技术,如霍夫曼编码(Huffman Coding)或LZW编码,这些都是处理大量数据的有效手段。 6. **column12.cpp**: 第十二章可能涉及到错误检测和纠正,比如奇偶...

    编程珠玑 第二版 修订版

    第11章 排序 109 11.1 插入排序 109 11.2 一种简单的快速排序 110 11.3 更好的几种快速排序 113 11.4 原理 115 11.5 习题 116 11.6 深入阅读 117 第12章 取样问题 119 12.1 问题 119 12.2 一种解决方案 ...

    编程珠玑中文版

    2. **排序与查找**:讨论了多种排序算法(如插入排序、快速排序、归并排序)和查找算法(如二分查找),以及它们的性能分析和优化。 3. **动态规划**:书中通过实例展示了如何利用动态规划解决复杂问题,例如背包...

    编程珠玑(经典)

    《编程珠玑》是计算机科学领域的一本经典著作,作者是Jon Bentley。这本书以其深入浅出的讲解方式,探讨了程序设计中的一些核心问题,并提供了许多实用的编程技巧和算法,被誉为程序员的“智慧之石”。它不仅仅是一...

    编程珠玑 第二版 修订版 epub

    总的来说,《编程珠玑》第二版修订版是一部深度和广度并重的编程指南,无论你是初学者还是经验丰富的开发者,都能从中获得启发和提升。通过学习这本书,你不仅可以提升编程技能,还能培养出解决问题的敏锐直觉和良好...

    编程珠玑 Programming Pearls 第二版(中文版+源代码)

    《编程珠玑》是计算机科学领域的一本经典之作,作者是Jon Bentley,它以其独特的视角和深入浅出的讲解方式,向读者展示了编程艺术的精髓。这本书的第二版更是深受程序员和计算机科学家们的喜爱,因为它不仅涵盖了...

    编程珠玑续本

    编程珠玑续、编程珠玑续本、编程珠玑续本、编程珠玑续本

Global site tag (gtag.js) - Google Analytics