#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void BubbleSort1 (int n, int *array) /*little > big*/
{
 int i, j;
 for (i=0; i<n-1; i++)
 {
  for (j=n-1; j>i; j--)
  {
   if (array[j] < array[j-1])
   {
    int temp = array[j];
    array[j] = array[j-1];
    array[j-1] = temp;
   }
  }
 }
}

void BubbleSort2 (int n, int *array)
{
 int i, j, flag=1; /*flag=1表示需要繼續(xù)冒泡*/
 for (i=0; i<n-1 && flag; i++)
 {
  flag = 0;
  for (j=n-1; j>i; j--)
  {
   if (array[j] < array[j-1])
   {
    int temp = array[j];
    array[j] = array[j-1];
    array[j-1] = temp;
    flag = 1;
   }
  }
 }
}

void SelectSort (int n, int *array)
{
 int i, j, min;
 for (i=0; i<n-1; i++)
 {
  min = i;
  for (j=i+1; j<n; j++)
  {
   if (array[min] > array[j])
    min = j;
  }
  int temp = array[min];
  array[min] = array[i];
  array[i] = temp;
 }
}

void InsertSort (int n, int*array)
{
 int i, j;
 for (i=1; i<n; i++)
 {
  if (array[i] < array[i-1]) /*是否需要插入*/
  {
   int key = array[i]; //哨兵
   for (j = i-1;j>=0 && array[j] > key; j--)
   {
    array[j+1] = array[j];
   }
   /*循環(huán)結(jié)束時(shí)array[j]<=key,將key插入到j(luò)+1處*/
   array[j+1] = key;
  }
 }
}

/*分組插入排序*/
void ShellSort (int n, int *array)
{
 int i, j;
 int increment;
 for (increment=n/2; increment > 0; increment /= 2)
 {
  for (i=0; i<increment; i++)  /*下面對(duì)一組序列進(jìn)行插入排序*/
  {
   for (j=i+increment; j<n; j+=increment)
   {
    if (array[j] < array[j-increment])
    {
     int key = array[j];
     int k;
     for (k=j-increment; k>=0 && array[k]>key; k -= increment)
     {
      array[k+increment] = array[k];
     }
     array[k+increment] = key;
    }
   }
  }
 }
}

/*分治法*/
void QuickSort (int left, int right, int *array)
{
 if(left>=right)
  return ;
 int i=left, j=right;
 int key=array[i];
 while (i<j)
 {
  while (i<j && array[j]>=key)
   j--;
  array[i] = array[j];
  while (i<j && array[i]<=key)
   i++;
  array[j] = array[i];
 }
 array[i] = key;
 QuickSort(left, i-1, array);
 QuickSort(i+1, right, array);
}

/*array[start+1] ~ array[end]已經(jīng)滿足堆的定義，調(diào)整使得array[start] ~ array[end]滿足堆定義*/
void HeapAdjust (int start, int end, int array[])
{
 int i;
 int temp = array[start]; /*產(chǎn)生第一個(gè)空白*/
 for (i=2*start+1; i<=end; i=2*i+1)  /*每次循環(huán)時(shí)空白節(jié)點(diǎn)為array[(i-1)/2]*/
 {
  if (i<end && array[i] < array[i+1])  /*在左右孩子中尋找較大值*/
   i++;
  if (array[i] > temp)
   array[(i-1)/2] = array[i];
  else
   break;
 }
 array[(i-1)/2] = temp;  /*插入原來(lái)的temp到空白處*/
}
void HeapSort (int n, int array[])
{
 int i;
 for (i=(n-2)/2; i>=0; i--)  /*構(gòu)造大頂堆*/
  HeapAdjust(i, n-1, array);

 for (i=n-1; i>0; i--)
 {
  int t = array[i]; /*將根節(jié)點(diǎn)交換到數(shù)組末端*/
  array[i] = array[0];
  array[0] = t;

  HeapAdjust(0, i-1, array); /*重新調(diào)整堆*/
 }
}

