#include <stdio.h>
#include <time.h>
#define N 100000
/*库比较函数:qsort(int *base,int n,int struct_size,int (*compare)(const
void *,const void *))中的比较函数*/
int compare(const void *first, const void *second)
{
if (*(int *)first > *(int *)second)/*当第一个数比第二个数大的时候,
就进行排序,排序的结果是从小到大*/
return 1;
else
return -1;
}
/*希尔排序*/
void ShellInsert(int *a, int n, int d)
{
int i, j, temp;
for (i = d; i < n; ++i){
j = i - d;
temp = a[i];
while (j >= 0 && temp < a[j]){
a[j + d] = a[j];
j -= d;
}
a[j + d] = temp;
}
}
void ShellSort(int *a, int n)
{
int d = n / 2;
while (d >= 1){
ShellInsert(a,n,d);
d /= 2;
}
}
/*快速排序*/
void QuickSort(int *a,int low,int high)
{
int l = low, h = high, temp;
if (l < h){
temp = a[low];
while (l != h){
while (l<h&&a[h]>temp)
--h;
if (l < h){
a[l] = a[h];
++l;
}
while (l < h&&a[l] < temp)
++l;
if (l < h){
a[h] = a[l];
--h;
}
}
a[l] = temp;
QuickSort(a,low,l-1);
QuickSort(a,h+1,high);
}
}
/*堆排序*/
void HeapInsert(int *a, int low, int high)
{
int i = low, j = low * 2, temp = a[i];
while (j <= high){
if (j < high && a[j] < a[j + 1])
++j;
if (temp < a[j]){
a[i] = a[j];
i = j;
j *= 2;
}
else
break;
}
a[i] = temp;
}
void HeapSort(int *a, int n)
{
int i, temp;
for (i = n / 2; i >= 0; --i)
HeapInsert(a,i,n-1);
for (i = n - 1; i >= 1; --i){
temp = a[i];
a[i] = a[0];
a[0] = temp;
HeapInsert(a,0,i-1);
}
}
/*折半排序*/
void BinarySort(int *a,int n)
{
int i, j, low, middle, high, temp;
for (i = 1; i < n; ++i){
low = 0;
high = i - 1;
temp = a[i];
while (low <= high){
middle = (low + high) / 2;
if (temp < a[middle])
high = middle - 1;
else
low = middle + 1;
}
for (j = i - 1; j > high; --j)
a[j + 1] = a[j];
a[low] = temp;
}
}
void initArray(int *a, int n)
{
srand(time(NULL));
int i;
for (i = 0; i < n; ++i)
a[i] = rand() % 100;
}
void print(int *a,int n)
{
int i;
for (i = 0; i < n; ++i){
printf("%d ", a[i]);
if (i && i % 20 == 0)
printf("\n");
}
printf("\n");
}
int main()
{
int a[N];
double start, finish;
//initArray(a, N);
//printf("排序前:\n");
//print(a, N);/*排序前*/
/*计算系统库函数排序消耗的时间*/
initArray(a, N);
start = clock();
qsort(a, N, sizeof(int), compare);
finish = clock();
printf("System library sort cost %.3fSeconds\n", (finish - start) /
1000);
/*计算折半插入排序消耗的时间*/
initArray(a, N);
start = clock();
BinarySort(a,N);
finish = clock();
printf("Binary sort cost %.3fSeconds\n", (finish - start) / 1000);
/*计算堆排序消耗的时间*/
initArray(a, N);
start = clock();
HeapSort(a, N);
finish = clock();
printf("Heap sort cost %.3fSeconds\n", (finish - start) / 1000);
/*计算希尔排序消耗的时间*/
initArray(a, N);
start = clock();
ShellSort(a, N);
finish = clock();
printf("Shell sort cost %.3fSeconds\n", (finish - start) / 1000);
/*计算快速排序消耗的时间*/
initArray(a, N);
start = clock();
QuickSort(a, 0, N - 1);
finish = clock();
printf("Quick sort cost %.3fSeconds\n", (finish - start) / 1000);
//printf("排序后:\n");
//print(a, N);
return 0;
}
对c语言系统库函数、堆排序、希尔排序、折半插入排序、快速排序消耗时间的比较,布布扣,bubuko.com
对c语言系统库函数、堆排序、希尔排序、折半插入排序、快速排序消耗时间的比较