#include<stdio.h>
#include <time.h>
#include<stdlib.h>
#define N 10000
double T, T1, T2, T3, T4, T5, T6;
int M;
clock_t start, stop; //clock_t是clock（）函数返回的变量类型
double duration;//时间
void Bubblesort(int arr[], int size)//冒泡排序
{
int i = 0, j = 0;
for (i = 0; i < size; i++) {
int h = 0;
for (j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
h = 1;
}
}
if (h = 0)
{
break;
}
}
}
//快速排序
void Quicksort(int arr[], int left, int right)
{
if (left >= right) {
return;
}
int key = arr[left];
int begin = left;
int end = right;
while (begin != end) {
while (begin < end && arr[end] >= key) {
end--;
}
if (end > begin) {
arr[begin] = arr[end];
}
while (begin < end && arr[begin] <= key) {
begin++;
}
if (begin < end) {
arr[end] = arr[begin];
}
}
arr[begin] = key;
Quicksort(arr, left, begin - 1);
Quicksort(arr, begin + 1, right);
}
//堆排序
void swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void adjust_down(int arr[], int root, int size)
{
int parent = root;
int left = root * 2 + 1;
int right = left + 1;
while (left < size) {
int max = left;
if (right<size && arr[right]>arr[max]) {
max = right;
}
if (arr[max] > arr[parent]) {
swap(&arr[max], &arr[parent]);
parent = max;
left = parent * 2 + 1;
right = left + 1;
}
else {
break;
}
}
}
//建堆
void heap_sort(int arr[], int size)
{
int begin = 0;
for (begin = size / 2 - 1; begin >= 0; --begin) {
adjust_down(arr, begin, size);
}
int end = size - 1;
while (end > 0) {
swap(&arr[0], &arr[end]);
adjust_down(arr, 0, end);
--end;
}
}
//选择排序
void selectSort(int arr[], int size)
{
int i = 0, j = 0;
int k = 0;
for (i = 0; i < size; i++) {
k = i;
for (j = i + 1; j < size; j++) {
if (arr[k] > arr[j]) {
k = j;
}
}
if (k != i) {
int tmp = arr[k];
arr[k] = arr[i];
arr[i] = tmp;
}
}
}
//希尔排序
void ShellSort(int arr[], int length) {
int increasement = length;
int i, j, k;
do {
//确定分组的增量
increasement = increasement / 3 + 1;
for (i = 0; i < increasement; i++) {
for (j = i + increasement; j < length; j += increasement) {
if (arr[j] < arr[j - increasement]) {
int temp = arr[j];
for (k = j - increasement; k >= 0 && temp < arr[k]; k -= increasement) {
arr[k + increasement] = arr[k];
}
arr[k + increasement] = temp;
}
}
}
} while (increasement > 1);
}
//插入排序
void InsertSort(int arr[], int size)
{
int i = 0, j = 0;
int tmp = 0;
for (i = 1; i < size; i++) {
tmp = arr[i];
j = i;
while (j > 0 && arr[j - 1] > tmp) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = tmp;
}
}
//归并排序
void merge(int* src, int* dst, int begin, int mid, int end)
{
int begin1 = begin;
int begin2 = mid;
int index = begin;
while (begin1 < mid && begin2 < end) {
if (src[begin1] < src[begin2]) {
dst[index++] = src[begin1++];
}
else {
dst[index++] = src[begin2++];
}
}
while (begin1 < mid) {
dst[index++] = src[begin1++];
}
while (begin2 < end) {
dst[index++] = src[begin2++];
}
memcpy(src + begin, dst + begin, (end - begin) * sizeof(int));
}
void _merge_sort(int* arr, int* tmp, int left, int right)
{
if (left + 1 >= right) {
return;
}
int mid = left + (right - left) / 2;
_merge_sort(arr, tmp, left, mid);
_merge_sort(arr, tmp, mid, right);
merge(arr, tmp, left, mid, right);
}
void merge_sort(int* arr, int size)
{
int* tmp = (int*)malloc(size * sizeof(int));
_merge_sort(arr, tmp, 0, size);
free(tmp);
}
int a[666666] = { 0 }; // 排序的数组
int a_cp[666666] = { 0 };//排序数组副本
void a_copy(int M) {
for (int i = 0; i < M; i++) //赋值排序数组
a_cp[i] = a[i];
}
void main()
{
printf("排序算法比较，输入序号查看，输入0退出\n");
printf("1 冒泡排序 2 快速排序\n");
printf("3 堆排序 4 选择排序\n");
printf("5 希尔排序 6 归并排序\n");
printf("7 插入排序\n");
printf("请输入想要排序的数组个数：");
scanf_s("%d", &M);
srand((int)time(0));
for (int i = 0; i < M; i++)
{
a[i] = rand() % M;
printf("%5d", a[i]);
if ((i + 1) % 20 == 0)
printf("\n");
}
while (1) {
srand((unsigned int)time(0));
int i, n;
printf("请输入你的选择：");
scanf_s("%d", &n);
printf("\n");
switch (n) {
case 1:
a_copy(M);//冒泡排序
start = clock();
Bubblesort(a, M);
stop = clock();
T1 = (float)(stop - start) / CLOCKS_PER_SEC;//CLOCKS_PER_SEC是一个常数，表示机器时钟每秒所走的时钟打点数
printf("冒泡排序用的时间：%lf秒\n", T1);
for (i = 0; i < M; i++) {
printf("%5d", a[i]);
if ((i + 1) % 20 == 0)
printf("\n");
}printf("\n");
printf("\n");
system("pause");
break;
case 2:
a_copy(M);//快速排序
start = clock();
Quicksort(a, 0, M);
stop = clock();
T = (float)(stop - start) / CLOCKS_PER_SEC;
printf("快速排序用的时间：%lf秒\n", T);
for (i = 0; i < M; i++) {
printf("%5d", a[i]);
if ((i+1 )% 20 == 0)
printf("\n");
}printf("\n");
printf("\n");
system("pause");//暂停
break;
case 3:
a_copy(M);//堆排序
start = clock();
heap_sort(a, M);
stop = clock();
T2 = (float)(stop - start) / CLOCKS_PER_SEC;
printf(" 堆排序用的时间：%lf秒\n", T2);
for (i = 0; i < M; i++) {
printf("%5d", a[i]);
if ((i + 1) % 20 == 0)
printf("\n");
}printf("\n");
printf("\n");
system("pause");
break;
case 4:
a_copy(M);
start = clock();//选择排序
selectSort(a, M);
stop = clock();
T3 = (float)(stop - start) / CLOCKS_PER_SEC;
printf("选择排序用的时间：%lf秒\n", T3);
for (i = 0; i < M; i++) {
printf("%5d", a[i]);
if ((i + 1) % 20 == 0)
printf("\n");
}
printf("\n");
printf("\n");
system("pause");
break;
case 5:
a_copy(M);
start = clock();//希尔排序
ShellSort(a, M);
stop = clock();
T4 = (float)(stop - start) / CLOCKS_PER_SEC;
printf("希尔排序用的时间：%lf秒\n", T4);
for (i = 0; i < M; i++) {
printf("%5d", a[i]);
if ((i + 1) % 20 == 0)
printf("\n");
}printf("\n");
printf("\n");
system("pause");
break;
case 6:
a_copy(M);
start = clock();//归并排序
merge_sort(a, M);
stop = clock();
T6 = (float)(stop - start) / CLOCKS_PER_SEC;
printf("归并排序用时：%lf秒\n", T6);
for (i = 0; i < M; i++) {
printf("%5d", a[i]);
if ((i + 1) % 20 == 0)
printf("\n");
} printf("\n");
system("pause");
break;
case 7:
a_copy(M);
start = clock();//插入排序
InsertSort(a, M);
stop = clock();
T5 = (float)(stop - start) / CLOCKS_PER_SEC;
printf("插入排序用的时间：%lf秒\n", T5);
for (i = 0; i < M; i++) {
printf("%5d", a[i]);
if ((i + 1) % 20 == 0)
printf("\n");
}printf("\n\n");
printf("\n");
system("pause");
break;
case 0:
exit(0);
break;
default:
printf("输入命令错误，请重新输入！！！");
break;
}
}
}
排序算法的实现。用C语言编程实现冒泡排序 选择排序 插入排序 shell排序 快速排序 堆排序算法 归并排序。利用随机函数产生N个随机整数（10000以上）。
