排序-阿里云开发者社区

开发者社区> 开发与运维> 正文
登录阅读全文

排序

简介: 各种排序方法的综合比较 结论:   排序方法 平均时间 最坏时间 辅助存储   简单排序 O(n2)  O(n2)  O(1)   快速排序 O(nlogn) O(n2)         O(logn)   堆排序 O(nlogn) O(nlogn) O(1)   归并排序 O(nlogn) O(...

各种排序方法的综合比较


结论:
   排序方法 平均时间 最坏时间 辅助存储
   简单排序 O(n2)  O(n2)  O(1)
   快速排序 O(nlogn) O(n2)         O(logn)
   堆排序 O(nlogn) O(nlogn) O(1)
   归并排序 O(nlogn) O(nlogn) O(n)
   基数排序 O(d(n+rd)) O(d(n+rd)) O(rd)
另外:直接插入排序、冒泡排序为简单排序,希尔排序(不稳定)

一、时间性能 

按平均的时间性能来分,有三类排序方法:
时间复杂度为O(nlogn)的方法有:快速排序、堆排序和归并排序,其中以快速排序为最

好;

时间复杂度为O(n2)的有:直接插入排序、起泡排序和简单选择排序,其中以直接插入为

最好,特别是对那些对关键字近似有序的记录序列尤为如此;

时间复杂度为O(n)的排序方法只有,基数排序。

当待排记录序列按关键字顺序有序时,直接插入排序和起泡排序能达到O(n)的时间复杂

度;而对于快速排序而言,这是最不好的情况,此时的时间性能蜕化为O(n2),因此是应

该尽量避免的情况。
简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。
二、空间性能

指的是排序过程中所需的辅助空间大小。

1. 所有的简单排序方法(包括:直接插入、起泡和简单选择)和堆排序的空间复杂度为O

(1);

2. 快速排序为O(logn  ),为栈所需的辅助空间;

3. 归并排序所需辅助空间最多,其空间复杂度为O(n );

4.链式基数排序需附设队列首尾指针,则空间复杂度为O(rd  )。

三、排序方法的稳定性能

1. 稳定的排序方法指的是,对于两个关键字相等的记录,它们在序列中的相对位置,在

排序之前和经过排序之后,没有改变。

2. 当对多关键字的记录序列进行LSD方法排序时,必须采用稳定的排序方法。

3. 对于不稳定的排序方法,只要能举出一个实例说明即可。

4. 快速排序和堆排序是不稳定的排序方法

#include <stdio.h>
#include <stdlib.h>

void ss_sort(int e[],int n)
{
  int i,j,k,t;
  for (i=0;i<n-1;i++) {
    for (k=i,j=i+1;j<n;j++)
      if (e[k]>e[j]) k=j;
    if (k!=i) {
      t=e[i]; e[i]=e[k]; e[k]=t;
    }      
  }     
}    

void si_sort(int e[],int n)
{
  int i,j,t;
  for (i=1;i<n;i++)
  {
    for (t=e[i],j=i-1;j>=0 && t<e[j];j--)
      e[j+1]=e[j];
    e[j+1]=t;   
  }      
}

void sb_sort(int e[],int n)
{
  int j,p,h,t;
  for (h=n-1;h>0;h=p)
  {
    for (p=j=0;j<h;j++)
    if (e[j]>e[j+1]) {
      t=e[j];
      e[j]=e[j+1];
      e[j+1]=t;
      p=j; 
    }    
  }      
}    

void shell(int e[],int n)
{
  int j,k,h,y;
  for (h=n/2;h>0;h=h/2)
    for (j=h;j<n;j++) {
      y=e[j];
      for (k=j-h;k>=0&&y<e[k];k-=h)
        e[k+h]=e[k];
      e[k+h]=y;   
    }      
}    

void sift(int e[],int n,int s)
{
  int t,k,j;
  t=e[s];
  k=s; j=2*k+1;
  while (j<n) {
    if (j<n-1&&e[j]<e[j+1])
       j++;
    if (t<e[j]) {
      e[k]=e[j];
      k=j;
      j=2*k+1;
    }
    else
      break;        
  }       
  e[k]=t;
}    

void heapsort(int e[],int n)
{
  int i,k,t;
  for (i=n/2-1;i>=0;i--)
    sift(e,n,i);
  for (k=n-1;k>=1;k--) {
    t=e[0];
    e[0]=e[k];
    e[k]=t;
    sift(e,k,0); 
  }         
}    

void r_quick(int e[],int low,int high)
{
  int i,j,t;
  if (low<high) {
    i=low;  j=high; t=e[low];
    while (i<j) {
      while (i<j && e[j]>t) j--;
      if (i<j) e[i++]=e[j];
      while (i<j && e[i]<=t)i++;
      if (i<j) e[j--]=e[i];     
    }      
    e[i]=t;
    r_quick(e,low,i-1);
    r_quick(e,i+1,high);
  } 

void merge_step(int e[],int a[],int s,int m,int n)  
{
  int i,j,k;
  k=i=s;  j=m+1;
  while (i<=m && j<=n)
    if (e[i]<=e[j]) a[k++]=e[i++];
    else a[k++]=e[j++];
  while (i<=m) a[k++]=e[i++];
  while (j<=n) a[k++]=e[j++];      
}    

void merge_pass(int e[],int a[],int n,int len)
{
  int f_s,s_end;
  f_s=0;
  while (f_s+len<n) {
    s_end=f_s+2*len-1;
    if (s_end>=n) s_end=n-1;
    merge_step(e,a,f_s,f_s+len-1,s_end);
    f_s=s_end+1;   
  }         
  if (f_s<n)
    for (;f_s<n;f_s++)
      a[f_s]=e[f_s];
}  

void merge(int e[],int n)
{
  int *p=(int *)malloc(sizeof(int)*n);
  int len=1,f=0;
  while (len<n) {
    if (f==0) merge_pass(e,p,n,len);
    else merge_pass(p,e,n,len);
    len *=2;
    f=1-f;   
  }      
  if (f)
    for (f=0;f<n;f++) e[f]=p[f];
  free(p);   
}      

int main(int argc, char *argv[])
{
  int a[8]={4,6,2,1,3,9,10,5},*p,i=0; 
 
  ss_sort(a,8);
  for (p=a;p<a+8;p++)
    printf("%d\n",*p);
  printf("\n"); 
   
  si_sort(a,8);
  for (p=a;p<a+8;p++)
    printf("%d\n",*p);
  printf("\n");  
 
  sb_sort(a,8);
  for (p=a;p<a+8;p++)
    printf("%d\n",*p);
  printf("\n");   
 
  shell(a,8);
  for (p=a;p<a+8;p++)
    printf("%d\n",*p);
  printf("\n");  
 
  heapsort(a,8);
  for (p=a;p<a+8;p++)
    printf("%d\n",*p);
  printf("\n"); 
 
  r_quick(a,0,7);
  for (p=a;p<a+8;p++)
    printf("%d\n",*p);
  printf("\n"); 
 
  merge(a,8);
  for (p=a;p<a+8;p++)
    printf("%d\n",*p);
  printf("\n"); 
  system("PAUSE"); 
  return 0;
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章
最新文章
相关文章