十大排序算法上
程序员文章站
2022-03-03 19:49:43
...
冒泡排序:
冒泡排序时间复杂度(n2),其主要思想是进行相邻数组之间两两比较来达到排序的效果.主要代码如下:
for(int i=0;i<n-1;;i++)
for(int j=0;j<n-i-1;j++)
if(a[j]>a[j+1]) swap(a[j],a[j+1]);//为升序排序 时间复杂度n2
选择排序:
选择排序时间复杂度也为(n2),其主要思想是固定住一个数的位置后,从未排序的位置中寻找一个最大or最小的元素放到已排序的末端。主要代码如下:
for(int i=0;i<n;i++)
{ int minid=i; //minid为固定末端的最后一个数
for(int j=i+1;j<n;j++)
{
if(a[j]<a[minid]) minid=j;
}
swap(a[minid],a[i]);
}
插入排序:
插入排序时间复杂度为(n2),其主要是通过构造有序数列,对未排序的数据,在已排序的数列从后往前扫描,找到相应的位置后插入即可。其主要代码如下:
for(int i=1;i<n;i++)
{
int pre=i-1;//代表已经排好序列的数组
int cur=a[i];
while(pre>=0&&a[pre]>cur])
{
a[pre+1]=a[pre];
pre--;
}
a[pre+1]=cur;
}
希尔排序
希尔排序时间复杂度为(n1.3),之际上为简单的插入排序改编版,其主要差别的是优先比较距离比较远的元素。其主要代码如下:
int i, j, gap;
for (gap = n / 2; gap > 0; gap /= 2)
for (i = gap; i < n; i++)
for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)
Swap(a[j], a[j + gap]);
归并排序
归并排序,时间复杂度为nlogn采用的是分治法,先使每个子序列有序,再使得子序列间段有序主要代码如下:
void msort(int l,int r)
{
if(l==r)return ;
int mid=(l+r)>>1;
msort(l,mid);msort(mid+1,r);
int i=l;int p=l;int j=mid+1;
while(i<=mid&&j<=r)
{
if(a[i]>a[j]) tem[p++]=a[j++];
else tem[p++]=a[i++];
}
while(i<=mid) tem[p++]=a[i++];
while(j<=r) tem[p++]=a[j++];
for(int i=l;i<=r;i++)a[i]=tem[i];
}
上一篇: Python十大常用文件操作
下一篇: Python十大装B语法