数据结构的各种排序-创新互联

文章目录

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

专注于为中小企业提供网站建设、成都网站制作服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业康平免费做网站提供优质的服务。我们立足成都，凝聚了一批互联网行业人才，有力地推动了近千家企业的稳健成长，帮助中小企业通过网站建设实现规模扩充和转变。内部排序算法性能比较

算法种类	最好情况	平均情况	最坏情况	空间复杂度	稳定性
直接插入排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定
冒泡排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定
简单选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定
希尔排序				O(1)	不稳定
快速排序	O(nlog2n)	O(nlog2n)	O(n^2)	O(log2n)	不稳定
堆排序	O(nlog2n)	O(nlog2n)	O(nlog2n)	O(1)	不稳定
2-归路排序	O(nlog2n)	O(nlog2n)	O(nlog2n)	O(n)	稳定
基数排序	O(d(n+r))	O(d(n+r))	O(d(n+r))	O( r )	稳定

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,20

d=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.按个位进行分配

0	1	2	3	4	5	6	7	8	9
520	211	233			985	666	007	438
	111					996		888
								168

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

2.按十位进行分配

0	1	2	3	4	5	6	7	8	9
007	211	520	233			666		985	996
	111		438			168		888

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

3.按百位进行分配

0	1	2	3	4	5	6	7	8	9
007	111	211		438	520	666		888	985
	168	233							996

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

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

名称栏目：数据结构的各种排序-创新互联
本文链接：http://dzwzjz.com/article/dihjpe.html