数据结构中几种排序算法分析比较

数据结构中几种排序算法比较分析

目录

1 插入排序..........................................................................................................................................2

1.1 直接插入排序.......................................................................................................................2

1.1.1 基本思想.................................... ............. ............. ............. ............. ............. ............. 2

1.1.2 复杂度分析.................................... ............. ............. ............. ............. ............. .........2

1.1.3 稳定性分析.................................... ............. ............. ............. ............. ............. .........3

1.2 希尔排序...............................................................................................................................3

2.1.3 稳定性分析.................................... ............. ............. ............. ............. ............. .........5

2.2 快速排序...............................................................................................................................5

2.2.1 基本思想.................................... ............. ............. ............. ............. ............. ............. 5

2.2.2 复杂度分析.................................... ............. ............. ............. ............. ............. .........5

2.2.3 稳定性分析.................................... ............. ............. ............. ............. ............. .........5

3 选择排序..........................................................................................................................................6

3.1 直接选择排序.......................................................................................................................6

3.3.2 复杂度分析.................................... ............. ............. ............. ............. ............. .........6

3.3.3 稳定性分析.................................... ............. ............. ............. ............. ............. .........6

3.2 堆排序...................................................................................................................................7

5 分配排序（多关键字排序）..........................................................................................................8

数据结构中几种排序算法比较分析

1 插入排序

1.1 直接插入排序

1.1.1 基本思想

假设数组的前i个结点序列a1，a2,……，ai-1是已排序好的，称为有序区，

i后面的n-i+1个序列ai,ai+1,……,an是无序区。对结点ai在这有序结点列中找

插入位置，并将ai插入，而使i个结点a1，a2，……，ai-1也变成排序的，成为

新的有序区。依次对i=2，……，n分别执行这样的插入步骤, 最终实现线行表

比较次数的最大值=

数据结构中几种排序算法比较分析

1.1.3 稳定性分析

1.2 希尔排序

1.2.1 基本思想

{a1，a2，……，ai，ai+1，……，a2i，a2i+1，……，a3i，a3i+1，

……，an}以一定的增量间隔h 分割成多个子序列{ a1，ai，a2i，a3i，

长i，对于每一个步长i下的各个子序列进行同样方法的排序，直到步长为1时再

但是Knuth的统计结果是，平均比较次数和对象平均移动次数在 与