写了几种常用的排序算法，并测试比较它们在不同N时花费的时间。
50000以下的整数，一些结果如下：
可见 在N为10和200的时候插入排序比较好；
4000和10000的时候希尔排序不错，10000的时候归并排序最好，但是它需要不断的拷贝；
10000以上快排有很好的效果。
root@ubuntu:sorts# ./a.out
Input your N:10
Input your times for every sort:3
======================================================
N:10, times:3
q_sort 5(0.00 sec) 2(0.00 sec) 2(0.00 sec) Average:3.00(0.00 sec)
merge_sort 5(0.00 sec) 3(0.00 sec) 3(0.00 sec) Average:3.67(0.00 sec)
insert_sort 2(0.00 sec) 2(0.00 sec) 1(0.00 sec) Average:1.67(0.00 sec)
bubble_sort 2(0.00 sec) 2(0.00 sec) 2(0.00 sec) Average:2.00(0.00 sec)
shell_sort 3(0.00 sec) 2(0.00 sec) 2(0.00 sec) Average:2.33(0.00 sec)
root@ubuntu:sorts# ./a.out
Input your N:200
Input your times for every sort:3
======================================================
N:200, times:3
q_sort 123(0.00 sec) 40(0.00 sec) 33(0.00 sec) Average:65.33(0.00 sec)
merge_sort 97(0.00 sec) 69(0.00 sec) 66(0.00 sec) Average:77.33(0.00 sec)
insert_sort 124(0.00 sec) 125(0.00 sec) 127(0.00 sec) Average:125.33(0.00 sec)
bubble_sort 561(0.00 sec) 440(0.00 sec) 395(0.00 sec) Average:465.33(0.00 sec)
shell_sort 107(0.00 sec) 45(0.00 sec) 38(0.00 sec) Average:63.33(0.00 sec)
root@ubuntu:sorts# ./a.out
Input your N:4000
Input your times for every sort:3
======================================================
N:4000, times:3
q_sort 1392(0.00 sec) 4582(0.00 sec) 1143(0.00 sec) Average:2372.33(0.00 sec)
merge_sort 1753(0.00 sec) 1464(0.00 sec) 1497(0.00 sec) Average:1571.33(0.00 sec)
insert_sort 30011(0.03 sec) 21558(0.02 sec) 20967(0.02 sec) Average:24178.67(0.02 sec)
bubble_sort 68045(0.07 sec) 68638(0.07 sec) 69282(0.07 sec) Average:68655.00(0.07 sec)
shell_sort 1202(0.00 sec) 1154(0.00 sec) 1136(0.00 sec) Average:1164.00(0.00 sec)
root@ubuntu:sorts# ./a.out
Input your N:10000
Input your times for every sort:3
======================================================
N:10000, times:3
q_sort 5570(0.01 sec) 3338(0.00 sec) 3031(0.00 sec) Average:3979.67(0.00 sec)
merge_sort 2770(0.00 sec) 3847(0.00 sec) 2726(0.00 sec) Average:3114.33(0.00 sec)
insert_sort 132152(0.13 sec) 137268(0.14 sec) 130461(0.13 sec) Average:133293.67(0.13 sec)
bubble_sort 532980(0.53 sec) 541508(0.54 sec) 532720(0.53 sec) Average:535736.00(0.54 sec)
shell_sort 4003(0.00 sec) 3989(0.00 sec) 4004(0.00 sec) Average:3998.67(0.00 sec)
root@ubuntu:sorts# ./a.out
Input your N:200000
Input your times for every sort:3
======================================================
N:200000, times:3
q_sort 56209(0.06 sec) 49304(0.05 sec) 51153(0.05 sec) Average:52222.00(0.05 sec)
merge_sort 76010(0.08 sec) 70382(0.07 sec) 69384(0.07 sec) Average:71925.33(0.07 sec)
insert_sort 53082750(53.08 sec) 60855177(60.86 sec) 55608651(55.61 sec) Average:56515526.00(56.52 sec)
bubble_sort 251693776(251.69 sec) 247223993(247.22 sec) 247935804(247.94 sec) Average:248951191.00(248.95 sec)
shell_sort 830143(0.83 sec) 823296(0.82 sec) 858193(0.86 sec) Average:837210.67(0.84 sec)
root@ubuntu:sorts# vi sorts.c
root@ubuntu:sorts#
=====================以下是代码============================
#include "stdio.h"
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include <string.h>
#include <sys/times.h>
#include <unistd.h>
int bubble_sort(unsigned int * array, int a_len);
int insert_sort(unsigned int * array, int a_len);
typedef int (*sort_funs_t)(unsigned int *array, int a_len);
/*************************start of q sort **********************/
#define Cutoff (10)
static inline void Swap(unsigned int * a1, unsigned int * a2)
{
unsigned int tmp;
tmp = *a1;
*a1 = *a2;
*a2 = tmp;
}
static inline unsigned int find_mid(unsigned int * array, int start, int end)
{
int mid = (start + end) / 2;
if (array[start] > array[mid]) {
Swap(&array[start], &array[mid]);
}
if (array[start] > array[end]) {
Swap(&array[start], &array[end]);
}
if ( array[mid] > array[end] ) {
Swap(&array[mid], &array[end]);
}
Swap(&array[mid], &array[end-1]);
return array[end-1];
}
int my_qsort(unsigned int * array, int start, int end)
{
int i, j;
if (start + Cutoff <= end) {
unsigned int mid_value = find_mid(array, start, end);
i = start, j = end-1;
for (;;) {
while (array[ ++i ] < mid_value);
while (array[ --j ] > mid_value);
if (i < j) {
Swap(&array[i], &array[j]);
}
else {
break;
}
}
Swap(&array[i], &array[end-1]);
my_qsort(array, start, i - 1);
my_qsort(array, i+1, end);
}
else {//这里N <10的时候我们用插入排序
//bubble_sort(array + start, end - start +1);
insert_sort(array+start, end - start + 1);
}
return 0;
}
int q_sort(unsigned int * array, int a_len)
{
return my_qsort( array, 0, a_len-1);
}
/*************************end of q sort **********************/
/*************************start of merge sort **********************/
int merge(unsigned int * A, unsigned int * tmp,
int start, int mid, int end)
{
int i = start, j = mid+1;
int k = start, merge_len = end - start + 1;
while (i <= mid && j <=end) {
if (A[i] <= A[j]) {
tmp[k++] = A[i++];
}
else {
tmp[k++] = A[j++];
}
}
while (i <= mid) {
tmp[k++] = A[i++];
}
while (j <= end) {
tmp[k++] = A[j++];
}
for (i = 0; i < merge_len; i++) {
A[start+i] = tmp[start+i];
}
//memcpy(&A[start], &tmp[start], k*sizeof( unsigned int));
return k;
}
int Msort(unsigned int * A, unsigned int * tmp, int start, int end)
{
if (start < end) {
int mid = (start + end) / 2;
Msort(A, tmp, start, mid);
Msort(A, tmp, mid+1, end);
merge(A, tmp, start, mid, end);
}
}
int merge_sort(unsigned int * A, int a_len)
{
unsigned int * tmp = malloc( sizeof(unsigned int) * a_len);
if (tmp) {
memset(tmp, 0, sizeof(unsigned int) * a_len);
Msort(A, tmp, 0, a_len-1);
}
else {
printf("malloc error!!\n");
return -1;
}
free(tmp);
return 0;
}
/*************************start of merge sort **********************/
/*************************start of insert sort **********************/
int insert_sort(unsigned int * array, int a_len)
{
unsigned int tmp = 0;
int i, j;
for (i = 1; i < a_len; i++) {
tmp = array[i];
for (j = i-1; j >= 0 && (array[j] > tmp); j--) {
array[j+1] = array[j];
}
array[j+1] = tmp;
}
return 0;
}
/*************************start of insert sort **********************/
/*************************start of shell sort **********************/
int shell_sort(unsigned int * array, int a_len)
{
int shell_i[] = {109,41, 19, 5, 1}, i, j, k;
int shell_num = sizeof(shell_i) / sizeof(shell_i[0]);
unsigned int tmp;
for (i = 0; i < shell_num; i++) {
for (j = shell_i[i]; j < a_len; j++) {
tmp = array[j];
for (k = j-shell_i[i]; k >= 0 && (array[k] > tmp); k -= shell_i[i]) {
array[k + shell_i[i]] = array[k];
}
array[k+shell_i[i]] = tmp;
}
}
}
/*************************end of shell sort **********************/
/*************************start of bub sort **********************/
//冒牌排序，没有冒泡的时候说明已经排好序，或者记住交换的点，少排些序
int bubble_sort(unsigned int * array, int a_len)
{
int i,j, swaped = 1, swap_pos = a_len-1;
unsigned int tmp = 0;
for (i = a_len-1; i > 0 && (swaped); i--) {
swaped = 0;
for (j = 0; j < i; j++) {
if (array[j] > array[j+1]) {
tmp = array[j+1];
array[j+1] = array[j];
array[j] = tmp;
swaped = 1;
swap_pos = j + 1;
}
}
i = swap_pos;
}
}
/*************************end of bub sort **********************/
void print_array(unsigned int * array, int a_len)
{
size_t i;
printf("========================\n");
for (i = 0; i < a_len; i++ ) {
printf(" %u", array[i]);
}
printf("\n########################\n");
}
unsigned int choose_issue(unsigned int * array, int a_len, int k, sort_funs_t sort_fun)
{
//print_array(array, a_len);
sort_fun(array, a_len);
//print_array(array, a_len);
return array[k-1];
}
unsigned int * full_array( int n )
{
int a_len, i;
unsigned int * array = NULL;
a_len = n * sizeof(unsigned int);
array = malloc(a_len);
if (array) {
memset(array, 0, a_len);
srand(time(NULL));
for (i = 0; i < n; i++) {
array[i] = rand() % 50000;
}
}
else {
assert(0);
}
return array;
}
char func_name[][12] = {
"q_sort",
"merge_sort",
"insert_sort",
"bubble_sort",
"shell_sort",
};
int sorts_test(int N, int times)
{
clock_t startClock[5][times], stopClock[5][times];
long cnt = 0, tmp = 0;
unsigned int *array = NULL;
sort_funs_t sort_funs[5];
int i, j;
sort_funs[0] = q_sort;
sort_funs[1] = merge_sort;
sort_funs[2] = insert_sort;
sort_funs[3] = bubble_sort;
sort_funs[4] = shell_sort;
for (j = 0; j < times; j++) {
if (N >= 50000 && (i == 3 || i == 2)) {//too large skip insert_sort and bubble_sort.
startClock[i][j] = 0;
stopClock[i][j] = 0;
continue;
}
array = full_array( N );
startClock[i][j] = clock();
choose_issue(array, N, N/2, sort_funs[i]);
stopClock[i][j] = clock();
if (array) free(array);
}
}
printf("======================================================\n");
printf("N:%d, times:%d\n", N, times);
for (i = 0; i < 5; i++) {
printf("%-12s ", func_name[i]);
cnt = 0;
for (j = 0; j < times; j++) {
tmp = (stopClock[i][j] - startClock[i][j]);
cnt += tmp;
printf("%ld(%.2f sec)\t", tmp, (double)(tmp)/CLOCKS_PER_SEC);
}
printf("\t Average:%.2lf(%.2f sec)\n", (double)cnt/times, (double)cnt/times/CLOCKS_PER_SEC);
}
}
{
int N, times;
printf("Input your N:");
scanf("%d", &N);
while(getchar() != '\n');
printf("Input your times for every sort:");
scanf("%d", ×);
sorts_test(N, times);
}
root@ubuntu:sorts#