冒泡 直接插入 希尔排序 效率比拼

来源：百度文库 编辑：神马文学网 时间：2024/10/02 18:43:02
分别运用直接排序和希尔排序对同一个数组进行效率之间的比较，数组为一个15元素的整形数组：77  89 24 0 5 7 11 56 28 49 105 25 1 9 10； 直接插入排序代码如下：#include
static int m;
 
int main()
{
 int i,j;
 int a[15];
 printf("please input 15 numbers\n");
 for(i=0;i<15;i++)
 scanf("%d",&a[i]); for(i=1;i<15;i++)
 {
  int temp=a[i];
  for(j=i;j>=0&&temp  {
   a[j]=a[j-1];
   m++;
  }
 a[j]=temp;
 }
 printf("采用直接排序法的结果如下:\n");
 for(i=0;i<15;i++)
 printf("a[%d]=%d\n",i,a[i]);
 printf("比较次数为:%d",m);
 
}
运行结果如图： 可以看到比较次数为57次。 我写的希尔排序代码如下：#include
void ShellSort(int *p, int t);
void ShellInsert(int *a,int dk);
static int m;
int main(int argc, char* argv[])
{
using namespace std;
int   Array[15];printf("请输入15个数字\n");
for(int i=0;i<15;i++)
scanf("%d",&Array[i]);
ShellSort(Array, 2);
return 0;
}
void  ShellSort(int *p, int  k)
{
 using namespace std; while(k>=0)
 {
 ShellInsert(p,k);//每调用一次希尔排序，传递进去一个增量值，每个增量值对应于若干个分组。
 k--;
 }
cout<<"经过希尔排序"<for(int n=0;n<15;n++)
cout<cout<<"比较的次数为:"<cout<void ShellInsert(int *a,int dk)
{
 using namespace std;
 int t;
 for(int i=dk;i<15;i++)//i增加一次，就是对应于对一个分组的排序操作。
 if(a[i] {
 t=a[i];
 for(int j=i;j>=0&&t {
 a[j]=a[j-dk];
 m++;
 }
 a[j]=t; }
}
运行结果如下： 可以看到比较次数降到了36次。 下面的是我的一个好友写的希尔排序，和我的差异主要在for循环。代码如下：#include
void ShellSort(int *p, int t);
void ShellInsert(int *a,int dk);
static int m;
int main(int argc, char* argv[])
{
using namespace std;
int   Array[15];
printf("请输入15个数字\n");
for(int i=0;i<15;i++)
scanf("%d",&Array[i]);
ShellSort(Array, 2);
return 0;
}
void  ShellSort(int *p, int  k)
{
 using namespace std; while(k>=0)
 {
 ShellInsert(p,k);//每调用一次希尔排序，传递进去一个增量值，每个增量值对应于若干个分组。
 k--;
 }
cout<<"经过希尔排序"<for(int n=0;n<15;n++)
cout<cout<<"比较次数为:"<cout<void ShellInsert(int *a,int dk)
{
 using namespace std;
 int t;
 for(int i=dk;i<15;i++)//i增加一次，就是对应于对一个分组的排序操作。
 if(a[i] {
 t=a[i];
 for(int j=i-dk;j>=0&&t=0&&t {
 m++; 
 a[j+dk]=a[j];
 }
 a[j+dk]=t; }
}
运行结果：可以看到比较次数降到了33次。 下面是我根据gap的取值公式写的改进型的希尔排序代码：#include
void ShellSort(int *p );
void ShellInsert(int *a,int dk);
static int m;
int main(int argc, char* argv[])
{
using namespace std;
int   Array[15];
printf("请输入15个数字\n");
for(int i=0;i<15;i++)
scanf("%d",&Array[i]);
ShellSort(Array);
return 0;
}
void  ShellSort(int *p )
{
 using namespace std; for (int k = 15/2; k > 0; k /= 2)
 ShellInsert(p,k);//每调用一次希尔排序，传递进去一个增量值，每个增量值对应于若干个分组。
 
cout<<"经过希尔排序"<for(int n=0;n<15;n++)
cout<cout<<"比较次数为:"<cout<void ShellInsert(int *a,int dk)
{
 using namespace std;
 int t;
 for(int i=dk;i<15;i++)//i增加一次，就是对应于对一个分组的排序操作。
 if(a[i] {
 t=a[i];
 for(int j=i-dk;j>=0&&t=0&&t {
 m++; 
 a[j+dk]=a[j];
 }
 a[j+dk]=t; }
}
运行结果如下：可以看到比较次数降到了29次 即兴发挥写了个冒泡算法代码如下：#include
static int m;
 
int main()
{
 int i,j;
 int a[15];
 printf("please input 15 numbers\n");
 for(i=0;i<15;i++)
 scanf("%d",&a[i]);for(i=0;i<14;i++)
for(j=0;j<14-i;j++)
if(a[j]>a[j+1])
{
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
m++;
}  printf("采用冒泡法的结果如下:\n");
 for(i=0;i<15;i++)
 printf("a[%d]=%d\n",i,a[i]);
 printf("比较次数为:%d",m);
 
}
运行结果：比较次数为57次。  
冒泡 直接插入 希尔排序 效率比拼 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。 希尔排序 冒泡排序原理详解 希尔排序2 希尔排序3 算法设计与分析　冒泡排序 第三十四课 插入排序、快速排序 直接排序---终极指南 在Word中直接插入目录 算法连载（2）--快速排序与插入排序的比较 - Compower Studio - CSD... MP3 AddIn for PowerPoint 1.0 | PPT直接插入MP3插件 转贴：如何直接在PPT中插入FLV影片 唯美佳人【flash素材】 有地址可直接插入博客 【转】 荷花仙子flash—有地址可直接插入博客中 - 唐老鴨(kenltx)的日志 - ... 漂亮的【LIASH素材】 ——有地址可直接插入博客中 漂亮的【flash素材】 ——有地址可直接插入博客中 精美红灯笼FLASH——有地址可直接插入博客333 【秀色可餐】冒泡极品 拿破仑.希尔 拿破仑.希尔 三种闷骚 让爱甜得冒泡_ 数据结构排序 饮食排序