阅： 3354 | 回： 3
等级:高手
-
积分:117
-
财富值:1.0
-
身份:普通用户
前言
顾名思义，所谓排序算法（Sorting Algorithm）就是将一组数据按某种特定的顺序重新排列组织。显然，这一需要是我们在日常处理工作当中总是要用到的。这也是排序算法是计算机世界中最为重要的算法的原因。最为常见的顺序是 数值顺序 和 字符顺序。对于一些其它算法的优化，一个高效的排序算法是起决定性作用的，比如查找、合并等。
排序算法的分类与评价
顾名思义，所谓排序算法（Sorting Algorithm）就是将一组数据按某种特定的顺序重新排列组织。显然，这一需要是我们在日常处理工作当中总是要用到的。这也是排序算法是计算机世界中最为重要的算法的原因。最为常见的顺序是 数值顺序 和 字符顺序。对于一些其它算法的优化，一个高效的排序算法是起决定性作用的，比如查找、合并等。
排序算法的分类与评价
- 计算复杂度（Computational Complexity），包括最坏、平均、最佳情况，通常由数据元素的数量（n）来计算，而用大O符号来表达。理想的计算复杂度是 O(n)，但一般而言，好的性能是 O(n log n)，平均性能是 O(log^2 n)。
- 空间使用（Memory Usage），指除了待排序的源数据外，算法所需的额外的临时存储空间。通常将不使用或使用有限个（常数）元素O(1)额外空间的排序算法，称为原地排序算法（In Place Sorting），比如冒泡排序。
- 稳定性（Stability），如果一个排序算法对于源数据中两个排序关键值相同的元素，在排序后不改变其原有顺序的，则称这个排序算法是稳定的。比如以下对(2, 9) (1, 3) (2, 7) (3, 4)四个数字对按第一个数字排序时，稳定的算法则会得到 (1, 3) (2, 9) (2, 7) (3, 4)，而不稳定的算法则会得到 (1, 3) (2, 7) (2, 9) (3, 4)。
- 是否使用递归，通常程序语言都会对递归寄存器有所限制，一些早期的语言甚至不支持递归。
- 是否对比，多数的排序算法都会进行元素间的对比，但也有些算法是不用对比的，如计数排序。
-
排序方式，包括 插入、交换、选择、合并 等等。
| 排序方式 | 排序算法 |
| 交换排序（Exchange Sort） |
冒泡排序（Bubble Sort） 鸡尾酒排序（Cocktail Sort） 快速排序（Quick Sort） 梳排序（Comb Sort） ... |
| 选择排序（Selection Sort） |
选择排序（Selection Sort） 堆排序（Heap Sort） ... |
| 插入排序（Insertion Sort） |
插入排序（Insertion Sort） 希尔排序（Shell Sort） 二叉查找树排序（Binary Tree Sort） ... |
| 合并排序（Merge Sort） |
合并排序（Merge Sort） ... |
| 分配排序（Distribution Sort） |
计数排序（Counting Sort） 基数排序（Radix Sort） 桶排序（Bucket Sort） ... |
| 并发排序（Concurrent Sort） | ... |
| 混合排序（Hybrid Sort） |
内省排序（Introsort） ... |
| 其它 |
... |
我的个性签名
等级:学者
等级:传说级人物