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<s<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大时较好 |
来自 http://www.cnblogs.com/FlyingBread/archive/2009/02/27/636993.html
相关推荐
本文主要总结和比较了九种常见的排序算法：快速排序、归并排序、堆排序、Shell排序、插入排序、冒泡排序、交换排序、选择排序以及基数排序。 1. **快速排序**：快速排序是一种基于分治思想的高效排序算法，由C.A.R....
常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结
在这个名为“各种排序算法总结（ppt）”的资料中，我们将会深入探讨多种常见的排序算法，包括它们的基本原理、优缺点以及实际应用。** 首先，我们要了解排序的目的是为了使数据有序，这在数据处理和分析中具有广泛...
### 各种排序算法比较 #### 一、引言 排序是计算机科学中最常见的操作之一，在数据处理和信息检索等领域有着广泛的应用。本篇文章将详细介绍几种经典的排序算法，并对它们进行对比分析，以便读者能够更好地理解和...
这里我们将深入探讨几种常见的排序算法，并在VS2013环境下进行实现和比较。 1. 冒泡排序（Bubble Sort） 冒泡排序是一种简单的交换排序，它通过重复遍历待排序的数列，依次比较相邻元素并根据需要交换位置，直到...
本文将对几种常见的内部排序算法和外部排序算法进行详细总结。 首先，排序的基本定义是：给定一个包含n个记录的序列，其关键字序列分别为K1, K2, ..., Kn，如果存在一个排列p1, p2, p3, ..., pn，使得关键字满足非...
所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。...在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。
常用排序算法总结，包括插入排序(InsertionSort)，冒泡排序(BubbleSort)，选择排序(SelectionSort)，快速排序（QuickSort)， * 二路归并排序(MergeSort)，堆排序(HeapSort)。有每一种排序算法的复杂度分析以及实现...
数据结构各种算法总结，冒泡法等排序算法的比较，有助于更深刻的理解
C#排序算法总结涵盖了交换排序和插入排序两大类排序算法，其中交换排序包括了冒泡排序、选择排序和快速排序，而插入排序则涉及直接插入排序和折半插入排序。下面将详细介绍每种排序算法的实现原理、特点以及在C#中的...
### 各种排序算法的稳定性和时间复杂度总结 #### 排序算法的稳定性与时间复杂度概述 在计算机科学中，排序算法是基础且重要的组成部分，用于将一系列数据按照特定顺序排列。排序算法的效率通常由其时间复杂度决定...
《十大经典排序算法总结》 排序算法是计算机科学的基础，其设计思想和效率对软件的性能有着直接影响。本文主要探讨了十种经典的排序算法，包括它们的设计思路、优缺点以及适用场景，帮助我们理解排序算法的核心。 ...
【排序算法总结】 排序是计算机科学中的一项基本操作，它涉及到如何有效地重新排列一组数据，使其按照特定的顺序排列。本文将重点介绍八大排序算法，包括插入排序、希尔排序、交换排序、快速排序、选择排序、堆排序...
本资源"总结了各种排序算法，并用C++代码实现，并有演示"，提供了丰富的学习材料，包括不同类型的排序算法以及它们的C++实现，还有可能的可视化演示，帮助理解每种算法的工作原理。 首先，让我们逐一了解常见的排序...
本文将对几种常见的排序算法进行总结和比较，包括快速排序、归并排序和堆排序等，以便于理解它们的工作原理、性能特点以及适用场景。 1. **快速排序(QuickSort)** 快速排序是由英国计算机科学家C.A.R. Hoare提出...
排序算法是计算机科学中的基础概念，用于组织和整理数据，使其按照特定顺序排列。以下是对几种常见排序算法的详细说明： 1. 插入排序： 插入排序是一种简单的排序算法，其时间复杂度为O(n^2)。它通过将每个元素...
《数据结构课程设计：各种排序算法比较》 在数据结构的学习中，排序算法是一个重要的章节，它涉及到如何高效地组织和处理数据。本课程设计旨在深入比较和理解几种常见的排序算法，包括直接插入排序、冒泡排序、选择...