C++分治策略实现快速排序
2019-10-08 08:48:24来源:博客园 阅读 ()
C++分治策略实现快速排序
问题描述:
给定一个未知顺序的n个元素组成的数组,现要利用快速排序算法对这n个元素进行非递减排序。
细节须知:
(1)代码实现了利用递归对数组进行快速排序,其中limit为从已有的随机数文件中输入的所要进行排序的数据的数量(生成随机数并写入文件的过程已在前篇中写出)。
(2)算法主要利用哨兵元素对数据进行分块,递归无限细分之后实现排序。
(3)代码同样利用clock函数对算法的执行时间进行计算以进行算法的效率评估。
(4)为了验证排序结果,代码实现了将排序后的内容输出到同文件夹下的sort_number.txt文件中。
算法原理:
它的完成过程主要是将数组分解为两部分,然后分别对每一部分排序。在划分数组时,是将所有小于某个哨兵元素的项目放到该项目之前,将所有大于该哨兵元素的项目放到该项目之后。哨兵元素可以是任意项目,为方便起见,通常直接选择第一个项目。因而可以总结为三步:(1)分解;(2)递归求解;(3)合并。其中,算法的核心部分为对数组进行划分,将小于x的元素放在原数组的左半部分,将大于x的元素放在原数组的右半部分。
1 #include <iostream> 2 #include <fstream> 3 #include <cstdlib> 4 #include <ctime> 5 #include <algorithm> 6 using namespace std; 7 #define limit 100000 8 9 void quicksort(int a[], int low ,int high) 10 { 11 if(low<high){ //递归的终止条件 12 int i = low, j = high; //使用i,j在对应区间内对数组进行排序; 13 int x = a[low]; //将数组的第一个元素作为哨兵,通过这种方式取出哨兵元素 14 15 while(i < j){ 16 while(i < j && a[j] >= x) 17 j--; //从右向左寻找第一个比哨兵元素小的元素 18 if(i < j){ 19 a[i] = a[j]; 20 i++; //把找到的第一个小于哨兵元素的元素值赋值给第一个元素,并把下界(i)向后移一位 21 } 22 23 while(i < j && a[i] <= x) 24 i++; //从左向右寻找第一个比哨兵元素大的元素 25 if(i < j){ 26 a[j] = a[i]; 27 j--; 28 } //把找到的第一个大于哨兵元素的元素值赋值给下标为j的元素,并把上界(j)向前移一位 29 } 30 a[i] = x; //把哨兵赋值到下标为i的位置,i前的元素均比哨兵元素小,i后的元素均比哨兵元素大 31 32 quicksort(a, low ,i-1); //递归进行哨兵前后两部分元素排序 33 quicksort(a, i+1 ,high); 34 } 35 } 36 int main(void) 37 { 38 ifstream fin; 39 ofstream fout; 40 int x; 41 int i; 42 int a[limit]; 43 44 fin.open("random_number.txt"); 45 if(!fin){ 46 cerr<<"Can not open file 'random_number.txt' "<<endl; 47 return -1; 48 } 49 time_t first, last; 50 51 52 for(i=0; i<limit; i++){ 53 fin>>a[i]; 54 } 55 fin.close(); 56 57 first = clock(); 58 59 quicksort(a,0,limit-1); 60 61 last = clock(); 62 63 fout.open("sort_number.txt"); 64 65 if(!fout){ 66 cerr<<"Can not open file 'sort_number.txt' "<<endl; 67 return -1; 68 } 69 for(i=0; i<limit; i++){ 70 fout<<a[i]<<endl; 71 } 72 73 fout.close(); 74 75 cout<<"Sort completed (already output to file 'sort_number.txt')!"<<endl; 76 cout<<"Time cost: "<<last-first<<endl; 77 78 return 0; 79 }
程序设计思路:
(1)分解:以a[p]为基准元素将a[p:r]划分成3段a[p:q-1],a[q]和a[q+1:r],使得a[p:q-1]中任何元素小于等于a[q],a[q+1:r]中任何元素大于等于a[q]。下标q在划分过程中确定。
(2)递归求解:通过递归调用快速排序算法,分别对a[p:q-1]和a[q+1:r]进行排序。
(3)合并:由于对a[p:q-1]和a[q+1:r]的排序是就地进行的,所以在a[p:q-1]和a[q+1:r]都已排好序后不需要执行任何计算,a[p:r]就已排好序。
结果数据格式为time_t格式相减得到的长整型以及输出到文件的整形数据。
时间复杂性分析:
对于输入序列a[p:r],算法的计算时间显然为O(r-p-1).
快速排序的运行时间与划分是否对称有关,其最坏情况发生在划分过程中产生的两个区域分别包含n-1个元素和1个元素的时候。由于算法的计算时间为O(n),所以如果算法的每一步都出现这种不对称划分,则其计算时间复杂性T(n)满足
T(n)= O(1),n≤1
T(n)= T(n-1)+O(n),n>1
解此递归方程可得T(n)=O(n²)。
在最好情况下,每次划分所取的基准都恰好为中值,即每次划分都产生两个大小为n/2的区域,此时,算法的计算时间T(n)满足
T(n)= O(1),n≤1
T(n)= 2T(n/2)+O(n),n>1
其解为T(n)=O(nlogn)。
可以证明,快速排序算法在平均情况下的时间复杂性也是O(nlogn)。
原文链接:https://www.cnblogs.com/Jesse-Cavendish/p/11615866.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++ 转换函数搭配友元函数 2020-06-10
- C++ 自动转换和强制类型转换(用户自定义类类型) 2020-06-10
- C++ rand函数 2020-06-10
- C++ 友元函数 2020-06-10
- C++ 运算符重载 2020-06-10
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash