复制代码 代码如下:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void BubbleSort1 (int n, int *array)
{
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;
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+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);
}

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)
{
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;
}
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);
}
}

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)
{
for (i=0; i+k-1<n; i += 2*k)
{/*[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);

return 0;
}