7种内部排序算法.txt

7种内部排序算法的比较 里面含 测试代码!

堆排序
#include<stdio.h>
void CreatHeap(int a[],int n,int h)
{   int i,j,flag,temp;
     i=h;
  j=2*i+1;
  temp=a[i];
  flag=0;
  while(j<n && flag!=1)
  {  if(j<n-1 && a[j]<a[j+1]) j++;
      if(temp>a[j])
    flag=1;
   else
   {  a[i]=a[j];
      i=j;
   j=2*i+1;
   }
  }
   a[i]=temp;
}
void InitCreatHeap(int a[],int n)
{   int i;
    for(i=(n-1)/2;i>=0;i--)
  CreatHeap(a,n,i);
}
void HeapSort(int a[],int n)
{   int i,temp;
    InitCreatHeap(a,n);
for(i=n-1;i>0;i--)
{  temp=a[0];
    a[0]=a[i];
    a[i]=temp;
    CreatHeap(a,i,0);
}

}
main()
{  int n,i,a[100];
   printf("请问你要输入几个排序数:\\n");
   scanf("%d",&n);
   printf("请输入你要排序的数值:\\n");
   for(i=0;i<n;i++)
    scanf("%d",&a[i]);
   HeapSort(a,n);
   printf("排序后的:\\n");
   for(i=0;i<n;i++)
    printf("%d\\t",a[i]);
}
-------------------------------------------------------------
对半排序
#include<stdio.h>
main()
{  int i,j,temp, low,high,mid,a[100],n;
  printf("请问你要输入几个数字:\\n");
   scanf("%d",&n);
   printf("请输入数字:\\n");
   for(i=0;i<n;i++)
    scanf("%d",&a[i]);
  for(i=1;i<n;i++)
  { temp=a[i];
    low=0;
high=i-1;
while(high>=low)
{   mid=(low+high)/2;
    if(temp<a[mid]) high=mid-1;
    else 
     low=mid+1;
}
for(j=i-1;j>=low;j--)
  a[j+1]=a[j];
a[low]=temp;
  }
     printf("排序后的:\\n");
     for(i=0;i<n;i++)
    printf("%d\\t",a[i]);
}
---------------------------------------------
快速排序
#include<stdio.h>
void QuickSort(int a[],int low,int high){
int i=low,j=high;
int temp=a[low];
while(i<j)
  {
   while(j>i&&temp<=a[j]) 
    j--;
      if(j>i)
   {
    a[i]=a[j];
        i++;
   
   }
   while(j>i&&a[i]<temp)
    i++;
   if(j>i)
   {
         a[j]=a[i];
   j--;
   }
  }
  a[i]=temp;
  if(low<i) QuickSort(a,low,i-1);
  if(i<high)QuickSort(a,j+1,high);
}
main()
{ int a[100];
  int  high ,low,i,n;
  printf("请问你要输入几个数字:\\n");
   scanf("%d",&n);
   printf("请输入数字:\\n");
   for(i=0;i<n;i++)
      scanf("%d",&a[i]);
  low=0;
  high=n-1;
  QuickSort(a,low,high);
  printf("排序后的:\\n");
  for( i=0;i<n;i++)
   printf("%d\\t",a[i]);
}
--------------------------------------
冒泡
#include<stdio.h>
main()
{int i,j,temp,n,a[100],flag=1;
   printf("请问你要输入几个排序数:\\n");
   scanf("%d",&n);
   printf("请输入你要排序的数值:\\n");
   for(i=0;i<n;i++)
    scanf("%d",&a[i]);
  for(i=0;i<n&&flag==1;i++)
  {    flag=0;
   for(j=1;j<n-i;j++)
    if(a[j]<a[j-1])
    {    flag=1; 
     temp=a[j-1];
        a[j-1]=a[j];
     a[j]=temp;
    }
  }
  printf("排序后的:\\n");
  for(i=0;i<n;i++)
  printf("%d\\t",a[i]);
}
---------------------------------------------------------
希尔
#include<stdio.h>
void ShellSort(int a[],int n,int d[],int numOfD)
{   int i,j,k,m,span,temp;
    for(m=0;m<=numOfD;m++)
{  span=d[m];
    for(k=0;k<span;k++)
    {  for(i=k;i<n-span;i=i+span)
       {
     temp=a[i+span];
     j=i;
     while(j>-1&&temp<=a[j])
     {  a[j+span]=a[j];
        j=j-span;
     }
     a[j+span]=temp;
    }
    }
}

}
main()
{int a[100], b[10],n,i,k,j;
  printf("请问你要输入几个数字:\\n");
   scanf("%d",&n);
   printf("请输入数字:\\n");
   for(i=0;i<n;i++)
      scanf("%d",&a[i]);
    j=n;
k=0;
   do{
     j=j/2;
  b[k]=j;
  k++;
   }while(j>0);
     ShellSort(a,n,b,k);
      printf("排序后的:\\n");
      for(i=0;i<n;i++)
   printf("%d\\t",a[i]);
}
---------------------------------------------
选择排序

