基本的排序算法

xaut3

这个属于 算法啦！好东西
! P  W: r% |5 }' |- g! i
1. 排序的基本概念
　　假定排序对象为若干记录组成的一个集合，每个记录包含若干个字段，选取其中一个或多个字段为排序码。我们暂时假设排序码的类型为整数类型。
4 T' R0 p' ?' P: l　　“正序”序列：待排序序列正好符合排序要求。
" @/ R0 i1 m* M5 k5 c　　“逆序”序列：把待排序序列逆转过来，正好符合排序要求。
0 f* _" {7 d- ~* R8 j$ h5 ^　　排序的稳定性：排序码相同的记录经过排序后相对次序保持不变，则这种排序方法称为是“稳定的”，否则是不稳定的。
  Y! t- j; f$ A- g; b  w1 R: p) t$ m2. 分类
! p  u0 [2 b$ T, @　　按排序中涉及的存储器不同
　　1）内部排序是把待排数据元素全部调入内存中进行的排序。
3 L# x, q2 D7 [* [7 `/ A/ a　　2）外部排序是因数量太大，把数据元素分批导入内存，排好序后再分批导出到磁盘和磁带外存介质上的排序方法。
　　按照排序方法分类
　　1）插入排序：直接插入、二分法插入、表插入、Shell排序
7 a* y# N" {0 z6 [9 D2 W# U　　2）选择排序：直接选择、堆排序
　　3）交换排序：冒泡排序、快速排序
1 ]: ^% _8 O  O1 [　　4）分配排序：基数排序
3 M! W( U$ y+ b( f1 C　　5）归并排序：二路归并排序
& m) j. Y+ }" L1 @6 m3、排序算法的评价
& y0 R4 X3 G. J' ]7 E* A1 A8 S. w  t) P　　1）时间复杂度:分析记录关键字的比较次数和记录的移动次数  （重要评价标准）
6 D0 U+ q( R( E　　2）空间复杂度:算法中使用的内存辅助空间
1 }6 ^& a! W' s9 ^6 m2 [! [2 M　　3）排序的稳定性
5 r! K& \7 x1 B) J- q$ g　　4）算法本身的复杂程度

4 K- u9 F! l- y! v8 D9 `' C8 U* M一、选择排序与堆排序
+ Y+ K- h' Q' k9 G: P+ y0 w1.直接选择排序
6 M7 v4 q) b. ~: W; ~3 I　　思路比较简单:即依次从剩余记录中选取最小的
2.堆排序
5 p+ G! Z; ~  T) c$ t* v
　　利用堆的思想,建立一个最大堆,把堆顶的元素(最大值)拿掉,再重新建堆,依次递归