软考--数据结构--八种常用常考的内部排序算法

1.直接插入（适用于键表结构）

从第二个关键字开始，逐一进行比较，插入合适位置

最好：每趟只需一次比较且不需要移动

最坏：总比较次数  n(n-1)/2 

总移动次数  (n+3)(n-2)/2

 

2.希尔排序/缩小增量排序（直接插入的升级版）

d2与d3的取值问题：只须满足 d1 > d2 >d3 && dn=1

分组后进行直接插入排序

 

3.简单选择排序

for（）{

找（选择）最小关键字并放到第一位

}

 

4.堆排序

堆分为小根堆和大根堆（堆顶为最大元素）

步骤①：对数据建立完全二叉树，按层次遍历一一填入得到初始堆

数据：{46，79，56，38，40，84}

初始堆：{84，79，56，38，40，46}

步骤②：调整为新堆

从n/2开始看

假设输出堆顶元素，以堆中最后一个元素替代，重新整理成新堆

 

5.冒泡交换排序

从最后一个元素开始，逐一与前一元素比较，大则跳下一元素，小则交换位置。

 

6.快速排序

数据：{57，68，59，52，72，28，96，33，24，19}

①设两个指针i、j

基准a = 57

i指向57   j指向19

i与j比较  i>j  交换位置

得{19，68，59，52，72，28，96，33，24，57}

②i向后指向68  继续比较  

i>j  交换位置

得{19，57，59，52，72，28，96，33，24，68}

③j向前指向24 

重复以上比较交换，直到i于j相等

得{【19，24，33，52，28】，57，【96，72，59，68】}

④将 b = {19，24，33，52，28}  和 c= {96，72，59，68}进行如上的操作

 

7.归并排序（使用合并操作完成排序的算法）

二路合并（二不唯一，看数据）：

两两合并比较

合并后的组可以用不同的排序方法

 

8.基数排序（十分有趣）

数据 = {135，242，192，93，354，11，24，19}

①把数据按个位排序得到新的排序

得 {11，242，192，93，24，135，345，19}

②把个位排序数据按十位排序得到新的排序

得 {11，19，24，135，242，345，192，93}

③将新的序列按百位排序

得 {11，19，24，93，135，192，242，345}

 

总结：

 

1.若待排序的记录数目n较小，可采用直接插入和简单选择。

2.若待排序记录按关键字基本有序，可以采用冒泡交换或者直接插入。

3.当n很大且关键字位数较少，可以采用链式基数排序。

4.若n较大，则可选择时间复杂度为O（nlogn）的排序方法。