#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);
    }
}
/////////////////////////////////////////////////////////////////////