`
liuxinyu95
  • 浏览: 30059 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Quick sort V.S. Merge sort

quicksortmergesortfunctionalhaskellC 
阅读更多
终于写完了这一章

本章全面地涉及了quick sort和merge sort的方方面面。同其他章节一样，即覆盖传统的imperative算法，也覆盖functional（函数式）算法。

首先展示的是著名的只有2行的Haskell快速排序算法。之后，针对Partition给出了一些小的改进。并且用两种方法严格证明了快速排序的平均性能。此后，我给出了各种著名的工程方法：2路partition, 3路parition (ternary quick sort)，3点中值法，随机快速排序等等，最后通过deforestation给出快速排序和树排序的关系。

为了解决快速排序的worst case问题，本章接下来介绍merge sort。首先介绍basic version和复杂度分析。之后我给出O(N lg N)性能的in-place merge sort算法。
此后介绍针对单向链表的merge sort和奇偶-partition，前者用于imperative实现，后者用于functional实现。然后，我介绍nature merge sort并给出bottom-up merge sort可以认为是nature merge sort的一种特殊形式。

最后，我们简单介绍并发merge sort和quick sort。作为结尾，我介绍一种有趣的排序分类方法。

全文可以在下面连接下载。

https://github.com/liuxinyu95/AlgoXY/blob/algoxy/preview/dcsort-en.pdf?raw=true
分享到：
| POJ 1061青蛙的约会题解
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    merge-quick-sort.rar_algorithms_merge sorting

    quick sorting algorithms

    src5_sort.zip_algorithms

    sort algorithms... bubble, selection, insertion, merge, quick....

    ads.rar_Quick

    this rar file conatins all sorting methods such as heap sort,merge sort,insertion sort,quick sort....with simple coding

    slides for merge and quick sort

    非常通俗易懂的merge归并，和quick快速排序算法讲解。并含代码。

    Data.Structures.and.Algorithms.USING.C

    24. Merge Sort Algorithm 25. Shell Sort 26. Quick Sort GRAPH DATA STRUCTURE 27. Graphs 28. Depth First Traversal 29. Breadth First Traversal TREE DATA STRUCTURE 30. Tree 31. Tree Traversal 32. ...

    algorithm.zip

    merge_sort 19s: 19820ms: 19820072us radix_sort 28s: 28092ms: 28092259us heap_sort 56s: 56574ms: 56574802us shell_sort 71s: 71964ms: 71964163us radix_linklist_sort2 139s: 139973ms: 139973427us...

    Data Structure and Algorithms

    8.2 Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 8.3 Quick Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 8.4 Insertion Sort . . . . . . . . . . . ....

    Data Structures Succinctly Part 1

    Data Structures Succinctly Part 1 Table of Contents The Story behind the Succinctly Series of Books ......................................................................................

    New folder1.zip_Quick_assd

    you are very smart bubble sort merge sort quick sort

    Animation_Sort_Java_Graphic.rar_Quick_java sort animation_sortin

    Sorting (Bubble, Selection, Insertion, Merge, Quick), using Java Graphic, with detail animation and explanation.

    python programming

    3.5 Handling Large Numbers: Long Ints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.6 Type Conversions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...

    searching, sorting (part 1 - selection sort, bubble sort)

    关于insertion sort， merge sort， quick sort 等。 USC Bill Cheng's PPT

    java十大排序算法实现

    4. 快速排序（Quick Sort） 5. 归并排序（Merge Sort） 6. 堆排序（Heap Sort） 7. 计数排序（Counting Sort） 8. 桶排序（Bucket Sort） 9. 基数排序（Radix Sort） 10. 希尔排序（Shell Sort）

    Python 实现十大经典排序算法-LeetCode案例版

    归并排序（Merge Sort）6. 快速排序（Quick Sort）7. 堆排序（Heap Sort）8. 计数排序（Counting Sort）9. 桶排序（Bucket Sort）10. 基数排序（Radix Sort）三、算法总结 十大经典排序算法 一、 引言 授人以鱼不如...

    sorts code

    bin-sort,bubble-sort,insert-sort,merge-sort,quick-sort and shill-sort

    普林斯顿算法课程 Robert Sedgewick

    insertion sort, shell sort, quick sort, merge sort, heap sort), searching algorithms (Binary search tree, Red-Black BST, hashing), 所以程序都用java实现，代码风格简洁，很值得学习。

    Mentorship-2019:指导@ 2019

    指导计划 演算法 ...│ Sort-Merge.js │ Sort-Odd_Even.js │ Sort-Quick.js │ Sort-Selection.js │ README.md │ └───Big O Notation │ README.md │ └───assets 数据结构 .

    经典算法的C#源码实现

    经典排序算法 - 快速排序Quick sort 经典排序算法 - 桶排序Bucket sort 经典排序算法 - 插入排序Insertion sort 经典排序算法 - 基数排序Radix sort 经典排序算法 - 鸽巢排序Pigeonhole sort 经典排序算法 - ...

    知名公司数据结构笔试题及答案

    a quick sort b.buble sort c.merge sort 5.哪种结构，平均来讲，获取一个值最快 a. binary tree b. hash table c. stack 6.一个二叉树的三种遍历方法的输出结果 7.链表按升序打印每打印完一个节点就将该...

    数据结构常用算法c++实现

    Quick sort Merge sort Heap sort Double linked list Skip list Self-organized linked-list ops (move-to-front, move-ahead-one) Largest common sequence Binary search tree Dynamic order statistics Red-...

Magicbox
Global site tag (gtag.js) - Google Analytics