`
阅: 3068 | 回: 3
发表于2015/7/30 14:40:54 楼主 
头像 等级:高手
积分:117
财富值:1.0
身份:普通用户
前言

顾名思义,所谓排序算法(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)
...
其它 ...
我的个性签名
发表于 2015/7/30 15:56:11   
头像 等级:学者
积分:88
财富值:2
身份:普通用户

谢谢分享


我的个性签名
发表于 2015/7/30 22:53:52   
头像 等级:传说级人物
积分:638
财富值:934
身份:普通用户
赞一个
我的个性签名
发表于 2015/8/23 23:06:50   
头像 等级:初学者
积分:3
财富值:-8
身份:普通用户

很好,多谢楼主

我的个性签名

快速回复

目前不允许游客发表,请 登录 注册 后再发贴。