文章目录

• • • • 内部排序算法性能比较
      • 1. 插入排序
      • • 1.1 直接插入排序
        • 1.2 折半插入排序
        • 1.3 希尔排序(不稳定)
      • 2. 交换排序
      • • 2.1 冒泡排序
        • 2.2 快速排序
      • 3. 选择排序
      • • 3.1 简单选择排序（不稳定）
        • 3.2 堆排序（不稳定）
      • 4. 归并排序
      • 5. 基数排序

内部排序算法性能比较

1. 插入排序

插入排序:每次将一个待排序的记录按其关键字大小插入前面已排好的子序列，直到全部记录插入完成。

1.1 直接插入排序

示例:对以下记录进行排序
{49,38,65,97,76,13,27,49'}

原始记录:49,38,65,97,76,13,27,49';
//()括号内的记录为已经排序好的子序列
第一趟:(38,49),65,97,76,13,27,49';
第二趟:(38,49,65),97,76,13,27,49';
第四趟:(38,49,65,97),76,13,27,49';
第五趟:(38,49,65,,76,97),13,27,49';
第六趟:(13,38,49,65,76,97),27,49';
第七趟:(13,27,38,49,65,76,97),49';
第八趟:(13,27,38,49,49',65,76,97);

1.2 折半插入排序

折半插入:将比较和移动操作分离。先查找位置再移动元素。(只适用于有序表)

void InsertSort(ElemType A[],int n){int i,j,low,mid,high;for(i=2;i<=n;i++){//折半查找A[0]=A[i];low=1;high=i-1;while(low<=high){mid=(low+high)/2;if(A[mid]>A[0]){high=mid-1;//查找左半子表}else{low=mid+1;//查找右半子表}//移动元素for(j=i-1;j>=high+1;--j){A[j+1]=A[j];//统一后移元素,空出插入位置}A[high+1]=A[0];//插入操作}}
}

1.3 希尔排序(不稳定)

希尔排序:先追求表中元素部分有序,在逐渐逼近全局有序

算法思想:
1.先将待排序记录分割为特殊"子表",即把相隔某个"增量"的记录组成一个子表。
2.对各个子表分别进行直接插入排序。
3.最后对全局记录进行一次插入排序。

示例:对以下记录进行排序
{50,26,38,80,70,90,8,30,40,20}

原始序列:50,26,38,80,70,90,8,30,40,20d=5:50,8,30,40,20,90,26,38,80,70;//(50,90),(26,8),(38,30),(80,40),(70,20)
d=3:26,8,30,40,20,80,50,38,90,70;//将间隔为3的分割为一组
d=1:8,20,26,30,38,40,50,70,80,90;//直接插入排序

2. 交换排序

交换:是指根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置

2.1 冒泡排序

基本思想:从前往后(或从后往前)两两比较相邻元素的值，若为逆序，则交换它们，直到序列比较完。称之为第一趟冒泡排序。
示例:对以下记录进行排序
{49,38,65,97,76,13,27,45}

原始序列:49,38,65,97,76,13,27,45
//每趟排序都会将一个元素放置到其最终位置上
第一趟:38,49,65,76,13,27,45,97;
第二趟:38,49,65,13,27,45,76,97;
第三趟:38,49,13,27,45,65,76,97;
第四趟:38,13,27,45,49,65,76,97;
第五趟:13,27,38,45,49,65,76,97;

2.2 快速排序

快速排序:基于分治法

算法思想:
1.在待排序表L[1...n]中任取一个元素pivot作为枢轴(基准,通常取首元素)
2.通过一趟排序将待排序表划分为独立的两部分L[1...k-1]和L[k+1...n]
3.使L[1...k-1]中所有元素小于pivot,L[k+1...n]中所有元素大于pivot
4.pivot放在了其最终位置L(k)上,以上过程称为一趟快速排序.
5.重复上述过程......

示例:对以下记录进行排序
{49,38,65,97,76,13,27,49'}

原始序列:49,38,65,97,76,13,27,49';
取pivot=49;
待补充......

3. 选择排序

3.1 简单选择排序（不稳定）

简单选择排序:每一趟在待排序元素中选取关键字最小的元素加入有序子序列
示例:对以下记录进行排序
{49,38,65,97,76,13,27,49'}

原始序列:49,38,65,97,76,13,27,49'
//每次选取关键字最小的元素,与前面相应位置进行交换
第一趟:13,38,65,97,76,49,27,49';//13与49交换位置
第二趟:13,27,65,97,76,49,38,49';//27与38交换位置
第三趟:13,27,38,97,76,49,65,49';//38与65交换位置
第四趟:13,27,38,49,76,97,65,49';//49与97交换位置
第五趟:13,27,38,49,49',97,65,76;//49'与76交换位置
第六趟:13,27,38,49,49',65,97,76;//65与97交换位置
第七趟:13,27,38,49,49',65,76,97;//76与97交换位置

3.2 堆排序（不稳定）

4. 归并排序

5. 基数排序

概念:不基于比较和移动元素进行排序，而基于关键字各位的大小进行排序。借助多关键字排序的思想对但逻辑关键字进行排序的方法

算法思想:
1.将整个关键字拆分为d位(组)
2.按照各个关键字权重递增的次序，做d趟"分配"和"收集"
3.分配:顺序扫描各个元素,根据当前处理的关键字位,将元素插入相应的队列
4.收集:把各个队列中结点依次出队并链接

基本操作 :
(1)按“各”位进行分配;
(2)从左到右进行收集;

示例:对如下10个记录进行排序
{520,211,438,888,007,111,985,666,233,168}
1.按个位进行分配

收集:520,211,111,233,985,666,996,007,438,888,168

2.按十位进行分配

收集:007,211,111,520,233,438,666,168,985,888,996

3.按百位进行分配

收集:007,111,168,211,233,438,520,666,888,985,996