各种排序的比较及其实现

目录

各种排序的比较及其实现 ............................................................................................................... 1

1. 插入类排序： ................................................................................................................... 1

1.1 直接插入排序： ....................................................................................................... 1 1.2 折半插入排序: .......................................................................................................... 2 1.3 shell（希尔）排序: .................................................................................................. 2 2.

交换类排序: ...................................................................................................................... 3 2.1 冒泡排序: .................................................................................................................. 3 2.2 快速排序: .................................................................................................................. 4 3.

选择类排序: ...................................................................................................................... 5 3.1 直接(简单)选择排序： ............................................................................................ 5 3.2 堆排序： ................................................................................................................... 6 4.

归并类排序: ...................................................................................................................... 7 4.1 归并排序（2-路归并）: .......................................................................................... 7 5.总结........................................................................................................................................ 8 5.1各种排序算法的比较: ................................................................................................ 8

各种排序的比较及其实现

1. 插入类排序：

基本思想：每次将一个待排序的记录，按关键字的大小插入到已排序列的一组记录的适当位置上，直到所有全部待排序列都插入为止。

1.1直接插入排序：

每次将一个待排序的记录，插入到已排序列的一组记录的适当位置上，每次使有序序列增加1个长度。 【算法特点】

1. 稳定排序

2. 可以用于链表和顺序表

3. 适用于初始记录基本有序的情况；当初始无序时、n较大时，移动次数较多，不宜

采用 代码：

voidInsertSort(ElemTypeA[], intn) {

inti, j;

for(i=2;i<=n;i++)//依次将A[2]～A[n]插入到前面已排序序列

1

}

if (A[i].key

A[0] = A[i];//复制为哨兵，A[0]不存放元素

for (j = i - 1; A[0].key

A[j + 1] = A[j];//向后挪位 A[j + 1] = A[0];//复制到插入位置

1.2折半插入排序:

直接插入排序每次时通过线性查找找到插入位置，而折半插入排序通过折半查找来实现查找位置。 【算法特点】

1. 稳定排序，由于使用折半查找，只能用于顺序表 2. 适合用于初始记录无序、n较大的情况 代码：

voidInsertSort(ElemTypeA[], intn) { }

inti, j, low, high, mid;

for (i = 2; i<= n; i++) {//依次将A[2]～A[n]插入到前面已排序序列 }

A[0] = A[i];//将A[i]暂存到A[0]

low = 1; high = i - 1;//设置折半查找的范围 while (low <= high) {//折半查找(默认递增有序) }

for (j = i - 1; j >= high + 1; --j)

A[j + 1] = A[j];//统一后移元素，空出插入位置 A[high + 1] = A[0];//插入操作

mid = (low + high) / 2;//取中间点

if (A[mid].key>A[0].key)high = mid - 1;//查找左半子表 else low = mid + 1;//查找右半子表

1.3 shell（希尔）排序:

直接插入排序在记录个数较少且序列基本有序时，效率较高。shell排序从“减少记录个数”和“序列基本有序”两个方面对其进行了改进。

shell排序是一种分组插入的算法。先将记录序列分割成几组，从而减少直接插入的数据量，

2