插入排序
1.直接插入排序
原理:将数组分为无序区和有序区两个区,然后不断将无序区的第一个元素按大小顺序插入到有序区中去,最终将所有无序区元素都移动到有序区完成排序。
要点:设立哨兵,作为临时存储和判断数组边界之用。
实现:
VoidInsertSort(NodeL[],intlength)
{
Inti,j;//分别为有序区和无序区指针
for(i=1;i<length;i++)//逐步扩大有序区
{
j=i+1;
if(L[j]<L[i])
{
L[0]=L[j];//存储待排序元素
While(L[0]<L[i])//查找在有序区中的插入位置,同时移动元素
{
L[i+1]=L[i];//移动
i--;//查找
}
L[i+1]=L[0];//将元素插入
}
i=j-1;//还原有序区指针
}
}
2.希尔排序
原理:又称增量缩小排序。先将序列按增量划分为元素个数相同的若干组,使用直接插入排序法进行排序,然后不断缩小增量直至为1,最后使用直接插入排序完成排序。
要点:增量的选择以及排序最终以1为增量进行排序结束。
实现:
VoidshellSort(NodeL[],intd)
{
While(d>=1)//直到增量缩小为1
{
Shell(L,d);
d=d/2;//缩小增量
}
}
VoidShell(NodeL[],intd)
{
Inti,j;
For(i=d+1;i<length;i++)
{
if(L[i]<L[i-d])
{
L[0]=L[i];
j=i-d;
While(j>0&&L[j]>L[0])
{
L[j+d]=L[j];//移动
j=j-d;//查找
}
L[j+d]=L[0];
}
}
}
交换排序
1.冒泡排序
原理:将序列划分为无序和有序区,不断通过交换较大元素至无序区尾完成排序。
要点:设计交换判断条件,提前结束以排好序的序列循环。
实现:
VoidBubbleSort(NodeL[])
{
Inti,j;
Boolischanged;//设计跳出条件
For(j=n;j<0;j--)
{
ischanged=false;
For(i=0;i<j;i++)
{
If(L[i]>L[i+1])//如果发现较重元素就向后移动
{
Inttemp=L[i];
L[i]=L[i+1];
L[i+1]=temp;
Ischanged=true;
}
}
If(!ischanged)//若没有移动则说明序列已经有序,直接跳出
Break;
}
}
2.快速排序
原理:不断寻找一个序列的中点,然后对中点左右的序列递归的进行排序,直至全部序列排序完成,使用了分治的思想。
要点:递归、分治
实现:
选择排序
1.直接选择排序
原理:将序列划分为无序和有序区,寻找无序区中的最小值和无序区的首元素交换,有序区扩大一个,循环最终完成全部排序。
要点:
实现:
VoidSelectSort(NodeL[])
{
Inti,j,k;//分别为有序区,无序区,无序区最小元素指针
For(i=0;i<length;i++)
{
k=i;
For(j=i+1;j<length;j++)
{
If(L[j]<L[k])
k=j;
}
If(k!=i)//若发现最小元素,则移动到有序区
{
Inttemp=L[k];
L[k]=L[i];
L[i]=L[temp];
}
}
}
2.堆排序
原理:利用大根堆或小根堆思想,首先建立堆,然后将堆首与堆尾交换,堆尾之后为有序区。
要点:建堆、交换、调整堆
实现:
VoidHeapSort(NodeL[])
{
BuildingHeap(L);//建堆(大根堆)
For(inti=n;i>0;i--)//交换
{
Inttemp=L[i];
L[i]=L[0];
L[0]=temp;
Heapify(L,0,i);//调整堆
}
}
VoidBuildingHeap(NodeL[])
{ For(i=length/2-1;i>0;i--)
Heapify(L,i,length);
}
归并排序
原理:将原序列划分为有序的两个序列,然后利用归并算法进行合并,合并之后即为有序序列。
要点:归并、分治
实现:
VoidMergeSort(NodeL[],intm,intn)
{
Intk;
If(m<n)
{
K=(m+n)/2;
MergeSort(L,m,k);
MergeSort(L,k+1,n);
Merge(L,m,k,n);
}
}
基数排序
原理:将数字按位数划分出n个关键字,每次针对一个关键字进行排序,然后针对排序后的序列进行下一个关键字的排序,循环至所有关键字都使用过则排序完成。
要点:对关键字的选取,元素分配收集。
实现:
VoidRadixSort(NodeL[],length,maxradix)
{
Intm,n,k,lsp;
k=1;m=1;
Inttemp[10][length-1];
Empty(temp); //清空临时空间
While(k<maxradix) //遍历所有关键字
{
For(inti=0;i<length;i++) //分配过程
{
If(L[i]<m)
Temp[0][n]=L[i];
Else
Lsp=(L[i]/m)%10; //确定关键字
Temp[lsp][n]=L[i];
n++;
}
CollectElement(L,Temp); //收集
n=0;
m=m*10;
k++;
}
}
相关推荐
八大排序算法总八大排序算法总八大排序算法总八大排序算法总结
排序算法总结。。。排序算法总结。。。。排序算法总结。。
总结了常用的八大排序算法:(交换式:1、冒泡,2、快排; 选择式:3、选择, 4、堆排; 插入式:5、插入, 6、希尔; 其他:7、归并, 8、基数排序)。 并包含了Java实现的源代码。
不稳定的排序算法:快速排序、希尔排序、堆排序、选择排序(简简记记::快快些些选选堆堆) 所需辅助空间最多:归并排序 所需辅助空间最少:堆排序 平均速度最快:快速排序 当n较大,则应采用时间复杂度为O(nlogn)的...
总结了八大排序算法的写法,并且比较了效率,供大家学习借鉴。
八大排序算法,排序算法是比较初级的算法,在学习排序算法的同时有助于我们去理解数据结构,熟练掌握C++语法规则
java.八大排序算法
最经典的8大排序算法总结,插入排、冒泡排序、快速排序、简单选择排序、归并排序、二叉树排序、基数排序等。
八大排序算法的MATLAB实现,包含直接选择,直接插入,希尔排序,归并排序,冒泡排序,快速排序,堆排序等排序算法的实现。
经典排序算法总结和源码,用C++实现 是学习排序的好文档啊
自己整理的八大排序算法的实现以及其各自的特点,希望能帮助需要的人
插入排序、快速排序、希尔排序、基数排序、堆排序、选择排序、冒泡排序、归并排序 八种排序算法的实现与时间比较
Java实现八大排序算法
对八大排序算法进行了详细的释义,包括思想过程、伪代码、实现代码。
我用vs2017写的包含八大排序算法和随机生成数的算法。其中包括:冒泡排序,快速排序,选择排序,插入排序,桶排序,希尔排序,计数排序。其实只有七个排序算法。