#include<stdio.h>
main()
{int a[100], min,i,k,temp,j,cout;
  printf("请问你要输入几个数字(不要超过100个！！):\\n");
   scanf("%d",&cout);
   printf("请输入数字:\\n");
   for(i=0;i<cout;i++)
    scanf("%d",&a[i]);
for(i=0;i<cout;i++)
   { 
  min=i;
  for(k=i+1;k<cout;k++)
  {
   if(a[min]>a[k])
   {
    min=k;
       
   }
   
  }if(i!=min)
  {
   temp=a[i];
   a[i]=a[min];
   a[min]=temp;
  }
   }
for(j=0;j<cout;j++)
  printf("%d\\t",a[j]);
}
------------------------------------------
直接插入
#include<stdio.h>
main()
{ int i,j,n,temp,a[100];
   printf("请问你要输入几个数字:\\n");
   scanf("%d",&n);
   printf("请输入数字:\\n");
   for(i=0;i<n;i++)
      scanf("%d",&a[i]);
   for(i=0;i<n-1;i++)
   {  j=i;
      temp=a[i+1];
      while(temp<a[j]&&j>-1)
   {   a[j+1]=a[j];
        j--;
   }
   a[j+1]=temp;
   }
      printf("排序后的:\\n");
      for(i=0;i<n;i++)
    printf("%d\\t",a[i]);
}

排序算法是一种基本并且常用的算法。由于实际工作中处理的数量巨大，所以排序算法 
对算法本身的速度要求很高。 
而一般我们所谓的算法的性能主要是指算法的复杂度，一般用O方法来表示。在后面我将 
给出详细的说明。 

对于排序的算法我想先做一点简单的介绍，也是给这篇文章理一个提纲。 
我将按照算法的复杂度，从简单到难来分析算法。 
第一部分是简单排序算法，后面你将看到他们的共同点是算法复杂度为O(N*N)（因为没有 
使用word,所以无法打出上标和下标）。 
第二部分是高级排序算法，复杂度为O(Log2(N))。这里我们只介绍一种算法。另外还有几种 
算法因为涉及树与堆的概念，所以这里不于讨论。 
第三部分类似动脑筋。这里的两种算法并不是最好的（甚至有最慢的），但是算法本身比较 
奇特，值得参考（编程的角度）。同时也可以让我们从另外的角度来认识这个问题。 
第四部分是我送给大家的一个餐后的甜点——一个基于模板的通用快速排序。由于是模板函数 
可以对任何数据类型排序（抱歉，里面使用了一些论坛专家的呢称）。 

现在，让我们开始吧： 

一、简单排序算法 
由于程序比较简单，所以没有加什么注释。所有的程序都给出了完整的运行代码，并在我的VC环境 
下运行通过。因为没有涉及MFC和WINDOWS的内容，所以在BORLAND C++的平台上应该也不会有什么 
问题的。在代码的后面给出了运行过程示意，希望对理解有帮助。 

1.冒泡法： 
这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡： 
#include <iostream.h> 

void BubbleSort(int* pData,int Count) 
{ 
int iTemp; 
for(int i=1;i<Count;i++) 
{ 
for(int j=Count-1;j>=i;j--) 
{ 
if(pData[j]<pData[j-1]) 
{ 
iTemp = pData[j-1]; 
pData[j-1] = pData[j]; 
pData[j] = iTemp; 
} 
} 
} 
} 

