1 快速排序（QuickSort）
快速排序是一个就地排序，分而治之，大规模递归的算法。从本质上来说，它是归并排序的就地版本。快速排序可以由下面四步组成。
（1） 如果不多于1个数据，直接返回。
（2） 一般选择序列最左边的值作为支点数据。
（3） 将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。
（4） 对两边利用递归排序数列。
快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。
2 归并排序（MergeSort）
归并排序先分解要排序的序列，从1分成2，2分成4，依次分解，当分解到只有1个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组。
3 堆排序（HeapSort）
堆排序适合于数据量非常大的场合（百万数据）。
堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。
堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。
4 Shell排序（ShellSort）
Shell排序通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序，以减少数据交换和移动的次数。平均效率是O(nlogn)。其中分组的合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。
Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相对比较简单，它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。
5 插入排序（InsertSort）
插入排序通过把序列中的值插入一个已经排序好的序列中，直到该序列的结束。插入排序是对冒泡排序的改进。它比冒泡排序快2倍。一般不用在数据大于1000的场合下使用插入排序，或者重复排序超过200数据项的序列。
6 冒泡排序（BubbleSort）
冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法。它通过一趟又一趟地比较数组中的每一个元素，使较大的数据下沉，较小的数据上升。它是O(n^2)的算法。
7 交换排序（ExchangeSort）和选择排序（SelectSort）
这两种排序方法都是交换方法的排序算法，效率都是 O(n2)。在实际应用中处于和冒泡排序基本相同的地位。它们只是排序算法发展的初级阶段，在实际中使用较少。
8 基数排序（RadixSort）
基数排序和通常的排序算法并不走同样的路线。它是一种比较新颖的算法，但是它只能用于整数的排序，如果我们要把同样的办法运用到浮点数上，我们必须了解浮点数的存储格式，并通过特殊的方式将浮点数映射到整数上，然后再映射回去，这是非常麻烦的事情，因此，它的使用同样也不多。而且，最重要的是，这样算法也需要较多的存储空间。
9 总结
下面是一个总的表格，大致总结了我们常见的所有的排序算法的特点。
| 排序法 |
平均时间 |
最差情形 |
稳定度 |
额外空间 |
备注 |
| 冒泡 |
O(n2) |
O(n2) |
稳定 |
O(1) |
n小时较好 |
| 交换 |
O(n2) |
O(n2) |
不稳定 |
O(1) |
n小时较好 |
| 选择 |
O(n2) |
O(n2) |
不稳定 |
O(1) |
n小时较好 |
| 插入 |
O(n2) |
O(n2) |
稳定 |
O(1) |
大部分已排序时较好 |
| 基数 |
O(logRB) |
O(logRB) |
稳定 |
O(n) |
B是真数(0-9)，
R是基数(个十百)
|
| Shell |
O(nlogn) |
O(ns) 1<2 |
不稳定 |
O(1) |
s是所选分组 |
| 快速 |
O(nlogn) |
O(n2) |
不稳定 |
O(nlogn) |
n大时较好 |
| 归并 |
O(nlogn) |
O(nlogn) |
稳定 |
O(1) |
n大时较好 |
| 堆 |
O(nlogn) |
O(nlogn) |
不稳定 |
O(1) |
n大时较好 |
/******************************************************************************************
*【Author】：flyingbread
*【Notice】：本文为原创技术文章，首发博客园个人站点(http://flyingbread.cnblogs.com/)，转载和引用请注明作者及出处。
******************************************************************************************/
分享到：
相关推荐
### 各种排序算法小结 #### 一、引言 排序算法是在计算机科学中非常基础且常用的一类算法。由于在实际应用中往往需要处理大量数据，因此对排序算法的效率有着较高要求。通常，我们会关注算法的时间复杂度来评估其...
2. **归并排序**：归并排序是基于分治法的排序算法，将数据不断分成两半，直到每个子序列仅包含一个元素，然后将这些元素按顺序合并回原序列。归并排序具有稳定性，但需要额外的空间来存储子序列。 3. **堆排序**：...
数据结构中的排序算法是计算机科学中的重要组成部分，它涉及到如何高效地组织和处理大量数据。以下是对各种排序算法的详细解释： 1. **插入排序**： - **直接插入排序**：这是一种简单的排序方法，通过将每个元素...
查找算法和排序算法小结 本文总结了常见的查找算法和排序算法，包括顺序查找、二分查找、选择排序、冒泡排序、二分排序、插入排序、希尔排序、堆排序、归并排序等。 一、查找算法 1. 顺序查找（Sequential Search...
各种排序算法的稳定性和时间复杂度小结.doc
排序算法是计算机科学中基础且重要的概念，它们用于组织和整理数据，使得数据按照特定顺序排列。本篇文章将概述几种常见的排序算法，包括快速排序、归并排序、堆排序、Shell排序、插入排序、冒泡排序、交换排序、...
几乎把网上的排序算法小结找遍了，简单地小结一下算法的思路（不含代码，只是用易懂的话说清楚算法是怎么做的），算法时间复杂度和空间复杂的求法（用理解的方式而不是分析代码），各种排序算法的优缺点，稳定与否...
【排序算法的稳定性和时间复杂度】 排序算法是计算机科学中的基本操作，它涉及将一组数据按照特定的顺序排列。稳定性和时间复杂度是衡量排序算法性能的重要指标。 **稳定性**指的是排序过程中相等的元素在排序后...
这篇博客“常用排序算法小结（附Java实现）”提供了一种深入理解并掌握常见排序算法的途径，尤其对于Java开发者来说非常实用。文章可能涵盖了如冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等多种经典...
选择排序是一种简单直观的排序算法，它的工作原理可以分为以下几个步骤： 1. **理解选择排序**：选择排序从数组的第一个元素开始，遍历数组寻找当前未排序部分的最小（或最大）元素。找到后，将这个最小（或最大）...
### 排序算法小结讲解+源码 #### 一、引言 排序算法作为计算机科学中的基础且常用算法，在实际应用中具有重要意义。随着数据量的不断增加，对排序算法的效率提出了更高要求。本文将从简单排序算法出发，逐步过渡到...
### 各种经典排序算法小结---必知必会 #### 概述 排序算法是计算机科学中的一个重要组成部分，主要用于将一系列数据按照特定顺序（升序或降序）进行排列。排序算法的学习对于理解算法复杂度、算法设计原理以及提高...
### 排序算法的稳定性和时间复杂度小结 #### 一、引言 排序算法是计算机科学中的基本算法之一，广泛应用于各种场景之中。排序算法不仅关注排序的速度（时间复杂度），还关注排序过程中是否能够保持相等元素原有的...
本篇内容主要总结了多种内部排序算法，包括它们的特点、效率以及适用场景。 1. 选择排序（Selection Sort）：不稳定排序，平均时间复杂度为O(n^2)。它通过反复遍历待排序的数据，每次找到最小（或最大）的元素，...
在高级语言的执行速度上，c是最快的，c++其次，而java和c#是最后的。Java和c#流行，主要的一个原因是可以跨平台。
### 排序学习总结 #### 一、概述 本文旨在对常见的排序算法...例如，对于小规模数据，可以直接使用简单排序算法如插入排序或选择排序；而对于大规模数据，则应考虑使用更高效的排序算法，如快速排序或归并排序等。
5．5 小结、历史与文献． ． ． 297 第6 章查找． ． ． ． ． ． ． ． 306 6．1 顺序查找． ． ． ． ． ． ． 308 6．2 通过键的比较进行查找． ．318 6．2．1 查找有序表． ． ． ． ． 318 6．2．2 二叉树...