一, 排序的概念与分类
排序的一般定义
排序是计算机内经常进行的一种操作 , 其目的是将一组 "无序" 的数据元素调整为 "有序" 的数据元素.
例如 : 将下列关键字序列
52, 49, 80, 36, 14, 58, 61, 23, 97, 75
调整为
14, 23, 36, 49, 52, 58, 61 ,75, 80, 97
排序的数学定义
假设含有 n 个数据元素的序列为 {R1 , R2 , ..., Rn }, 其相应的关键字序列为 { K1 , K2 , ..., Kn }, 这些关键字相互之间可以进行比较 , 即在它们之间存在着这样一个关系:
Kp1 <= Kp2 <= ...<=Kpn
按此固有关系将上式记录序列重新排列为
{ R p1 , R p2 , ... ,R pn }
的操作称作 排序 .
排序的稳定性
如果在序列中有两个数据元素 r[i] 和 r[j], 它们的关键字 k[i ] ==k[j], 且在排序之前, 对象 r[i] 排在 r[j]. 如果在排序之后 , 对象 r[i] 仍在对象 r[j] 的前面, 则称这个排序方法是稳定的.
多关键字排序
排序时需要比较的关键字多余一个
排序结果首先按关键字 1 进行排序
当关键字 1 相同时按关键字 2 进行排序
......
当关键字 n-1 相同时按关键字 n 进行排序
排序中的关键操作
比较: 任意两个数据元素通过比较操作确定先后次序
交换: 数据元素之间需要交换才能得到预期结果
内排序和外排序
内排序: 整个排序过程不需要访问外存便能完成
外排序: 待排序的数据元素数量很大 , 整个序列的排序过程不可能在内存中完成
排序的审判
时间性能: 关键性能差异体现在比较和交换的数量
辅助存储空间: 为完成排序操作需要的额外的存储空间; 必要时可以 "空间换时间"
算法的实现复杂性: 过于复杂的排序法会影响代码的可读性和可维护性 , 也可能影响排序的性能
二, 基本的排序算法
选择排序
每一趟 ( 例如第 i 趟 , i = 0, 1, ... , n- 2) 在后面 n-i 个待排的数据元素中选出关键字最小的元素 , 作为有序元素序列的第 i 个元素.
插入排序
当插入第 i(i>=1) 个数据元素时, 前面的 V[0], V[1], ... , V[i-1] 已经排好序 . 这时 , 用 V[i] 的关键字与 V[i-1], V[i-2], ... 的关键字进行比较 , 找到插入位置即将 V[i] 插入 , 原来位置上的对象向后顺移.
冒泡排序
设待排数据元素序列中的元素个数为 n. 最多作 n-1 趟, i = 1, 2, ... ... , n-1. 在第 i 趟中从后向前, j = n-1, n-2, ... ... , i, 两两比较 V[j-1] 和 V[j] 的关键字. 如果发生逆序, 则交换 V[j-1] 和 V[j].
希尔排序
将待排序列划分为若干组, 在每一组内进行插入排序, 以使整个序列基本有序, 然后再对整个序列进行插入排序.
将 n 个数据元素分为 d 个子序列:
- {
- R[1],R[1+d],R[1+2d],...,R[1+kd]
- }
- {
- R[2],R[2+d],R[2+2d],...,R[2+kd]
- }
- ...
- {
- R[d],R[2+d],R[3+2d],...,R[(k+1)d]
- }
其中, d 称为增量, 它的值在排序过程中从大到小逐渐缩小, 直至最后一趟排序减为 1.
快速排序
1) 任取待排序序列中的某个数据元素 ( 例如: 第一个元素) 作为基准, , 按照该元素的关键字大小将整个序列划分为左右两个子序列:
左侧子序列中所有元素都小于或等于基准元素
右侧子序列中所有元素都大于基准元素
基准元素排在这两个子序列中间
2) 分别对这两个子序列重复施行上述方法, 直到所有的对象都排在相应位置上为止 .
归并排序
将两个或两个以上的有序序列合并成一个新的有序序列
V[1] ... V[m] 和 V[ m +1] ... V[n] -------------------> V[1] ... V[n]
这种归并方法称为 2 路归并.
总结:
希尔排序 , 快速排序和归并排序将排序算法的时间复杂度提高到了 O(n*logn)
希尔排序和快速排序的排序结果是不稳定的
算法实现源码
来源: http://www.bubuko.com/infodetail-3109034.html