欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

十大排序算法上

程序员文章站 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];
}