`
liuxinyu95
  • 浏览: 30877 次
  • 性别: 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

    **归并排序（Merge Sort）详解** 归并排序是一种基于分治法的高效排序算法，由John W. Backus在1945年提出。它将一个大问题分解为两个或更多的小问题来解决，然后将小问题的结果合并，得到最终的解。归并排序在各种...

    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

    private static void merge(Comparable[] a, Comparable[] aux, int l, int m, int r) { // 复制原始数组到辅助数组 for (int k = l; k ; k++) { aux[k] = a[k]; } int i = l, j = m; for (int k = l; k ; ...

    排序算法-SortingAlgorithm-java.zip

    堆排序 1.选择排序 Selection Sort 2.冒泡排序 Bubble Sort 3.插入排序 Insertion Sort 4.归并排序 Merge Sort 5.快速排序 Quick Sort 6.堆排序 Heap Sort 7.总结 summary

    常用的十种java排序算法实现

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

    sort.cpp_排序算法演示程序_

    《sort.cpp：排序算法的深度探索与实践》 在编程领域，排序算法是基础且重要的概念，它在数据处理和数据分析中发挥着至关重要的作用。本文将深入探讨一个名为"sort.cpp"的程序，该程序旨在演示七种流行的排序算法，...

    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. ...

    SortAlgorithm.rar

    4. **快速排序**（Quick Sort）：由C.A.R. Hoare提出的快速排序是一种非常高效的排序算法，采用分治策略。它的工作原理是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小...

    常用的8个Python排序算法

    1. 冒泡排序（Bubble Sort） def bubble_sort(arr): ...5. 归并排序（Merge Sort） 6. 快速排序（Quick Sort） 7. 堆排序（Heap Sort） 8. 计数排序（Counting Sort） 解压密码 douge

    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...

    matlab开发-sort1m

    4. **快速排序（Quick Sort）**：基于分治策略的高效排序算法，选取一个“基准”元素，将数组分为两部分，小于基准的放左边，大于基准的放右边，再对这两部分递归排序。 5. **归并排序（Merge Sort）**：也是分治...

    C语言中的sort

    这个标签可能意味着你有一个名为`sort.c`的源代码文件，其中实现了某种排序算法。你可以用上述的编译和运行步骤来处理这个文件。 7. **关于文件`lab1`：** 这可能是练习或实验1的目录或文件，可能包含了关于排序...

    src5_sort.zip_algorithms

    "src5_sort.zip_algorithms"这个压缩包文件显然包含了多种经典的排序算法实现，包括冒泡排序、选择排序、插入排序、归并排序和快速排序。这些算法在实际编程中有着广泛的应用，尤其是在数据处理和分析中。 首先，...

    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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...

    java十大排序算法实现

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

    sort_demo.rar_DEMO_排序比较

    4. **快速排序**（Quick Sort）：通过选取一个基准元素并进行分区操作，将数组分为小于基准和大于基准两部分，然后递归地对这两部分进行排序。最好、最坏和平均时间复杂度分别是O(nlogn)、O(n^2)和O(nlogn)，空间...

    实验1代码_sort_caughtnxh_

    4. **快速排序(Quick_sort.py)**：快速排序是由C.A.R. Hoare提出的，使用了分治策略。它选取一个基准值，将数组分为两部分，一部分的元素都小于基准，另一部分都大于基准，然后再对这两部分递归进行快速排序。快速...

    Sort_show.rar_Hill-climbing_show_sortshowdemo_排序算法

    归并排序（Merge Sort）** 归并排序是分治法的一个典型应用，它将大问题分解为小问题，再合并小问题的解来得到最终解。归并排序总是保证稳定性和O(n log n)的时间复杂度，但需要额外的O(n)空间。 **5. 快速排序...

    sort-algorithm_java.rar_sort_快速排序

    5. 快速排序（Quick Sort）： 快速排序由C.A.R. Hoare在1960年提出，是一种采用分治法的高效排序算法。基本思想是选取一个基准值，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的...

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