// 快速排序.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream> 
#include <ctime>
#include<time.h>
#include<math.h>


using namespace std; 
const int N=20;

int R[N];
int nums[N];
struct SqList
{int r[N+1];
int length;
};
  void  Initial(SqList &SL,int nums[],int len)   
  {  
  for(int i = 0; i<len; i++)   
  SL.r[i]=nums[i];   
  SL.length=len;   
  }  
 void InsertSort(SqList &SL)           //直接插入排序   
  {   
  int   temp;   
  for(int i=1;i<SL.length;i++)   
  if(SL.r[i]<SL.r[i-1])   
  {   
  temp=SL.r[i];   
  for(int j =i-1; (temp<SL.r[j])&&(j>=0);j--)//這里的循環條件   
  SL.r[j+1]=SL.r[j];   
  SL.r[j+1]=temp;   
  }   
  }   
//快排的無返回型函數 
void qs(int data[],int low,int high)//data[]數組,low最低位,high最高位 
{ 
     int i,pivot,j; 
     if(low<high) 
     { 
       pivot = data[low];i=low;j=high;//pivot存儲支點值，初始化i,j 
     
       while(i<j) 
       { 
         while(i<j&&data[j]>=pivot) j--;//低位小于高位且高位值>=支點 高位左移1位 
  
         if(i<j) data[i++]=data[j];//低位右一位賦值為高位 
         while (i<j&&data[i]<=pivot) i++; 
         if(i<j) data[j--]=data[i];//則高位左一位賦值為低位 
       } 
       data[i]=pivot;//高低位重合點賦值為支點 
       //此時i左全部小于支點，右全部大于支點 
       qs(data,low,i-1); 
       qs(data,i+1,high);//遞歸調用，分別排序左右兩部分 
  
     } 
} 
  void Heapify(int s,int m) 
{ /*對R[1..n]進行堆調整，用temp做暫存單元 */ 
     int j,temp; 
     temp=R[s]; 
     j=2*s; 
     while (j<=m) 
     { 
      if (R[j]<R[j+1]&&j<m) j++; 
      if (temp>R[j]) break; 
      R[s]=R[j]; 
          s=j; 
          j=j*2; 
     }/* end of while */ 
     R[s]=temp; 
} /* end of Heapify */ 

void BuildHeap(int n) 
{ /* 由一個無序的序列建成一個堆 */ 
   int i; 
   for(i=n/2;i>0;i--) 
      Heapify(i,n); 
} 


void Heap_Sort(int n) 
{ /* 對R[1..n]進行堆排序，不妨用R[0]做暫存單元 */ 
    int i; 
    BuildHeap(n); /* 將R[1-n]建成初始堆 */ 
    for(i=n;i>1;i--) 
    { /* 對當前無序區R[1..i]進行堆排序，共做n-1趟。 */ 
        R[0]=R[1]; R[1]=R[i];R[i]=R[0]; /* 將堆頂和堆中最后一個記錄交換 */ 
        Heapify(1,i-1); /* 將R[1..i-1]重新調整為堆，僅有R[1]可能違反堆性質 */ 
    } /* end of for */ 
} /* end of Heap_Sort */ 
void main() 
{
	int i;
	int cp[N+1];
cout<<"Please input "<<N<<" numbers:\n";
for(i=0;i<N;i++)
{
 nums[i]=rand()/10+1;
 R[i+1]=nums[i];
 cp[i]=nums[i];
}
     for(i=0;i<N;i++)
{
cout<<nums[i]<<" ";
}
cout<<endl; 
	clock_t s1,f1;
	double d1;
	s1=clock();
    qs(nums,0,N-1); 

   f1=clock();
   d1=(double)(f1-s1)/CLOCKS_PER_SEC;
   printf("快速排序時間為%f\n",d1);
    
   
	
  // d1=(double)(f1-s1)/CLOCKS_PER_SEC;
  
 cout<<"快速排序結果為:\n";   
    for(i=0;i<N;i++)
{
cout<<nums[i]<<" ";
}
cout<<endl; 
	clock_t s2,f2;
	double d2;
	s2=clock();
    Heap_Sort(N); 

   f2=clock();
   d2=(double)(f2-s2)/CLOCKS_PER_SEC;
   printf("堆排序的時間為%f\n",d2);

    puts("\n堆排序結果為:\n"); 
    for(i=1;i<=N;i++) 
        printf("%d\t",R[i]); 
	puts("\n直接插入排序結果為:\n");
	SqList SL;
	Initial(SL,cp,N);   
		clock_t s3,f3;
	double d3;
	s3=clock();
   InsertSort(SL);  

   f3=clock();
   d3=(double)(f3-s3)/CLOCKS_PER_SEC;
   printf("直接插入排序時間為%f\n",d3);
	  
	for(  i   =   0;   i   <   SL.length;   i++)   
  cout<<SL.r[i]<<"   "; 
   
  cout<<endl;  
   printf("快速排序時間為%f\n",d1);
  printf("堆排序的時間為%f\n",d2);
 printf("直接插入排序時間為%f\n",d3);
}