测试选择排序,冒泡排序,快速排序,插入排序,希尔排序算法性能

文章作者:中山市飞娥软件工作室「Feiesoft.com」  浏览次数:1923 次  更新日期:2014-04-09

C:\Users\ChenFeie\Desktop>sorttest
正在生成待测试的随机数组...用时 0.000755 秒,数组长度:100000
正在测试选择排序算法性能...用时 5.816847 秒
正在测试冒泡排序算法性能...用时 24.678479 秒
正在测试快速排序算法性能...用时 0.011887 秒
正在测试插入排序算法性能...用时 3.111858 秒
正在测试希尔排序算法性能...用时 0.026572 秒

C:\Users\ChenFeie\Desktop>sorttest
正在生成待测试的随机数组...用时 0.000843 秒,数组长度:100000
正在测试选择排序算法性能...用时 5.707276 秒
正在测试冒泡排序算法性能...用时 24.336994 秒
正在测试快速排序算法性能...用时 0.012778 秒
正在测试插入排序算法性能...用时 3.016288 秒
正在测试希尔排序算法性能...用时 0.026750 秒

C:\Users\ChenFeie\Desktop>sorttest
正在生成待测试的随机数组...用时 0.001532 秒,数组长度:100000
正在测试选择排序算法性能...用时 6.073125 秒
正在测试冒泡排序算法性能...用时 25.397233 秒
正在测试快速排序算法性能...用时 0.011747 秒
正在测试插入排序算法性能...用时 3.162182 秒
正在测试希尔排序算法性能...用时 0.028051 秒

===================================

// 算法名称:选择排序(不稳定)

void select_sort(int arr[],int len)

{

 int i,j,k,tmp;

 for(i=0;i<len-1;i++)

 {

  k=i;

  for(j=i+1;j<len;j++)

   if(arr[k]>arr[j])k=j;

  if(k !=i)

  {

   tmp=arr[k];

   arr[k]=arr[i];

   arr[i]=tmp;

  }

 }

}

// 算法名称:冒泡排序(稳定)

void bubble_sort(int arr[],int len)

{

 int i,j,k,swap=0;

 for(i=len-1;i>=0;i--)

 {

  swap=0;

  for(j=0;j <=i-1;j++)

  {

   if(arr[j]>arr[j+1])

   {

    k=arr[j];

    arr[j]=arr[j+1];

    arr[j+1]=k;

    swap=1;

   }

  }

  if(0 ==swap)break;

 }

}

// 算法名称:快速排序(不稳定)

void quick_sort(int arr[],int start,int end)

{

 int i=start,j=end,k=arr[start];

 while(i<j)

 {

  while(j>i && arr[j]>=k)j--;

  if(i<j)arr[i]=arr[j];

  while(i<j && arr[i]<k)i++;

  if(i<j)arr[j]=arr[i];

 }

 arr[i]=k;

 if(i>start+1)quick_sort(arr,start,i-1);

 if(j<end-1)quick_sort(arr,j+1,end);

}

// 算法名称:插入排序(稳定)

void insert_sort(int arr[],int len)

{

 int i,j,k;

 for(i=1;i<len;i++)

 {

  k=arr[i];

  for(j=i;j>0 && arr[j-1]>k;j--)

   arr[j]=arr[j-1];

  arr[j]=k;

 }

}

// 算法名称:希尔排序(不稳定)

void shell_sort(int arr[],int len)

{

 int d=len / 2,k,i,j;

 while(d>0)

 {

  for(i=d;i<len;i++)

  {

   k=arr[i];

   for(j=i;j>=d && arr[j-d]>k;j -=d)

    arr[j]=arr[j-d];

   arr[j]=k;

  }

  d /=2;

 }

}

 

===================================

从测试的结果表明,快速排序算法与希尔排序算法是效率最高的,其次是直接插入排序算法,但快速与希尔排序算法是不稳定的,即可能改变等值的位置,而直接插入排序则不会,因此对于小规模的数据排序,小编建议使用直接插入排序。