排序算法

排序算法空间、时间复杂度

简单排序法——

 

冒泡法是第二维循环中自己循环，找最小或最大值

 

选择排序和交换排序是第二维循环与第一维循环中的值比较；交换法最清晰，选择法作了改进，

只交换位置标号，算法复杂度没变。

 

插入法，它的基本工作原理是抽出牌，在前面的牌中寻找相应的位置插入，然后继续下一张（较为复杂）

 

高级排序法——

 

快速排序，从冒泡法改进得到，基本思想是任选一个记录，一般选取序列第一个， 通过一趟排序将待排 记录分割成相邻的两个区域，其中一个区域中记录的关键字比另一个区域关键字都小，即一个区域的值都大于所取的关键字，另一个区域的指都小于所取的关键字， 则可以分别对这两个区域的记录进行排序，以达到整个序列有序。

将它区别于SHELL排序，后者是先有一个递减的步长数组，对相隔step-1的内容排列，然后改变步长，依次

下去。

 

归并排序，先在原记录中找一个中间位置（low+high）/2，对两段分别进行归并排序，最后再整体排序（即分三次）。

注意，快速排序没有最后整体排序，但一开始先排了一次。 

 

堆排序，对选择排序的改进，利用堆的特性对记录序列进行排序。

 

时间复杂度

 

冒泡排序、选择排序和插入排序的比较次数为O(n²)，最坏情况 O(n²)，最好O(n)

（但选择排序最好是 O(n²)）

快速排序在平均情况下复杂性为O(nlogn)，最坏情况 O(n²)，最好O(nlogn)

堆排序和合并排序在最坏情况下复杂性为O(nlogn)。可见，合并排序和堆排序是比较排序算法中时间复杂度最优算法。

 

空间复杂度

空间性能是排序所需辅助空间大小

 

所有简单排序和堆排序都是0(1)

快速排序为0(logn)，要为递归程序执行过程栈所需的辅助空间

归并排序和基数排序所需辅助空间最多，为O(n)

 
冒泡法排序(C语言)

#include"stdio.h"
#define True 1
#define False 0
void main()
{
   int a[7]={9,12,6,15,3,16,10};
   int i,temp;
   for(i=1;i<=6;i++)  /*m个数字需要m-1轮排序*/
  {
    int j;
    int ok=True;       

    for(j=0;j<=7-i;j++)/*第i轮排序需要比较m-i次*/
   {

     if(a[j]>a[j+1])
     {
        ok=False;
        temp=a[j];
        a[j]=a[j+1];
        a[j+1]=temp;
     }
    }
     if(ok==True)  /*若该轮排序没有发生任何交换,则说明已经排好序了*/
          break;
   }
   for(i=0;i<7;i++)
  {
      printf("%4d",a[i]);
  }

}

快速排序法（C语言）

#include"stdio.h"
void quickSort(int a[],int left,int right)
{
   int i,j,temp;
   i=left;
   j=right;
   temp=a[left];
   if(left>right)
      return;
   while(i!=j)/*找到最终位置*/
   {
      while(a[j]>=temp && j>i)
         j--;
      if(j>i)
         a[i++]=a[j];
       while(a[i]<=temp && j>i)
          i++;
       if(j>i)
          a[j--]=a[i];
        
   }
   a[i]=temp;
   quickSort(a,left,i-1);/*递归左边*/
   quickSort(a,i+1,right);/*递归右边*/
}

void main()
{
    int a[7]={8,2,6,12,1,9,5};
    int i;
    quickSort(a,0,6);
    /*排好序的结果*/
    for(i=0;i<7;i++)
        printf("%4d",a[i]);
}

直接选择排序（C语言）
#include"stdio.h"
#include"conio.h"
void selectSort(int a[],int count)
{
  int i,j,min,temp;
  for(i=0;i  {
     min=i;
     for(j=i+1;j       if(a[j]           min=j;
     if(min!=i)
     {
       temp=a[min];
       a[min]=a[i];
       a[i]=temp;
     }
   }
}
void main()
{
  int a[7]={8,9,3,5,1,6,4};
  int i;
  selectSort(a,7);
  clrscr();
  for(i=0;i<7;i++)
    printf("%4d",a[i]);
}

直接插入排序（C语言）
#include"stdio.h"
#include"conio.h"
void insertSort(int a[],int count)   /*count为排序数字个数*/
{
   int i,j,temp;
   for(i=1;i   {
      temp=a[i];
      j=i-1;
      while(a[j]>temp && j>=0)
      {
        a[j+1]=a[j];
         j--;
      }
      if(j!=(i-1)) /*第i个数字比前面的都大，不需要重新插入*/      
      {
        a[j+1]=temp;
      }
        
    }
}
void main()
{
   int a[7]={8,10,2,3,1,7,13};
   int i;
   insertSort(a,7);
   clrscr();
   for(i=0;i<7;i++)      /*输出排序后的结果*/
   {
      printf("%4d",a[i]);
   }
}