void main() 
{ 
int data[] = ; 
BubbleSort(data,7); 
for (int i=0;i<7;i++) 
cout<<data[i]<<" "; 
cout<<"\n"; 
} 

倒序(最糟情况) 
第一轮：10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交换3次) 
第二轮：7,10,9,8->7,10,8,9->7,8,10,9(交换2次) 
第一轮：7,8,10,9->7,8,9,10(交换1次) 
循环次数：6次 
交换次数：6次 

其他： 
第一轮：8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交换2次) 
第二轮：7,8,10,9->7,8,10,9->7,8,10,9(交换0次) 
第一轮：7,8,10,9->7,8,9,10(交换1次) 
循环次数：6次 
交换次数：3次 

上面我们给出了程序段，现在我们分析它：这里，影响我们算法性能的主要部分是循环和交换， 
显然，次数越多，性能就越差。从上面的程序我们可以看出循环的次数是固定的，为1+2+...+n-1。 
写成公式就是1/2*(n-1)*n。 
现在注意，我们给出O方法的定义： 

若存在一常量K和起点n0，使当n>=n0时，有f(n)<=K*g(n),则f(n) = O(g(n))。（呵呵，不要说没 
学好数学呀，对于编程数学是非常重要的！！！） 

现在我们来看1/2*(n-1)*n，当K=1/2，n0=1，g(n)=n*n时，1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n) 
=O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。 
再看交换。从程序后面所跟的表可以看到，两种情况的循环相同，交换不同。其实交换本身同数据源的 
有序程度有极大的关系，当数据处于倒序的情况时，交换次数同循环一样（每次循环判断都会交换）， 
复杂度为O(n*n)。当数据为正序，将不会有交换。复杂度为O(0)。乱序时处于中间状态。正是由于这样的 
原因，我们通常都是通过循环次数来对比算法。 


2.交换法： 
交换法的程序最清晰简单，每次用当前的元素一一的同其后的元素比较并交换。 
#include <iostream.h> 
void ExchangeSort(int* pData,int Count) 
{ 
int iTemp; 
for(int i=0;i<Count-1;i++) 
{ 
for(int j=i+1;j<Count;j++) 
{ 
if(pData[j]<pData[i]) 
{ 
iTemp = pData[i]; 
pData[i] = pData[j]; 
pData[j] = iTemp; 
} 
} 
} 
} 

void main() 
{ 
int data[] = ; 
ExchangeSort(data,7); 
for (int i=0;i<7;i++) 
cout<<data[i]<<" "; 
cout<<"\n"; 
} 
倒序(最糟情况) 
第一轮：10,9,8,7->9,10,8,7->8,10,9,7->7,10,9,8(交换3次) 
第二轮：7,10,9,8->7,9,10,8->7,8,10,9(交换2次) 
第一轮：7,8,10,9->7,8,9,10(交换1次) 
循环次数：6次 
交换次数：6次 

其他： 
第一轮：8,10,7,9->8,10,7,9->7,10,8,9->7,10,8,9(交换1次) 
第二轮：7,10,8,9->7,8,10,9->7,8,10,9(交换1次) 
第一轮：7,8,10,9->7,8,9,10(交换1次) 
循环次数：6次 
交换次数：3次 

从运行的表格来看，交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样 
也是1/2*(n-1)*n，所以算法的复杂度仍然是O(n*n)。由于我们无法给出所有的情况，所以 
只能直接告诉大家他们在交换上面也是一样的糟糕（在某些情况下稍好，在某些情况下稍差）。 

3.选择法： 
现在我们终于可以看到一点希望：选择法，这种方法提高了一点性能（某些情况下） 
这种方法类似我们人为的排序习惯：从数据中选择最小的同第一个值交换，在从省下的部分中 
选择最小的与第二个交换，这样往复下去。 
#include <iostream.h> 
void SelectSort(int* pData,int Count) 
{ 
int iTemp; 
int iPos; 
for(int i=0;i<Count-1;i++) 
{ 
iTemp = pData[i]; 
iPos = i; 
for(int j=i+1;j<Count;j++) 
{ 
if(pData[j]<iTemp) 
{ 
iTemp = pData[j]; 
iPos = j; 
} 
} 
pData[iPos] = pData[i];