#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表示需要继续冒泡*/  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];    }    /*循环结束时array[j]<=key,将key插入到j+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++)  /*下面对一组序列进行插入排序*/   {    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]已经满足堆的定义，调整使得array[start] ~ array[end]满足堆定义*/ void HeapAdjust (int start, int end, int array[]) {  int i;  int temp = array[start]; /*产生第一个空白*/  for (i=2*start+1; i<=end; i=2*i+1)  /*每次循环时空白节点为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;  /*插入原来的temp到空白处*/ } void HeapSort (int n, int array[]) {  int i;  for (i=(n-2)/2; i>=0; i--)  /*构造大顶堆*/   HeapAdjust(i, n-1, array);  for (i=n-1; i>0; i--)  {   int t = array[i]; /*将根节点交换到数组末端*/   array[i] = array[0];   array[0] = t;   HeapAdjust(0, i-1, array); /*重新调整堆*/  } } /*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) /*递归调用*/ {  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) /*非递归实现归并排序*/ {  int k, i;  for (k=1; 2*k<n; k *= 2) /*设置每段待归并的有序序列的长度：1,2,4,8,16……*/  {   for (i=0; i+k-1<n; i += 2*k) /*考虑待归并的左右两段序列，[i+k-1]是左序列末尾元素下标*/   {        /*[end=i+2*k-1]是右序列末尾元素下标,end不应该超过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("下面比较几个时间复杂度为NlogN的排序算法效率高低,其他3个低效率的排序就不考虑了\n");  printf("输入待排序数量（int类型表示,在我的机器上超过100万就可能溢出）:\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个数据花费时间为： %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个数据花费时间为： %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个数据花费时间为： %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个数据花费时间为： %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个数据花费时间为： %ldms\n", n, (stop-start)*1000/CLOCKS_PER_SEC); /* for(i=0; i<n; i++)  {   printf("%d ", a[i]);  } */  return 0; }