各类排序比较

在写完了各个排序的具体介绍后，现在对各种排序的具体时间做一下比较，形象的看看各个排序的性能(如果对里面具体哪个排序算法不太了解，可以参看博主有关文章)

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <time.h>

using namespace std;

//直接插入排序
void insert_sort(int* a, int n)
{
	for (int i = 1; i < n; ++i)
	{
		int j = i - 1;
		int temp = a[i];
		while (j >= 0 && a[j] > temp)
		{
			a[j + 1] = a[j];
			--j;
		}

		a[j + 1] = temp;
	}
}

//希尔排序
void shell_sort(int* a, int n)
{
	int gap = n / 2;
	while (gap != 0)
	{
		for (int i = gap; i < n; ++i)
		{
			int j = i - gap;
			int temp = a[i];
			while (j >= 0 && a[j] > temp)
			{
				a[j + gap] = a[j];
				j = j - gap;
			}

			a[j + gap] = temp;
		}

		gap = gap / 2;
	}
}

//冒泡排序
void bubble_sort(int* a, int n)
{
	for (int i = 0; i <= n - 1; ++i)
	{
		int flag = 1;

		for (int i = 0; i <= n - i - 1; ++i)
		{
			if (a[i] > a[i + 1])
			{
				int t = a[i];
				a[i] = a[i + 1];
				a[i + 1] = t;
				flag = 0;
			}
		}

		if (flag == 1)
		{
			break;
		}
	}
}

//选择排序
void select_sort(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		int k = i;
		for (int j = i + 1; j < n; ++j)
		{
			if (a[k] > a[j])
			{
				k = j;
			}
		}

		if (k != i)
		{
			int t = a[k];
			a[k] = a[i];
			a[i] = t;
		}
	}
}

//快速排序
void quick_sort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	int i = left;
	int j = right;
	int temp = a[left];

	while (i < j)
	{
		while (j > i && temp <= a[j])
			--j;
		while (i < j && temp >= a[i])
			++i;

		if (i != j)
		{
			int t = a[i];
			a[i] = a[j];
			a[j] = t;
		}
	}

	a[left] = a[i];
	a[i] = temp;

	quick_sort(a, left, i - 1);
	quick_sort(a, i + 1, right);
}

void swap(int* h, int m, int n)
{
	int t;

	t = h[m];
	h[m] = h[n];
	h[n] = t;
}

//堆排序
void siftdown(int* h, int i, int n)
{
	int flag = 0, t;

	while (2 * i <= n && flag == 0)
	{
		if (h[i] > h[2 * i])
			t = i;
		else
			t = 2 * i;

		if (2 * i + 1 <= n)
			if (h[2 * i + 1] > h[t])
				t = 2 * i + 1;

	    if (t != i)
		{
			swap(h, t, i);
			i = t;//方便继续向下调整
		}
		else
			flag = 1;
	}
}

void creat(int* h, int n)
{
	int i;

	for (i = n / 2; i >= 1; i--)
		siftdown(h, i, n);
}

void heap_sort(int* h, int n)
{
	while (n > 1)//直到n = 1 即只剩下最后一个数字没有操作，此时也没有必要操作了
	{
		swap(h, 1, n);//最大堆的第一个数字最大，把该最大数移到数组的而最后一个数字去
    	n--;
    	siftdown(h, 1, n);//把第一个数字重新更新为最大数
	}
}

//归并排序
void merge(int* a, int low, int mid, int high)
{
    int i = low, j = mid + 1, k = 0;
    int *b = (int* )malloc((high - low + 1) * sizeof(int));

    while (i <= mid && j <= high)
    {
        if (a[i] > a[j])
        {
            b[k] = a[i];
            ++i;
            ++k;
        }
        else
        {
            b[k] = a[j];
            ++j;
            ++k;
        }
    }

    while (i <= mid)
    {
        b[k] = a[i];
        ++i;
        ++k;
    }

    while (j <= high)
    {
        b[k] = a[j];
        ++j;
        ++k;
    }

    for (i = low, k = 0; i <= high; ++i, ++k)//注意这里i的初值是low而不是0
        a[i] = b[k];                         //循环终止条件时i <= high而不是i < high

    free(b);
}

void mergepass(int* a, int length, int n)
{
    int i;

    for (i = 0; i + 2 * length - 1 < n; i = i + 2 * length)
    {
        merge(a, i, i + length - 1, i + 2 * length - 1);
    }

    if (i + length - 1 < n)
        merge(a, i, i + length - 1, n - 1);
}

void merge_sort(int* a, int n)
{
    for (int length = 1; length < n; length = 2 * length)
        mergepass(a, length, n);
}

//产生随机数
int rnd()
{
	return rand() % (1000 - 10 + 1) + 10;
}

void print(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d  ", a[i]);
	}
	printf("\n");
}
int main()
{
	int* a, n;
	while (~scanf("%d", &n)) //输入需要排列的元素个数
	{
		a = (int* )malloc(n * sizeof(int));
		srand((unsigned)time(NULL));
		generate_n(a, n, rnd); //用随机数产生数组个数

		clock_t start, finish; //程序排序开始时间与结束时间

		start = clock(); //记录下排序前的时间
		sort(a, a + n);  //这里测试c++里面自带的sort函数
		finish = clock(); //记录排序结束的时间
		printf("STL SORT time is: %0.8lf\n", double(finish - start)); //差值即为排序需要时间

		random_shuffle(a, a + n); //这里必须随机打乱数组元素

		start = clock();
		insert_sort(a, n);
		finish = clock();
		printf("INSERT SORT time is: %0.8lf\n", double(finish - start));

		random_shuffle(a, a + n);

		start = clock();
		select_sort(a, n);
		finish = clock();
		printf("SELECT SORT time is: %0.8lf\n", double(finish - start));

		random_shuffle(a, a + n);

		start = clock();
		bubble_sort(a, n);
		finish = clock();
		printf("BUBBLE SORT time is: %0.8lf\n", double(finish - start));

		random_shuffle(a, a + n);

		start = clock();
		shell_sort(a, n);
		finish = clock();
		printf("SHELL SORT time is: %0.8lf\n", double(finish - start));

		random_shuffle(a, a + n);

		start = clock();
		quick_sort(a, 0, n - 1);
		finish = clock();
		printf("QUICK SORT time is: %0.8lf\n", double(finish - start));

		random_shuffle(a, a + n);

		start = clock();
		creat(a, n - 1);
		heap_sort(a, n - 1);
		finish = clock();
		printf("HEAP SORT time is: %0.8lf\n", double(finish - start));


		random_shuffle(a, a + n);

		start = clock();
		creat(a, n);
		merge_sort(a, n);
		finish = clock();
		printf("MERGE SORT time is: %0.8lf\n", double(finish - start));


		free(a);
	}

	return 0;
}