尝试用顺序表实现排序算法(持续更新..)

2024-06-04 13:41| 来源: 网络整理| 查看: 265

数据结构刚刚学到顺序表，于是顺便试下复习下C语言，自学下后面必会的各种排序算法并自己实现下。（排序算法毕竟比较基础也是很多时候面试会面到的）算是随笔吧,最近又挺忙的，搞项目的事排序算法很多，按依据的原则分可以有：

**- 插入排序 - 交换排序 - 选择排序 - 归并排序 - 计数排序**

按时间复杂度分可以有：

O(nlogn); O(n^2);

O(d*n);

1. 插入排序 1.1.直接插入排序(Straight Insertion Sort) 直插是最简单，最易实现的。我按自己的理解复述下：依次提取元素，将此元素在之前已排好的有序序列中实现插入。插入位置的确认是通过历遍有序序列（这里从提取的元素前一个元素开始历遍，也可以从序列第一个元素开始，你喜欢咯= =）,设提取的元素是a,若此元素a小于有序序列中的元素b，即将该元素b往后移一位，直到找到等于或小于元素a的元素，就将元素a插入到该元素后面。通常默认将序列中第一个元素看作已排好的有序序列，然后从第二个元素到表尾的元素是待排序列。不多说先po写好的代码：

void InsertSort(SqList *L) { int i,j,k,temp; //temp=L->elem[0]; for(i=1;ilength;i++) { temp=L->elem[i];//待插入元素提取出来 for(j=i-1;j>=0 && L->elem[j]> temp;j--)//若待插入元素比有序序列中比较元素小，就将该比较元素后移一位 { L->elem[j+1]=L->elem[j]; } L->elem[j+1]=temp;//实现待插入元素插入 for(k=0;klength;k++)//打印一趟排序 printf("%d ",L->elem[k]); printf("\n"); } }

算法时间复杂度为O(n^2);

1.2折半插入(Binary Insertion Sort)

折半插入是对直插的一点改进，毕竟记录数量n很大时比较麻烦。在直插查找插入位置时，选择历遍有序序列中所有元素，该历遍次数的数量级是n。在有序查找中，有一种折半查找的算法，可以应用到这个查找的过程，这就出现了折半插入撸。 po个代码

void BinaryInsertSort(SqList *L) { int i,j,k,temp,upper,lower,key; for(i=1;ilength;i++) { temp=L->elem[i];//待插入元素提取到temp lower=0; upper=i-1;//在lower到upper区间进行插入 while(lower=upper+1;j--)//插入点后面元素全部后移 L->elem[j+1]=L->elem[j];//元素后移 L->elem[upper+1]=temp;//插入待插元素 for(k=0;klength;k++)//打印序列 printf("%d ",L->elem[k]); printf("\n"); } }

虽然折半插入减少了序列查找的次数，但是插入的次数没有改变，因此时间复杂度仍然为O(n^2).

1.3希尔排序(Shell’s Sort)

终于来到了比较有点意思的希尔排序，又称“缩小增量排

【本文地址】

公司简介

联系我们