一、实验目的
- 掌握各种常用排序的算法思想；
- 掌握各种常用排序的算法实现；
- 掌握各种常用排序时间复杂度，比较各种排序的优缺点。
二、实验相关知识
- 复习C语言文件读写的相关知识
- 复习课本中第9章关于内部排序的相关知识点；
三、实验内容与要求
1.编程实现各种排序算法，并对比各种算法的效率。
【设计要求】在给出的代码素材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) ;//基数排序
四、程序代码及运行结果
【程序代码】
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");
}
}
void shellsort(int data[],int n)//希尔排序
{
int i, j, x;
do
{
n = n / 3 + 1;
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;
}
} 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 quicksort(int data[],int n)//快速排序
{
Qsort(data, 1, n);
}
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 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 mergesort(int data[],int n)//合并排序
{
Msort(data, 0, n - 1, data);
}
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 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; //复位
}
}
}【运行结果】
【算法时间复杂度分析】
填写各个排序算法在读文件1~5的数据进行排序时，需要的时间，单位：毫秒。
| 直接插入 | 希尔 | 冒泡 | 快速 | 简单选择 | 堆 | 归并 | 基数 | |
| 1.data | 143 | 16 | 179 | 128 | 151 | 1 | 33 | 7 |
| 2.data | 74 | 8 | 182 | 115 | 134 | 2 | 40 | 6 |
| 3.data | 71 | 9 | 186 | 117 | 142 | 2 | 36 | 8 |
| 4.data | 1 | 0 | 0 | 114 | 135 | 1 | 41 | 6 |
| 5.data | 285 | 31 | 648 | 462 | 608 | 3 | 139 | 15 |
五、实验心得体会
巩固了文件读写及排序算法的知识。
