【深圳大学算法设计与分析】实验一 算法性能分析（十大排序算法）
综合上述实验可得，当数据规模相当大时，选择排序、冒泡排序、插入排序耗费的时间相当多，该类算法虽然简单易懂，但是效率较低，不适合处理大量数据。合并排序和快速排序采用了分治、递归的思想，运行大量数据时效率仍然非常高，远胜于前面的几种排序算法。因此，当数据规模较大时，选择后面两种排序算法为佳。
实验目的
1.掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理。
2.掌握不同排序算法时间效率的经验分析方法，验证理论分析与经验分析的一致性。
实验内容与结果
实现选择排序、冒泡排序、合并排序、快速排序、插入排序算法；
（1）选择排序
原理：从未排序的数据元素中选出最小的一个元素，放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小元素，继续放在起始位置，直到未排序元素个数为0。
算法分析：整个算法是双重循环：
外循环控制排序的趟数，对n个记录进行排序的趟数为n-1趟；
内循环控制每一趟的排序，进行第i趟排序时，所需的比较次数总是n-i次，关键字比较次数KCN 与记录的初始排列无关。
总的关键字比较次数为
记录移动次数RMN与初始排列有关，最好的情况是，排列已经有序，则RMN=0；最坏情况是，每一趟都要进行交换，总的记录移动次数为 RMN = 3(n-1)。
时间复杂度是O(n2)，空间复杂度是O(1）。
选择排序是一种不稳定的排序方法。
（2）冒泡排序
原理：对于n个待排序记录，从第1个记录起，依次比较相邻两个记录的关键字，如果发生逆序，则交换之，直至第n-1个记录和第n个记录比较完，循环n-1次即可排列有序。
算法分析：
最好情况：在记录的初始序列正序时，只执行一趟起泡排序,做n-1次关键字比较，但是不移动记录。
最坏情况：记录的初始序列逆序时，要执行n-1趟冒泡，第i趟做n-i次关键字比较，执行n-i次记录交换，比较次数KCN和交换次数RCN为：
冒泡排序的时间复杂度为O(n2)。
冒泡排序是一种稳定的排序方法。
（3）合并排序
原理：归并是指将两个或两个以上的有序序列合并成一个有序序列。
2-路归并排序：
- 初始时，将每个记录看成一个单独的有序序列，则n个待排序记录就是n个长度为1的有序子序列；
- 将前后相邻的两个有序序列归并为一个有序序列(两两归并)，得到(int)(n/2)个长度为2或1的有序子序列——一趟归并；
- 重复做两两归并操作，直到得到长度为n的有序序列为止。
其核心是如何将相邻的两个子序列归并成一个子序列。
算法分析：
（1）假设待归并的两个有序表长度分别为m和n，若是顺序存储，则归并后，都会利用一个长度为m+n的数组作为辅助数组用于保存合并序列，则空间复杂度为O（m+n）
（2）归并操作至多只需要m+n次移位和m+n次比较，因此归并的时间复杂度为O(m+n)
（3）如果待排序的记录为n个，则需要做(int)(log2n)趟2－路归并排序，每趟2－路归并排序的时间复杂度为O(n),因此2－路归并排序的时间复杂度为O(nlog n)。
（4）需要额外空间，大小与待排序记录空间相同，则空间复杂度为O(n)。
（5）归并排序是一种稳定的排序方法。
（4）快速排序
原理：任取待排序记录序列中的某个记录作为枢轴(也称为基准、锚点或支点记录，pivot), 通过一趟排序，将待排序记录以枢轴为界分割成两部分，其中，比枢轴关键字小的记录都在枢轴的前面，而枢轴后面的记录都比枢轴关键字大。然后，采用同样方法再分别对这两部分子序列进行排序，最后达到整个序列有序。
算法分析：时间复杂度是O(nlog n)，空间复杂度是：S(n)=O(㏒n)。
快速排序是一种不稳定的排序方法。
（5）插入排序
原理：将待排序的记录依次插入到已排好序的序列中，得到一个新的、记录数增加1的有序表。 直到所有的记录都插入完为止。
算法分析：
关键字比较次数和记录移动次数与记录的初始排列有关。
时间复杂度为O(n2)，空间复杂度为O(1)。
最大的优点是简单，在记录数较少时，是比较好的办法。
插入排序是一种稳定的排序方法。
当n=10000时
当n=20000时
当n=30000时
当n=40000时
当n=50000时
表格如下
图像如下
在大数据量进行排序时，冒泡排序需要耗费大量时间，选择排序和插入排序所耗费时间略少，合并排序和快速排序耗费时间最少。
（6）选择排序
在大数据量排序情况下，理论值大于实际值不少，原因是基准值n=10000时平均运行时间较长。
（7）冒泡排序
在大数据量排序情况下，理论值和实际值较为相似；理论值略小于实际值的原因是基准值n=10000时平均运行时间较少。
（8）合并排序
在大数据量排序情况下，理论值和实际值较为接近。
（9）快速排序
在大数据量排序情况下，理论值和实际值较为相似，且快速排序的平均运行时间少，效率高。
（10）插入排序
在大数据量排序情况下，理论值和实际值几乎一致。
从10亿数据中快速挑选出最大的10个数。
算法思想：将十亿分块，每个块为十万，用选择排序将每个块最大的十个数进入队列，最后再统一取出找出最大的十个数即为最终所求。
最终结果
实验总结
综合上述实验可得，当数据规模相当大时，选择排序、冒泡排序、插入排序耗费的时间相当多，该类算法虽然简单易懂，但是效率较低，不适合处理大量数据。合并排序和快速排序采用了分治、递归的思想，运行大量数据时效率仍然非常高，远胜于前面的几种排序算法。因此，当数据规模较大时，选择后面两种排序算法为佳。
实验代码
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<queue>
using namespace std;
int n; //数据总数
int* zu;
queue<int> q;
int select()//选择排序
{
int qi, zhi; //记录起止时间
qi = clock();
//
for (int i = 0; i < n; i++)
{
int min = 99999,minpos;
for (int j = i; j < n; j++)
if (zu[j] < min)//找到最小值放到前面
{
min = zu[j];
minpos = j;
}
if (i != minpos)
swap(zu[i], zu[minpos]);//交换
}
//
zhi = clock();
return zhi - qi; //返回时间差
}
int bubble()//冒泡排序
{
int qi, zhi; //记录起止时间
qi = clock();
//
int i, j;
for (i = 0; i < n - 1; i++)
for (j = 0; j < n-i-1; j++)
if (zu[j] > zu[j + 1])
swap(zu[j], zu[j + 1]);
//
zhi = clock();
return zhi - qi; //返回时间差
}
void merge(int* a, int l, int mid, int r)//合并两序列
{
int* b = new int[r - l + 1];
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r)
{
if (a[i] <= a[j])
b[k++] = a[i++];
else
b[k++] = a[j++];
}
while (i <= mid)
b[k++] = a[i++];
while (j <= r)
b[k++] = a[j++];
for (i = l,k=0; i <= r; i++)//将排序好的序列传回去
a[i] = b[k++];
}
void mergesort(int *a,int l,int r)//递归进行归并排序
{
if (l < r)
{
int mid = (l + r) / 2;
mergesort(a, l, mid);
mergesort(a, mid + 1, r);
merge(a, l, mid, r);
}
}
int guibing()//归并排序
{
int qi, zhi; //记录起止时间
qi = clock();
//
mergesort(zu, 0, n - 1);
//
zhi = clock();
return zhi - qi; //返回时间差
}
int part(int l,int r)//划分子表并返回轴的位置
{
int zhou = zu[l];//保存轴的值
while (l < r)
{
while (l < r && zhou <= zu[r])//注意'='不能漏掉
r--;
zu[l] = zu[r];
while (l < r && zhou >= zu[l])
l++;
zu[r] = zu[l];
}// 循环结束的条件是l==r
zu[l] = zhou;//将轴的值放入l==r的位置
return l; //返回轴的位置
}
void qsort(int l, int r)
{
int zhoupos;
if (l < r)
{
zhoupos = part(l, r);
qsort(l, zhoupos - 1);
qsort(zhoupos + 1, r);
}
}
int quick()//快速排序
{
int qi, zhi; //记录起止时间
qi = clock();
//
qsort(0, n - 1);
//
zhi = clock();
return zhi - qi; //返回时间差
}
int insert()//插入排序
{
int qi, zhi; //记录起止时间
qi = clock();
//
int i, j;
for (i = 1; i < n; i++)//第一个数据不用插入
{
int temp = zu[i];
for (j = i; j > 0; j--)
{
if (temp < zu[j - 1])
zu[j] = zu[j - 1];
else
break;
}
zu[j] = temp;
}
//
zhi = clock();
return zhi - qi; //返回时间差
}
void show()//输出函数
{
for (int i = 0; i < n; i++)
{
cout << zu[i] << " ";
}
cout << endl;
}
void ceshi(int ci, int size)//测试次数和排序数组大小
{
n = size;
zu=new int[size];//动态建立数组
srand(time(0));
int t1,t2,t3,t4,t5, i, j;
t1 = t2 = t3 = t4 = t5 = 0;
/*
for (i = 0; i < ci; i++)
{
for (j = 0; j < size; j++)
zu[j] = rand();
//show();//1
t1+= select();
t2 += bubble();
t3 += guibing(); 不能放一起，要分开！！！！！
t4 += quick();
t5 += insert();
//show(); cout << endl;//2 语句1和2用来测试排序算法是否正确，此时n要取小值
}
*/
for (i = 0; i < ci; i++)
{
for (j = 0; j < size; j++)
zu[j] = rand();
t1 += select();
}
for (i = 0; i < ci; i++)
{
for (j = 0; j < size; j++)
zu[j] = rand();
t2 += bubble();
}
for (i = 0; i < ci; i++)
{
for (j = 0; j < size; j++)
zu[j] = rand();
t3 += guibing();
}
for (i = 0; i < ci; i++)
{
for (j = 0; j < size; j++)
zu[j] = rand();
t4 += quick();
}
for (i = 0; i < ci; i++)
{
for (j = 0; j < size; j++)
zu[j] = rand();
t5 += insert();
}
cout << "选择排序的平均运行时间为" << t1 / ci << "ms" << endl;
cout << "冒泡排序的平均运行时间为" << t2 / ci << "ms" << endl;
cout << "合并排序的平均运行时间为" << t3 / ci << "ms" << endl;
cout << "快速排序的平均运行时间为" << t4 / ci << "ms" << endl;
cout << "插入排序的平均运行时间为" << t5 / ci << "ms" << endl;
}
void selectshiyi()//选择排序从10亿中找最大的10个
{
int i,j,k,l;
srand(time(0));
zu = new int[100000];
k = 0;
n = 100000;
for (i = 0; i < 1000000000; i++)//将十亿分块，每个块为十万，将每个块最大的十个数进入队列，最后再统一取出找出最大的十个数
{
zu[k++] = rand();
if (k == 99999) //每次数组存满十万则进行操作
{
for (l = 0; l < 10; l++)
{
int max = -1, maxpos;
for (j = 0; j < n; j++)
if (zu[j] > max)//找到最大值
{
max = zu[j];
maxpos = j;
}
q.push(zu[maxpos]);//进入队列
zu[maxpos] = 0;
}
k = 0;
}
}
n = 10000;
for (i = 0; i < n; i++)//取出队列中的值
{
zu[i] = q.front();
q.pop();
}
for (l = 0; l < 10; l++)//将最大的十个数存入队列
{
int max = -1, maxpos;
for (j = 0; j < n; j++)
if (zu[j] > max)
{
max = zu[j];
maxpos = j;
}
q.push(zu[maxpos]);
zu[maxpos] = 0;
}
for (i = 0; i < 10; i++)//输出
{
cout << q.front() << " ";
q.pop();
}
cout << endl;
}
int main()
{
/*
for (int i = 1; i <= 5; i++)
{
cout << endl << endl;
int size = i*10000; //设置数组大小
cout << "排序数组大小n=" << size << endl;
ceshi(20, size); //测试20次
}
*/
selectshiyi();
}
（by 归忆）
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
25
0- 0
已为社区贡献8条内容
所有评论(0)