常用排序方法（二）

在上篇博客中，已经详细介绍了插入排序和交换排序，下面会主要介绍选择排序。选择排序基本思想：每一次在n-i+1（i=1，2…，n-1）个记录中选取键值最小的记录作为有序序列的第i个记录。这个排序中我们主要应用的还是直接选择排序和堆排序两种选择排序方法。

一、直接选择排序

基本思想：在第i次选择操作中，通过n-i次键值间比较，从n-i+1个记录选出键值最小的记录，并和第i个记录交换。算法描述如下：

swap(R[min],R[i]）是将记录R[min]和R[i]交换。
   直接选择排序过程示例：
         初始关键字  [45 38 66 90 88 10 2545]
         第一次选择 10 [38 6690 88 45 2545]
         第二次选择 10 25 [6690 88 45 3845]
         第三次选择 10 25 38[90 88 45 6645]
         第四次选择 10 25 3845 [88 90  6645]
         第五次选择 10 25 384545 [90 66 88]
         第六次选择 10 25 384545 66 [90 88]
         第七次选择 10 25 384545 66 88 [90]
         排序结果     10 25 38 4545 66 88 90
   这个算法的时间复杂度为O（n2）.算法简单，容易实现，但是不适宜n较大的情况。同时值得注意的，直接选择排序是不稳定的。
二、堆排序
   未完待续...
3楼liutengteng130昨天 23:12
算法很有意思
2楼lishehe昨天 23:03
自考的知识挺重要的
1楼kanglix1an昨天 23:38
加油