sort.cpp

7中内排序的c语言代码,包括:直接插入,shell,选择,冒泡,等等排序算法

#include "stdio.h"
void insert(int [], int);//直接插入法
void shellsort(int [], int);//希尔排序(复合的直接插入法)
void select(int [], int);//选择排序法
void bubble(int [], int);//冒泡排序法（属于交换排序）
void quicksort(int [], int, int);//快速排序（属于交换排序）
void heapsort(int [],int);//堆排序
void heapadjust(int [],int i, int);//堆的调整（指具体某一变量的筛选过程）
const int len=10; 
int main( )
{
 int i;
 int a[len]={ 5,12,3,7,4,15,30,21,16,8};
 int low=0, high=len-1;
// for(i=0; i<len;i++)
//  scanf ("%d",&a[i]);
//  insert(a, len);//直接插入法
// shellsort(a, len);//希尔排序(复合的直接插入法)
// select(a, len);//选择排序法
// bubble(a, len);//冒泡排序法（交换排序）
// quicksort(a, low,high);//快速排序（交换排序）
// heapsort(a,len);//堆排序
 for(i=0;i<len;i++)
 {
  printf("%5d",a[i]);
 }
 return 0;
}


// 方法一：直接插入法
void insert(int a[ ], int len)//直接插入法
{
 int i, j,inserter; 
 int n=len;
 for(i=1;i<=n-1;i++)//共进行n-1趟比较 
 {
  inserter=a[i]; j=i-1; 
  while(j>=0&&inserter<a[j])
  {
   a[j+1]=a[j];
   j--;
  }
  a[j+1]=inserter;
 }
}


// 方法二：希尔排序法
void shellsort(int a[ ], int len)
{
 int d=len, i;
 while(d>1)
 {
  d=(d+1)/2;//每趟希尔排序的步长（该式子也决定了总的希尔排序趟数） 
  for(i=0;i<len-d;i++)//具体的一趟希尔排序
  {
   int temp;
   if(a[i]>a[i+d])
   {
     temp=a[i+d];
     a[i+d]=a[i];
     a[i]=temp;
   }
  }
 }
}



// 方法三：选择排序法
void select(int a[ ], int len)
{
 int n=len, i, j;
 for(i=0;i<n-1;i++)//共n-1轮比较
  {
   for(j=i+1;j<n;j++)
   {
     int temp;
     if(a[i]>a[j])
	 {
      temp=a[i];
      a[i]=a[j];
      a[j]=temp;
	 }
   }
 }
}


// 方法四：冒泡排序法
void bubble(int a[ ], int len)
{
 int n=len, i, j;
 for(i=1;i<n;i++)//共n-1轮比较
  {
   for(j=0;j<n-i;j++)
   {
     int temp;
     if(a[j]>a[j+1])
	 {
      temp=a[j+1];
      a[j+1]=a[j];
      a[j]=temp;
	 }
   }
  }
}


// 方法五：快速排序法
void quicksort(int a[ ], int low, int high)
{
 int i=low,j=high; 
 if(i<j)
 {
  int pivot=a[i];//选出基准记录
  while(i<j)
  {
   while(i<j&&a[j]>pivot)
   j--;
   if(i<j)
   a[i++]=a[j];
   while(i<j&&a[i]<pivot)
   i++;
   if(i<j)
   a[j--]=a[i];
  }
  a[i]=pivot;//此时的i位置为基准的实际位置,a[i]就为基准变量(完成一趟快速排序)
  /*以上语句相当于完成partion(int [],int,int)函数的功能*/
  quicksort(a, low, i-1);//对子区间再进行快速排序
  quicksort(a, i+1,high);
 }
}

/*///////////方法六：堆排序////////////////////////*/


void heapadjust(int a[], int i, int heapsize)
{
	int pivot=a[i];//基准元素(i对应元素在数组中的实际位置）
	int current=i;
    int child=current*2+1;
	while(child<heapsize)
	{
		if(child<heapsize-1&&a[child]<a[child+1])
		   child=child+1;
		if(pivot>=a[child])
			break;//提前结束该循环语句
		else
		{
		  a[current]=a[child];
		  current=child;
		  child=current*2+1;
		}
	}
	a[current]=pivot;
}

void heapsort(int a[], int len)
{
    int i;

    for (i = len/ 2-1; i >= 0; i--)//整个for循环完成初始时大顶堆的构建
        heapadjust(a, i, len);     
    for (i = len-1; i >= 1; i--)              
    {
        int temp;
		temp=a[i];
        a[i]=a[0];
		a[0]=temp;
        heapadjust(a, 0, i);
    }
}
/////////////////////////////////////////////////////////////////////