算法 | 编程实现各种排序算法，并对比各种算法的效率
【设计要求】:
在给出的代码素材sort.cpp文件中补充main函数中的swtich语句，以及以下排序函数,并比较各种排序方法在对素材文件中的1.data~5.data待排序序列进行排序时所需要的时间。
void shellsort(int data[], int n);//希尔排序
void bubllesort(int data[], int n);//冒泡排序
void quicksort(int data[], int n);//快速排序
void selectsort(int data[], int n);//简单选择排序
void heapsort(int data[], int n);//堆排序
void mergesort(int data[], int n);//合并排序
void radixsort(int data[], int n);//基数排序【代码如下】:
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define RADIX_10 10 //整形排序
#define KEYNUM_31 10
#define SOURCEFILE "4.data"
const int LineLenght = 20;//控制屏幕打印时，每行元素个数
const int MaxSize = 30000;
void Printdata(int data[], int n);//打印数组中个的各个元素
int Getdata(int* data, int& n);
void creatdata(int& n);//产生n个0~1000之间的随机整数，并写入source.data
void insertsort(int data[], int n);//直接插入排序
int Outputdata(int data[], int n);
void shellsort(int data[], int n);//希尔排序
void bubllesort(int data[], int n);//冒泡排序
void quicksort(int data[], int n);//快速排序
void selectsort(int data[], int n);//简单选择排序
void heapsort(int data[], int n);//堆排序
void mergesort(int data[], int n);//合并排序
void radixsort(int data[], int n);//基数排序
int main()
{
int n;
int data[MaxSize];
char SORCEFILE[10];
clock_t start, end;
printf("输入待排序序列所在文件名，例：1.data:");
scanf("%s", &SORCEFILE);
Getdata(data, n); //读取文件的数据存放在data数组中
int menu;
printf("请选择排序方式:\n");
while (1)
{
printf("1. 直接插入排序\n");
printf("2. 希尔插排序\n");
printf("3. 冒泡排序\n");
printf("4. 快速排序\n");
printf("5. 简单选择插入排序\n");
printf("6. 堆排序\n");
printf("7. 归并排序\n");
printf("8. 基数排序\n");
scanf("%d", &menu);
switch (menu)
{
case 1: {
start = clock();
insertsort(data, n);
end = clock();
Printdata(data, n);//输出数据
Outputdata(data, n);
printf("排序时间为%d毫秒", end - start);
printf("您可以尝试一下其它的排序方法:\n");
break;
}
case 2: {
start = clock();
shellsort(data, n);
end = clock();
Printdata(data, n);//输出数据
Outputdata(data, n);
printf("排序时间为%d毫秒", end - start);
printf("您可以尝试一下其它的排序方法:\n");
break;
}
case 3: {
start = clock();
bubllesort(data, n);
end = clock();
Printdata(data, n);//输出数据
Outputdata(data, n);
printf("排序时间为%d毫秒", end - start);
printf("您可以尝试一下其它的排序方法:\n");
break;
}
case 4: {
start = clock();
quicksort(data, n);
end = clock();
Printdata(data, n);//输出数据
Outputdata(data, n);
printf("排序时间为%d毫秒", end - start);
printf("您可以尝试一下其它的排序方法:\n");
break;
}
case 5: {
start = clock();
selectsort(data, n);
end = clock();
Printdata(data, n);//输出数据
Outputdata(data, n);
printf("排序时间为%d毫秒", end - start);
printf("您可以尝试一下其它的排序方法:\n");
break;
}
case 6: {
start = clock();
heapsort(data, n);
end = clock();
Printdata(data, n);//输出数据
Outputdata(data, n);
printf("排序时间为%d毫秒", end - start);
printf("您可以尝试一下其它的排序方法:\n");
break;
}
case 7: {
start = clock();
mergesort(data, n);
end = clock();
Printdata(data, n);//输出数据
Outputdata(data, n);
printf("排序时间为%d毫秒", end - start);
printf("您可以尝试一下其它的排序方法:\n");
break;
}
case 8: {
start = clock();
radixsort(data, n);
end = clock();
Printdata(data, n);//输出数据
Outputdata(data, n);
printf("排序时间为%d毫秒", end - start);
printf("您可以尝试一下其它的排序方法:\n");
break;
}
default: {
printf("没有这种排序方式，请选择正确的排序方法:\n");
}
}
}
return 0;
}
void Printdata(int data[], int n)
{
for (int i = 0; i < n; i++)
{
printf("%4d", data[i]);
if (i % LineLenght == LineLenght - 1)
printf("\n");
}
printf("\n");
return;
}
int Getdata(int data[], int& n)
{
FILE* fp;
if ((fp = fopen(SOURCEFILE, "r")) == NULL) /* 以读方式打开文本文件 */
{
printf("Failure to open score.txt!\n");
return 0;//读数据失败
}
int i = 0;
fscanf(fp, "%6d", &n);//获取文件中的元素个数
while (!feof(fp) && i < n)
{
fscanf(fp, "%4d", &data[i]);
i++;
}
fclose(fp);
return 1; //成功读数据
}
void insertsort(int data[], int n)//直接插入排序
{
int i, j, x;
for (i = 1; i < n; i++)
{
x = data[i];
for (j = i - 1; j >= 0; j--)
{
if (data[j] > x)
data[j + 1] = data[j];
else break;
}
if (j != i) data[j + 1] = x;
}
}
int Outputdata(int data[], int n)
{
FILE* fp;
if ((fp = fopen("out.data", "w")) == NULL) /* 以写方式打开文本文件 */
{
printf("Failure to open score.txt!\n");
return 0;//写数据失败
}
for (int i = 0; i < n; i++)
fprintf(fp, "%4d", data[i]);
fclose(fp);
return 1;
}
void shellsort(int data[], int n)//希尔排序
{
int a = n;
do
{
a = a / 3 + 1;
insertsort(data, a);
} while (a > 1);
}
void bubllesort(int data[], int n)//冒泡排序
{
bool kk = true;//优化
for (int a = 0; a < n - 1 && kk; a++)
{
kk = false;
for (int b = a + 1; b < n; b++)//从前往后扫描
{
if (data[a] > data[b])//从小到大排序
{
int temp = data[b];//交换
data[b] = data[a];
data[a] = temp;
kk = true;
}
}
}
}
void Qsort(int a[], int left, int right)
{
int i, j, t, temp;
if (left > right)//结束的条件
return;
temp = a[left]; //temp中存的就是基准数
i = left;
j = right;
while (i != j)
{
while (a[j] >= temp && i < j)//先从右边开始找
j--;
while (a[i] <= temp && i < j)//再找左边的
i++;
if (i < j)//交换两个数在数组中的位置 比基准大的，和比基准小的互换位置
{
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
a[left] = a[i];
a[i] = temp;
Qsort(a, left, i - 1);//继续处理左边的，递归
Qsort(a, i + 1, right);//继续处理右边的 ，递归
}
void quicksort(int data[], int n)///快排
{
Qsort(data, 1, n);
}
void selectsort(int data[], int n)//简单选择排序
{
int a, b;
for (b = 1; b < n; b++)
{
int min = b;
for (a = b + 1; a < n; a++)//找最小值
{
if (data[a] < data[min])
{
min = a;
}
}
if (b != min)
{
int temp = data[b];
data[b] = data[min];
data[min] = temp;
}
}
}
void heapsort(int data[], int n)//堆排序
{
for (int i = n / 2; i >= 0; i--)//建初堆
{
int t = data[i];
int x = data[i];
int m = i;
int j = 2 * m;
bool finished = false;
while (j <= n && !finished)
{
if (j + 1 <= n && data[j] < data[j + 1])
{
j = j + 1;
}
if (x >= data[j])
{
finished = true;
}
else {
data[m] = data[j];
m = j;
j = 2 * m;
}
}
data[m] = t;
}
for (int i = n - 1; i >= 1; i--)
{
int b = data[0];
data[0] = data[i];
data[i] = b;
int t = data[0];//重建堆
int x = data[0];
int m = 0;
int j = 2 * m;
bool finished = false;
while (j <= i - 1 && !finished)
{
if (j + 1 <= i - 1 && data[j] < data[j + 1])
{
j = j + 1;
}
if (x >= data[j])
{
finished = true;
}
else {
data[m] = data[j];
m = j;
j = 2 * m;
}
}
data[m] = t;
}
}
void Merge(int r1[], int low, int mid, int high, int r2[]) {
int i = low; int j = mid + 1; int k = low;
while ((i <= mid) && (j <= high))
{
if (r1[i] <= r1[j]) { r2[k] = r1[i]; i++; }
else { r2[k] = r1[j]; j++; }
k++;
}
while (i <= mid)
{
r2[k] = r1[i];
k++;
i++;
}
while (j <= high)
{
r2[k] = r1[j];
k++;
j++;
}
}
void Msort(int r1[], int low, int high, int r3[])//合并排序
{
int* r2;
r2 = (int*)malloc((high + 1) * sizeof(int));
if (low == high)
{
r3[low] = r1[low];
}
else
{
int mid = (low + high) / 2;
Msort(r1, low, mid, r2);
Msort(r1, mid + 1, high, r2);
Merge(r2, low, mid, high, r3);
}
free(r2);
}
void mergesort(int data[], int n)//合并排序
{
Msort(data, 0, n - 1, data);/*把函数的实现代码粘贴在此处*/
}
int GetNumInPos(int num, int pos)
{
int temp = 1;
for (int i = 0; i < pos - 1; i++)
temp *= 10;
return (num / temp) % 10;
}
void radixsort(int data[], int n)//基数排序
{
int* radixArrays[RADIX_10]; //分别为0~9的序列空间
for (int i = 0; i < 10; i++)
{
radixArrays[i] = (int*)malloc(sizeof(int) * (n + 1));
radixArrays[i][0] = 0; //index为0处记录这组数据的个数
}
for (int pos = 1; pos <= KEYNUM_31; pos++) //从个位开始到31位
{
for (int i = 0; i < n; i++) //分配过程
{
int num = GetNumInPos(data[i], pos);
int index = ++radixArrays[num][0];
radixArrays[num][index] = data[i];
}
for (int i = 0, j = 0; i < RADIX_10; i++) //收集
{
for (int k = 1; k <= radixArrays[i][0]; k++)
data[j++] = radixArrays[i][k];
radixArrays[i][0] = 0; //复位
}
}
}【算法效率】: