基本的排序算法

xaut3

这个属于 算法啦！好东西
1 o+ H( @: n4 I/ \4 s; N# q
1. 排序的基本概念
　　假定排序对象为若干记录组成的一个集合，每个记录包含若干个字段，选取其中一个或多个字段为排序码。我们暂时假设排序码的类型为整数类型。
  U5 ~& l$ Q! C; D! ^2 w/ Y) f2 M　　“正序”序列：待排序序列正好符合排序要求。
' v( |/ X/ }( v　　“逆序”序列：把待排序序列逆转过来，正好符合排序要求。
　　排序的稳定性：排序码相同的记录经过排序后相对次序保持不变，则这种排序方法称为是“稳定的”，否则是不稳定的。
" D' k7 D  L7 q! u" G( F9 x4 ^( [2. 分类
　　按排序中涉及的存储器不同
　　1）内部排序是把待排数据元素全部调入内存中进行的排序。
1 c( f1 P' D6 f7 r　　2）外部排序是因数量太大，把数据元素分批导入内存，排好序后再分批导出到磁盘和磁带外存介质上的排序方法。
" C1 u' E) R9 _" R- N* H  Y　　按照排序方法分类
. S* C4 _- k5 c; A! D& d6 f3 F  [, I. M　　1）插入排序：直接插入、二分法插入、表插入、Shell排序
　　2）选择排序：直接选择、堆排序
1 u# \; m) V; g5 D; N" C2 X　　3）交换排序：冒泡排序、快速排序
　　4）分配排序：基数排序
　　5）归并排序：二路归并排序
! C: {+ V' \. _3、排序算法的评价
% K8 b4 E. F( J1 ], E( s1 |7 h　　1）时间复杂度:分析记录关键字的比较次数和记录的移动次数  （重要评价标准）
- V$ i; o! k* |* k3 s　　2）空间复杂度:算法中使用的内存辅助空间
　　3）排序的稳定性
$ {; G8 q2 j- E4 w- w6 i" g9 T+ i4 c　　4）算法本身的复杂程度
/ s4 _: }' Y7 v  |! T8 F
一、选择排序与堆排序
1.直接选择排序
1 l& I* G: E5 f3 i  a7 \　　思路比较简单:即依次从剩余记录中选取最小的
, G: D0 l- o6 |/ I% s* B2.堆排序

　　利用堆的思想,建立一个最大堆,把堆顶的元素(最大值)拿掉,再重新建堆,依次递归