赞
踩
1编程实现曾经学过的所有排序算法,并对程序进行测试,列举多个测试用例,检查程序是否输出正确结果。
2、对比在待排序数据量不断增大的情况下,各个排序算法的运行时间变化情况,思考哪些算法的运行时间增长速度快,哪些算法的运行时间增长速度慢,哪个算法效率高?
3、记录测试数据量分别是10、100、1000、10000、10,0000、100,0000、1000,0000的运行时间。思考效率高的算法就一定在任何数据量下的效率都高吗?
4、分析每个算法的运行时间,用θ符号表示出算法的时间复杂度。
实验需求:
排序算法代码,存放至少100,0000个数据的随机数组,测试程序运行时间的clock()函数。
实验环境: 软件codeblocks 17.12
一、srand() and rand()函数
用srand(time(0))来设置种子 rand()函数产生随机数
srand是种下随机种子数,你每回种下的种子不一样,用rand得到的随机数就不一样。为了每回种下一个不一样的种子,所以就选用Time(0),Time(0)是得到当前时时间值
srand() 和rand() 共同使用能产生伪随机序列,如果想要产生相同的随机序列,把srand参数改成一个固定的数即可。
int arr[N];
//随机播种
srand(1);
for(int i=0; i<N; i++)
{
arr[i]=rand()%MAX;//我们在比较各种排序的算法,因此种子必须一样(控制变量)
printf("%d ",arr[i]);
}
二、测试clock函数
clock_t start_time=clock();
{
bubbleSort(arr,N);
}
clock_t end_time=clock();
printf("Running time is: %fms\n",double(end_time-start_time));
时间函数测试完成
三,测试判断排序结果的函数
printf("\n排序的结果为:%s",isSorted(arr,N)==true?"true":"false");
使用判断函数的好处是数据量过大时,无法人为判断程序是否正确排序,排序准确是测试排序运行时间的前提。
四、回归题目
N的值控制数据量的大小,MAX控制数据的范围
五、测试排序算法, 记录测试数据量分别是100、1000、10000、10,0000、100,0000、1000,0000的运行时间。思考效率高的算法就一定在任何数据量下的效率都高吗?
对程序进行测试,列举多个测试用例,检查程序是否输出正确结果.
四、试排序算法, 记录测试数据量分别是100、1000、10000、10,0000、100,0000、1000,0000的运行时间。思考效率高的算法就一定在任何数据量下的效率都高吗?
冒泡排序
总结:用冒泡排序排100000的数据会很久 时间呈O(n2)递增 空间复杂度为O(1),冒泡是一种稳定的排序算法,冒泡可以在第二个for循环里面做一个优化,不过还是很慢。
选择排序
总结:可见选择排序是比冒泡排序要快一点 但时间复杂度仍然是O(n2) ,空间复杂度为O(1) 选择排序是不稳定的排序算法。而且数据的次序不会影响函数的时间复杂度。
插入排序
总结:插入排序比选择和冒泡排序都要快
时间复杂度还是在O(n^2)
空间复杂度为O(1)
快速排序
总结:排序10,0000个数据的时候时间级别大大减少,但排序100,0000的数据的时候,直接停止工作。
最好情况:时间复杂度:O(nlog2n)
最坏情况:时间复杂度:O(n^2)
快速排序算法的时间复杂度平均为O(nlog2n)
快速排序是一个不稳定的算法,但是在数据相对较小的时候,他是折合时间复杂度和空间复杂度最优的算法。
归并排序
时间复杂度为:O(nlog2n)
可知归并排序比快排,堆排序都快,并且稳定。但是他需要开辟一个很大的辅助空间。
堆排序
时间复杂度为:O(nlog2n)
一百万个数据排序起来,堆排序比快速排序要快,可见数据量要大的时候堆排序比快排优。
接下来终于到线性级别的排序方式了~
基数排序(桶排序)
基数排序是对数据有要求的,必须是整数,对于一些资金含(小数的排序就用不了),基数排序的原理是,先取键值,比如排序单纯排自然数的时候,直接取键值为0~9,然后对数据进行从个位再到十位一直往下进行排序。每排一次放在桶子里边(相当于一个队列),最后把桶子里面的数据串联起来即可。
10000个数据排序时间为几乎为0!!
桶排序 :时间复杂度为O(n) 空间复杂度为O(n)
排一千万数据需要时间是1000ms以内。但是桶排序的缺点就是需要开辟一个很大的辅助空间,不过这个已经是相比于其他算法,既折中排序速度有很快的排序算法了。
计数排序
计数排序最大的特点就是数组的元素与下标一致,省略了排序的时间。
算法的步骤如下:
1.找出待排序的数组中最大和最小的元素
2.统计数组中每个值为i的元素出现的次数,存入数组的第i项
3.对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加)4.反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1
总结:时间复杂度O(n) 空间复杂度O(n)
可见,计数排序的算法排序整数是最快的!虽然计数排序看上去很强大,但是它存在两大局限性:
1.当数列最大最小值差距过大时,并不适用于计数排序
比如给定20个随机整数,范围在0到1亿之间,此时如果使用计数排序的话,就需要创建长度为1亿的数组,不但严重浪费了空间,而且时间复杂度也随之升高。
2.当数列元素不是整数时,并不适用于计数排序
如果数列中的元素都是小数,比如3.1415,或是0.00000001这样子,则无法创建对应的统计数组,这样显然无法进行计数排序。
正是由于这两大局限性,才使得计数排序不像快速排序、归并排序那样被人们广泛适用。
实验总结:综上所述,我们可以体会各种排序算法的应用场景,不是为了学习而学,要真正弄懂,才能够体会编程思想,进而享受编程的乐趣,最后,附上全部代码供大家参考:
#include <iostream> #include <time.h> #include <cstdio> #include <cstdlib> #define N 10000 //数据量的大小 #define MAX 100 //数据的范围1-100 using namespace std; //-----------冒泡排序 void bubbleSort(int arr[],int n) { int temp; for(int i=0; i<=n-1; i++) { for(int j=i+1; j<=n-1; j++) { if(arr[i]>arr[j]) { temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; } } } } //------------选择排序: void chioseSort(int arr[],int n) { int temp,index; for(int i=0; i < n-1; ++i) { index = i; for(int j=i+1; j<n; ++j) { if(arr[j]<arr[index]) index = j; } if(index!=i) { temp = arr[i]; arr[i] = arr[index]; arr[index] = temp; } } } //------------直接插入排序: void insertSort(int arr[], int len) { int i, j, key; for(i = 1; i < len; ++i){ key = arr[i]; for(j = i-1; j >=0; --j){ if(arr[j] > key) arr[j+1] = arr[j]; else break; } arr[j+1] = key; } } //------------快速排序: int partition(int arr[], int low, int high) { int key=arr[low]; while(low<high) { while(low<high&&arr[high]>=key) high--; arr[low]=arr[high]; while(low<high&&arr[low]<=key) low++; arr[high]=arr[low]; } arr[low]=key; //返回枢轴所在的位置 且 low and high 值是一样的 return low; } void Qsort(int arr[],int low,int high) { int key; if(low<high) { key=partition(arr,low,high); Qsort(arr,low,key-1); Qsort(arr,key+1,high); } } //------------归并排序 //辅助数组 int temp[N]; void combineArr(int arrL[],int ln,int arrR[],int rn) { int i=0,j=0; int k=0; while(i<ln&&j<rn) { if(arrL[i]<=arrR[j]) { temp[k++]=arrL[i++]; } else { temp[k++]=arrR[j++]; } } while(i<ln) { temp[k++]=arrL[i++]; } while(j<rn) { temp[k++]=arrR[j++]; } for(int i=0; i<k; i++) { arrL[i]=temp[i]; } } void conflationSort(int arr[],int l,int r) { if(r>l) { int mid= (l+r)/2; conflationSort(arr,l,mid); conflationSort(arr,mid+1,r); combineArr(&arr[l],mid-l+1,&arr[mid+1],r-mid); } } //------------堆排序 void swap(int *a,int *b){ int temp = *a; *a = *b; *b = temp; } //调整堆 void adjustHeap(int arr[],int index,int lenght) { int l = index*2+1; int n = lenght; int temp = arr[index]; while(l<n){ if((l+1)<n&&arr[l+1]>arr[l]) l++; if(arr[l] <= temp) break; arr[index] = arr[l]; index = l; l = index*2+1; } arr[index] = temp; } //新建堆 void buildHeap(int arr[],int n) { for(int i = n/2 -1;i>=0;--i) { adjustHeap(arr,i,n); } } void heapSort(int arr[],int n) { buildHeap(arr,n); for(int i = n-1;i>0;--i) { swap(&arr[0],&arr[i]); adjustHeap(arr,0,i); } } //------------基数排序 //辅助数组 int temps[10][N]; //获取最大位数的位置 如8->1 , 17->2,7832->4 int getMexExp(int arr[],int n){ int maxN = arr[0]; for(int i=1;i<n;++i){ //把所有的数据都遍历一遍 然后找最大值 确定数据的位数 时间为N maxN = arr[i]>maxN?arr[i]:maxN; } int exps = 1; maxN = maxN/10; while(maxN!=0){ maxN = maxN/10; exps++; } return exps; //返回一个最大值的位数 } //基数排序 void radixSort(int arr[],int n) { //存每个桶中数的个数 int countIndex[10] = {0}; //相当于10桶子 int exps = getMexExp(arr,n); //把位数传给exps int exp = 1; for(int e=0;e<exps;++e){ //入桶 for(int i=0;i<n;++i){ //把数据遍历一遍 获取从个位 十位 一直往下 int index = (arr[i]/exp)%10; temps[index][countIndex[index]++] = arr[i]; //存放到队列里的过程 } //取值,改变数组 int k=0; for(int i=0;i<10;++i){ //排序数字0~9 //如果桶中数的个数大于0 if(countIndex[i]>0){ int n = countIndex[i]; //将数取出,改变数组 for(int j =0;j<n;++j){ arr[k++] = temps[i][j]; //按照各个位数排好 给原来的数组 } } } //将桶中的数的个数重置为0 for(int i=0;i<10;++i) countIndex[i] = 0; //位数改变 exp *=10; } } //------------------计数排序 //创建辅助数组 //int temp[N]; void CountSort(int arr[], int n) { int i; int minValue = arr[0]; int maxValue = arr[0]; int range = 0; int count = 0; for (i = 0; i < n; i++)//计算数据的分散空间 { if (arr[i] < minValue){ minValue = arr[i]; //找最大值和最小值 } if (arr[i] > maxValue){ maxValue = arr[i]; } } range = maxValue - minValue + 1; //存放的空间大小为最大值与最小值之差 for (i = 0; i < n; i++)//统计每个元素出现的次数 { temp[arr[i] - minValue]++; } for(i=0;i<range;i++)//通过统计temp[];回收元素 { while (temp[i]--) { arr[count++] = i + minValue; } } } //以上排序结果均测试完毕,结果为true。 bool isSorted(int arr[],int n) { for(int i=0; i<n-1; i++) { //从小到大排序 if(arr[i]>arr[i+1]) { return false; } } return true; } int main() { //int arr[10]={3,2,5,2,3,4,6,7,2,10}; int arr[N]; //随机播种 srand(1); for(int i=0; i<N; i++) { arr[i]=rand()%MAX; // printf("%d ",arr[i]); } printf("\n"); clock_t start_time=clock(); { // bubbleSort(arr,N); // chioseSort(arr,N); //insertSort(arr,N); //heapSort(arr,N); CountSort(arr,N); // radixSort(arr,N); // conflationSort(arr,0,N-1); // Qsort(arr,0,N-1); } clock_t end_time=clock(); printf("Running time is: %fms\n",double(end_time-start_time)); printf("\n排序的结果为:%s",isSorted(arr,N)==true?"true":"false"); return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。