/*array[s…m]和array[m+1…t]均已各自有序，合并使得array[s…t]有序*/
void Merge(int s, int m, int t, int *array)
{
 int temp[t-s+1];
 int i=s, j=m+1, k=0;
 while(i<=m && j<=t)
 {
  if(array[i] < array[j])
   temp[k++] = array[i++];
  else
   temp[k++] = array[j++];
 }
 while(i<=m)
  temp[k++] = array[i++];
 while(j<=t)
  temp[k++] = array[j++];

 for(i=s, k=0; i<=t && k<=t-s; i++, k++)
 {
  array[i] = temp[k];
 }
}
void MSort (int s, int t, int *array) /*遞歸調(diào)用*/
{
 if(s == t)
  return ;
 int m = (s+t)/2;
 MSort(s, m, array);
 MSort(m+1, t, array);
 Merge(s, m, t, array);
}
void MergeSort1(int n, int *array)
{
 MSort(0, n-1, array);
}
void MergeSort2(int n, int *array) /*非遞歸實(shí)現(xiàn)歸并排序*/
{
 int k, i;
 for (k=1; 2*k<n; k *= 2) /*設(shè)置每段待歸并的有序序列的長(zhǎng)度：1,2,4,8,16……*/
 {
  for (i=0; i+k-1<n; i += 2*k) /*考慮待歸并的左右兩段序列，[i+k-1]是左序列末尾元素下標(biāo)*/
  {        /*[end=i+2*k-1]是右序列末尾元素下標(biāo),end不應(yīng)該超過(guò)n-1*/
   int end=i+2*k-1;
   if(end > n-1)
    end = n-1;
   Merge(i, i+k-1, end, array);
  }
 }
}

int main()
{
 long start, stop;
 int n;
 printf("下面比較幾個(gè)時(shí)間復(fù)雜度為NlogN的排序算法效率高低,其他3個(gè)低效率的排序就不考慮了\n");
 printf("輸入待排序數(shù)量（int類型表示,在我的機(jī)器上超過(guò)100萬(wàn)就可能溢出）:\n");
 scanf("%d", &n);
 int a[n], i;

 for(i=0; i<n; i++)
  a[i] = rand()%n;
 start = clock();
 ShellSort(n, a);
 stop = clock();
 printf("希爾排序%d個(gè)數(shù)據(jù)花費(fèi)時(shí)間為： %ldms\n", n, (stop-start)*1000/CLOCKS_PER_SEC);

 for(i=0; i<n; i++)
  a[i] = rand()%n;
 start = clock();
 HeapSort(n, a);
 stop = clock();
 printf("堆排序%d個(gè)數(shù)據(jù)花費(fèi)時(shí)間為： %ldms\n", n, (stop-start)*1000/CLOCKS_PER_SEC);

 for(i=0; i<n; i++)
  a[i] = rand()%n;
 start = clock();
 MergeSort1(n, a);
 stop = clock();
 printf("遞歸式歸并排序%d個(gè)數(shù)據(jù)花費(fèi)時(shí)間為： %ldms\n", n, (stop-start)*1000/CLOCKS_PER_SEC);

 for(i=0; i<n; i++)
  a[i] = rand()%n;
 start = clock();
 MergeSort2(n, a);
 stop = clock();
 printf("非遞歸式歸并排序%d個(gè)數(shù)據(jù)花費(fèi)時(shí)間為： %ldms\n", n, (stop-start)*1000/CLOCKS_PER_SEC);

 for(i=0; i<n; i++)
  a[i] = rand()%n;
 start = clock();
 QuickSort(0, n-1, a);
 stop = clock();
 printf("快速排序%d個(gè)數(shù)據(jù)花費(fèi)時(shí)間為： %ldms\n", n, (stop-start)*1000/CLOCKS_PER_SEC);

/* for(i=0; i<n; i++)
 {
  printf("%d ", a[i]);
 }
*/
 return 0;
}