几种排序算法效率比较
#include <stdio.h>#include <time.h>
#include <stdlib.h>
#include <conio.h>
#define NUM 1024*10
void swap(int *p, int *q)
{
int tmp = *p;
*p = *q;
*q = tmp;
}
//////////////////选择排序///////////////////
void selectSort(int *p, int num)
{
for (int i = 0; i < num; i++)
{
int min = p[i];
int minindex = i;
for (int j = i; j < num; j++)
{
if (min > p[j])
{
min = p[j];
minindex = j;
}
}
swap(&p[minindex], &p[i]);
}
}
////////////////////////////////////////////////
///////////////////快速排序/////////////////////
int getSort(int *p, int min, int max)
{
int i = min;
int j = max;
int key = p[min];
while (1)
{
for (; ; j--)
{
if (i == j)
return i;
if (p[j] < key)
{
swap(&p[i], &p[j]);
i++;
break;
}
}
for (; ; i++)
{
if (i == j)
return i;
if (p[i] > key)
{
swap(&p[i], &p[j]);
j--;
break;
}
}
}
return -1;
}
void quickSort(int *p, int min, int max)
{
if (min >= max)
return ;
int i = getSort(p, min, max);
if (i < 0)
return ;
quickSort(p, min, i-1);
quickSort(p, i+1, max);
}
void quickSort2(int *p, int min, int max)
{
if (min >= max)
return ;
int i = min;
int j = max;
int key = (p[min]+p[min+1])/2;
int iIndex = i, jIndex = j;
while (1)
{
if (i == j)
break;
for (;; j--)
{
if (p[j] < key)
{
iIndex = j;
break;
}
if (i == j)
break;
}
for (;; i++)
{
if (p[i] >= key)
{
jIndex = i;
swap(&p[jIndex], &p[iIndex]);
break;
}
if (i == j)
break;
}
}
quickSort2(p, min, i);
quickSort2(p, i+1, max);
}
///////////////////////////////////////////////
///////////////////堆排序//////////////////////
void dealHeap(int *p, int index, int count)
{
if (2*index + 2 > count)
return ;
int left = 2*index + 1;
int right = 2*index + 2;
int m = p[left] > p[right] ? left : right;
if (p[m] > p[index])
{
swap(&p[m], &p[index]);
dealHeap(p, m, count);
}
}
void createHeap(int *p, int count)
{
for (int i = count; i >= 0; i--)
{
dealHeap(p, i, count);
}
}
void heapSort(int *p, int count)
{
createHeap(p, count);
for (int i = count; i >= 0; i--)
{
dealHeap(p, 0, i);
if (i != 1)
swap(&p[0], &p[i]);
}
}
//////////////////////////////////////////////////////
void writeData(int *buffer)
{
for (int i = 0; i < NUM; i++)
{
buffer[i] = rand()%20000 + 1;
}
FILE *fp = fopen("data.dat", "wb");
fwrite(buffer, sizeof(int), NUM, fp);
fclose(fp);
}
void readData(int *buffer)
{
FILE *fp = fopen("data.dat", "rb");
fread(buffer, sizeof(int), NUM, fp);
fclose(fp);
}
void usageMessage()
{
printf("1选择排序\n");
printf("2快速排序\n");
printf("3堆排序\n");
printf("q退出\n");
}
int main()
{
int *buffer = (int *)malloc(sizeof(int) * NUM);
writeData(buffer);
usageMessage();
int over = 1;
while (over)
{
readData(buffer);
float start;
switch(getche())
{
case '1':
{
start = clock()/1000.0f;
selectSort(buffer, NUM);
float end = clock()/1000.0f;
printf("\t选择排序 using time: %f\n", end-start);
break;
};
case '2':
{
start = clock()/1000.0f;
quickSort(buffer, 0, NUM-1);
float end = clock()/1000.0f;
printf("\t快速排序 using time: %f\n", end-start);
break;
}
case '3':
{
start = clock()/1000.0f;
heapSort(buffer, NUM-1);
float end = clock()/1000.0f;
printf("\t堆排序 using time: %f\n", end-start);
break;
}
case 'q':
{
//exit
over = 0;
}
}
}
free(buffer);
return 0;
}
1、通过三种算法的比较，当数据量大的时候，快速排序用时最短。数据量少的时候差别基本上不大。
2、这三种算法都不是很适合数据整体是顺序的情况、这个时候情况不理想。可以选择插入排序等来替换（有时间写一个测试一下）
3、从网上的理论上讲，堆排序在数据量很大的时候要优于快速排序。我这里堆排序总是稍微比快速排序慢一点点， 是不是堆排序写的有问题呢？
通过设置NUM宏的值来对数据量不同的情况进行测试。编译环境vs2008 + win7
