实验一：快速排序算法及其优化
编程实现快速排序
// 编程实现的快排
void qSort(int n[],int l,int r){
if(l>=r){
return;
}
int i,j;
i=l-1;
j=r+1;
int x = n[ (i+j)/2 ];
while(i<j){
do i++ ;while(n[i]<x);
do j-- ;while(n[j]>x);
if(i<j){
int ten = n[i];
n[i] = n[j];
n[j] = ten;
}
}
qSort(n,l,j);
qSort(n,j+1,r);
}
快速排序的优化
1）基准的选择
1）基准的选择：快速排序的运行时间与划分是否对称有关。最坏情况下，每次划分过程产生两个区域分别包含n-1个元素和1个元素，其时间复杂度会达到O(n^2)。在最好的情况下，每次划分所取的基准都恰好是中值，即每次划分都产生两个大小为n/2的区域。此时，快排的时间复杂度为O(nlogn)。
所以基准的选择对快排而言至关重要。快排中基准的选择方式主要有以下三种：① 固定基准； ② 随机基准； ③ 三数取中
固定基准
// 编程实现的快排
// 固定基准
void qSort(int n[],int l,int r){
if(l>=r){
return;
}
int i,j;
i=l-1;
j=r+1;
int x = n[ (i+j)/2 ];
while(i<j){
do i++ ;while(n[i]<x);
do j-- ;while(n[j]>x);
if(i<j){
int ten = n[i];
n[i] = n[j];
n[j] = ten;
}
}
qSort(n,l,j);
qSort(n,j+1,r);
}
随机基准
std::mt19937_64 gen(std::random_device{}());
int generateRandomNumber(int min_value, int max_value) {
std::uniform_int_distribution<int> distribution(min_value, max_value);
return distribution(gen);
}
// 元素互换
void swap(int* arr,int i,int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 编程实现的快排
void qSort(int n[],int l,int r){
if(l>=r){
return;
}
int i,j;
i=l-1;
j=r+1;
int x = n[ (i+j)/2 ];
// 改为随机基准
int xx = generateRandomNumber(l,r);
swap(n ,(i+j)/2 , xx);
x = n[ (i+j)/2 ];
while(i<j){
do i++ ;while(n[i]<x);
do j-- ;while(n[j]>x);
if(i<j){
int ten = n[i];
n[i] = n[j];
n[j] = ten;
}
}
qSort(n,l,j);
qSort(n,j+1,r);
}
三数取中
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x =(l + r) >> 1;
// 多数取中法
int lll = 3;
if(r-l+1>=lll){
for (int i = l+1; i <= l+lll; i++) {
int key = q[i];
int j = i - 1;
while (j >= l && q[j] > key) {
q[j + 1] = q[j];
j--;
}
q[j + 1] = key;
}
int te = q[l+lll];
q[l+lll] = q[x];
q[x] = te;
}
x = q[x];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j){
int rdf = q[i];
q[i] = q[j];
q[j] = rdf;
}
}
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
2）（习题7.4-5）
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
if(r-l+1<=10){
for (int i = l+1; i <= r; i++) {
int key = q[i];
int j = i - 1;
while (j >= l && q[j] > key) {
q[j + 1] = q[j];
j--;
}
q[j + 1] = key;
}
return;
}
int i = l - 1, j = r + 1, x =(l + r) >> 1;
x = q[x];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j){
int rdf = q[i];
q[i] = q[j];
q[j] = rdf;
}
}
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
我的其他优化方式
拆递归
#include<stack>// 记得导入栈
void quick_sort2(int q[], int ll, int rr){
// int ind = 0;
int l,r;
stack<int> sta;
// 也可以用数组
sta.push(ll);
sta.push(rr);
while(!sta.empty()){
// r = sta[--ind];
// l = sta[--ind];
r = sta.top();
sta.pop();
l = sta.top();
sta.pop();
if (l >= r) continue;
if(r-l+1<=20){// 结合插入排序
for (int i = l+1; i <= r; i++) {
int key = q[i];
int j = i - 1;
while (j >= l && q[j] > key) {
q[j + 1] = q[j];
j--;
}
q[j + 1] = key;
}
continue;
}
// 多元取中
int lll = 5;
for (int i = l+1; i <= l+lll; i++) {
int key = q[i];
int j = i - 1;
while (j >= l && q[j] > key) {
q[j + 1] = q[j];
j--;
}
q[j + 1] = key;
}
int te = q[l+lll];
q[l+lll] = q[x];
q[x] = te;
i = l+lll-1;
x = q[x];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j){
int rdf = q[i];
q[i] = q[j];
q[j] = rdf;
}
}
sta.push(l);
sta.push(j);
sta.push(j+1);
sta.push(r);
}
}
多线程
双线程
// 多线程之双线程
#include <iostream>
#include <chrono>
#include<stack>//使用stack时需要的头文件
#include<mingw.thread.h> // 我的vscode 如果是别的编译器直接用thread包就可以
using namespace std;
void threadFunctionA(int q[], int ll, int rr){
// int ind = 0;
int l,r;
stack<int> sta;
sta.push(ll);
sta.push(rr);
while(!sta.empty()){
// r = sta[--ind];
// l = sta[--ind];
r = sta.top();
sta.pop();
l = sta.top();
sta.pop();
if (l >= r) continue;
if(r-l+1<=20){
for (int i = l+1; i <= r; i++) {
int key = q[i];
int j = i - 1;
while (j >= l && q[j] > key) {
q[j + 1] = q[j];
j--;
}
q[j + 1] = key;
}
continue;
}
int i = l - 1, j = r + 1, x =(l + r) >> 1;
// 多元取中
int lll = 5;
for (int i = l+1; i <= l+lll; i++) {
int key = q[i];
int j = i - 1;
while (j >= l && q[j] > key) {
q[j + 1] = q[j];
j--;
}
q[j + 1] = key;
}
int te = q[l+lll];
q[l+lll] = q[x];
q[x] = te;
i = l+lll-1;
x = q[x];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j){
int rdf = q[i];
q[i] = q[j];
q[j] = rdf;
}
}
sta.push(l);
sta.push(j);
sta.push(j+1);
sta.push(r);
}
}
void quick_sort3(int q[], int l, int r)
{
// 多线程
if (l >= r) return;
if(r-l+1<=10){
for (int i = l+1; i <= r; i++) {
int key = q[i];
int j = i - 1;
while (j >= l && q[j] > key) {
q[j + 1] = q[j];
j--;
}
q[j + 1] = key;
}
return;
}
int i = l - 1, j = r + 1, x =(l + r) >> 1;
// 另一种取中
int lll = 5;
for (int i = l+1; i <= l+lll; i++) {
int key = q[i];
int j = i - 1;
while (j >= l && q[j] > key) {
q[j + 1] = q[j];
j--;
}
q[j + 1] = key;
}
int te = q[l+lll];
q[l+lll] = q[x];
q[x] = te;
x = q[x];
i = l+lll-1;
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j){
int rdf = q[i];
q[i] = q[j];
q[j] = rdf;
}
}
// quick_sort(q, l, j), quick_sort(q, j + 1, r);
thread newTh1(threadFunctionA, q, l,j);
thread newTh2(threadFunctionA, q, j+1,r);
// 这里是拆分为两个线程
newTh1.join();
newTh2.join();
}
四线程
// 四线程并发
#include <iostream>
#include <chrono>
#include<stack>//使用stack时需要的头文件
#include<mingw.thread.h> // 我的vscode 如果是别的编译器直接用thread包就可以
using namespace std;
void threadForSort(int q[], int ll, int rr)
{
// 消递归
int ind = 0;
int l,r;
int* sta1 = new int[1000000]; // 也可以用stack 没太大差别 所以暂时没优化
sta1[ind++] = ll;
sta1[ind++] = rr;
while(ind>0){
r = sta1[--ind];
l = sta1[--ind];
if (l >= r) continue;
if(r-l+1<=20){
for (int i = l+1; i <= r; i++) {
int key = q[i];
int j = i - 1;
while (j >= l && q[j] > key) {
q[j + 1] = q[j];
j--;
}
q[j + 1] = key;
}
continue;
}
int i = l - 1, j = r + 1, x =(l + r) >> 1;
// 另一种取中
int lll = 5;
for (int i = l+1; i <= l+lll; i++) {
int key = q[i];
int j = i - 1;
while (j >= l && q[j] > key) {
q[j + 1] = q[j];
j--;
}
q[j + 1] = key;
}
int te = q[l+lll];
q[l+lll] = q[x];
q[x] = te;
i = l+lll-1;
x = q[x];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j){
int rdf = q[i];
q[i] = q[j];
q[j] = rdf;
}
}
sta1[ind++] =l ;
sta1[ind++] =j ;
sta1[ind++] =j+1 ;
sta1[ind++] =r ;
}
delete[] sta1;
}
// 元素互换
void swap(int* arr,int i,int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 数组分区
int partition(int* arr, int strat, int end) {
// 选取一个分区的-支点
int pivot = arr[strat];
// 左右指针指向
int left = strat, right = end;
while (left < right)
{
// 分别从左右两边遍历数组
while (arr[left] <= pivot && left < right)
left++;
while (arr[right] >= pivot && left < right)
right--;
// 交换左右指针的值
swap(arr, left, right);
}
if (arr[left] < pivot)
{
swap(arr, strat, left);
return left;
}
else if (arr[left] > pivot)
{
swap(arr, strat, left - 1);
return left - 1;
}
}
// 四线程
// 定义快速排序函数，递归实现
void quick_sort4(int* q, int l, int r) {
// 前提条件
if (l >= r)
return;
// 分区,返回分区下标
int mid = partition(q, l, r);
// 现在 拆成四个线程
// 递归调用
// quickSort(q, l, mid - 1); // 这里对应两个线程
int mid1 = partition(q, l, mid - 1);
thread newTh1(threadForSort, q, l,mid1-1);
thread newTh2(threadForSort, q, mid1+1,mid-1);
// quickSort(q, mid + 1, r);// 这里也对应两个线程
mid1 = partition(q, mid + 1, r);
thread newTh3(threadForSort, q, mid+1,mid1-1);
thread newTh4(threadForSort, q, mid1+1,r);
newTh1.join();
newTh2.join();
newTh3.join();
newTh4.join();
}
动态多线程
除了多线程之外的方法都没有特别明显的速度提升
同时，双线程，四线程的提升也都不如这里的动态多线程
所以 仅在这里展示一下 加速效果 同时提供我自己写的测试函数
// 动态进行多线程划分
#include <iostream>
#include <chrono>
#include<stack>//使用stack时需要的头文件
#include<mingw.thread.h> // 我的vscode 如果是别的编译器直接用thread包就可以
using namespace std;
int maxLength = 1000000;// 测试数据长度
int devideSize = maxLength/100; // 开新线程标准 防止产生太多线程 数据长度大于此数时开启新线程
int testNum = 15;// 测试次数
// volatile int maxThread
int compare(const void *a, const void *b)
{
int *pa = (int*)a;
int *pb = (int*)b;
return (*pa )- (*pb); //从小到大排序
}
int* getRand(int length)
{
int* n = new int[length];
int i;
for(i=0;i<length;i++){
n[i] = rand();
}
return n;
}
void threadForSort(int q[], int ll, int rr)
{
// thread* all[10000];
// int thNum = 0;
// 消递归
int ind = 0;
int l,r;
int* sta1 = new int[1000000]; // 也可以用stack 没太大差别 所以暂时没优化
sta1[ind++] = ll;
sta1[ind++] = rr;
while(ind>0){
r = sta1[--ind];
l = sta1[--ind];
if (l >= r) continue;
if(r-l+1<=20){
for (int i = l+1; i <= r; i++) {
int key = q[i];
int j = i - 1;
while (j >= l && q[j] > key) {
q[j + 1] = q[j];
j--;
}
q[j + 1] = key;
}
continue;
}
int i = l - 1, j = r + 1, x =(l + r) >> 1;
// 另一种取中
int lll = 5;
for (int i = l+1; i <= l+lll; i++) {
int key = q[i];
int j = i - 1;
while (j >= l && q[j] > key) {
q[j + 1] = q[j];
j--;
}
q[j + 1] = key;
}
int te = q[l+lll];
q[l+lll] = q[x];
q[x] = te;
i = l+lll-1;
x = q[x];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j){
int rdf = q[i];
q[i] = q[j];
q[j] = rdf;
}
}
// thread* point1 = NULL;
// thread* point2 = NULL;
if( j-l>devideSize ){
thread newTh1(threadForSort, q, l,j);
// all[thNum++] = &newTh1;
// point1 = &newTh1;
newTh1.join();
}else{
sta1[ind++] =l ;
sta1[ind++] =j ;
}
if( r-j>devideSize ){
thread newTh1(threadForSort, q, l,j);
// point2 = &newTh1;
newTh1.join();
// all[thNum++] = &newTh1;
}else{
sta1[ind++] =j+1 ;
sta1[ind++] =r ;
}
}
delete[] sta1;
}
// 元素互换
void swap(int* arr,int i,int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
void mysort(int *n,int l){
threadForSort(n,0,l-1);
}
void comprehensiveTest()
{// 进行100次测试 算平均时间 计算性能提升
double cAllTime = 0;
double myAllTime = 0;
int i,j;
int total = maxLength;
for(i=0;i<testNum;i++){
int *num1 = getRand(total);
int* num2 = new int[total];
for(j=0;j<total;j++){
num2[j] = num1[j];
}
auto start1 = std::chrono::high_resolution_clock::now(); // 记录开始时间
qsort(num1, total, sizeof(int), compare);
auto end1 = std::chrono::high_resolution_clock::now(); // 记录结束时间
auto start2 = std::chrono::high_resolution_clock::now(); // 记录开始时间
mysort(num2 , total);
auto end2 = std::chrono::high_resolution_clock::now(); // 记录结束时间
for(j=0;j<total;j++){
if(num1[i] !=num2[i]){
cout << "出错了" << endl;
break;
}
}
delete[] num1;
delete[] num2;
std::chrono::duration<double, std::milli> cTime = end1 - start1; // 计算执行时间
std::chrono::duration<double, std::milli> myTime = end2 - start2; // 计算执行时间
std::cout << "c++程序执行时间：" << cTime.count() << " 毫秒" << " " << "我的程序执行时间：" << myTime.count() << " 毫秒" ;
double gap = cTime.count()-myTime.count();
if(gap>0){
cout << " 快了 " << gap << " " <<endl;
}else{
cout << " 慢了 " << -1*gap << " " <<endl;
}
cAllTime +=cTime.count();
myAllTime+=myTime.count();
}
cAllTime/=testNum;
myAllTime/=testNum;
cout << "平均快了 " << cAllTime-myAllTime << endl;
cout << "提升比例 " << (cAllTime-myAllTime)/cAllTime << endl;
}
void compareTest(){
int count = 7;
int allLen[count] = {10000,50000,100000,1000000 , 5000000,8000000 , 10000000};
// int myScore;
// int cScore = myScore = 0;
int i,j;
for(i=0;i<count;i++){
int *num1 = getRand(allLen[i]);
int* num2 = new int[allLen[i]];
for(j=0;j<allLen[i];j++){
num2[j] = num1[j];
}
auto start1 = std::chrono::high_resolution_clock::now(); // 记录开始时间
qsort(num1, allLen[i], sizeof(int), compare);
auto end1 = std::chrono::high_resolution_clock::now(); // 记录结束时间
auto start2 = std::chrono::high_resolution_clock::now(); // 记录开始时间
mysort(num2 , allLen[i]);
auto end2 = std::chrono::high_resolution_clock::now(); // 记录结束时间
for(j=0;j<allLen[i];j++){
if(num1[i] !=num2[i]){
cout << "出错了" << endl;
break;
}
}
delete[] num1;
delete[] num2;
std::chrono::duration<double, std::milli> cTime = end1 - start1; // 计算执行时间
std::chrono::duration<double, std::milli> myTime = end2 - start2; // 计算执行时间
std::cout << "c++程序执行时间：" << cTime.count() << " 毫秒" << " " << "我的程序执行时间：" << myTime.count() << " 毫秒" ;
double gap = cTime.count()-myTime.count();
if(gap>0){
cout << " 快了 " << gap << " " <<endl;
}else{
cout << " 慢了 " << -1*gap << " " <<endl;
}
}
}
int main()
{
srand(time(0));
// compareTest();
comprehensiveTest();
return 0;
}
在我自己电脑上的输出：
c++程序执行时间：80.01 毫秒 我的程序执行时间：19.538
毫秒 快了 60.472
c++程序执行时间：79.171 毫秒 我的程序执行时间：30.538 毫秒 快了 48.633
c++程序执行时间：82.023 毫秒 我的程序执行时间：36.338 毫秒 快了 45.685
c++程序执行时间：78.11 毫秒 我的程序执行时间：23.378
毫秒 快了 54.732
c++程序执行时间：79.382 毫秒 我的程序执行时间：27.272 毫秒 快了 52.11
c++程序执行时间：79.223 毫秒 我的程序执行时间：19.551 毫秒 快了 59.672
c++程序执行时间：79.345 毫秒 我的程序执行时间：23.529 毫秒 快了 55.816
c++程序执行时间：78.306 毫秒 我的程序执行时间：25.156 毫秒 快了 53.15
c++程序执行时间：78.463 毫秒 我的程序执行时间：21.429 毫秒 快了 57.034
c++程序执行时间：78.98 毫秒 我的程序执行时间：28.995
毫秒 快了 49.985
c++程序执行时间：78.659 毫秒 我的程序执行时间：22.821 毫秒 快了 55.838
c++程序执行时间：78.817 毫秒 我的程序执行时间：25.161 毫秒 快了 53.656
c++程序执行时间：79.496 毫秒 我的程序执行时间：25.921 毫秒 快了 53.575
c++程序执行时间：78.601 毫秒 我的程序执行时间：31.099 毫秒 快了 47.502
c++程序执行时间：79.954 毫秒 我的程序执行时间：21.93
毫秒 快了 58.024
平均快了 53.7256
提升比例 0.678045
PS E:\c++_proje
我的其他优化方式--算法思想描述
- 在拆递归之前，也尝试了多元取中法，以及在长度足够短的时候采用插入排序直接排序的算法，所以在我的其他优化中都加入了这些成分。
拆递归思想
拆递归的优化方式是考虑到算法的递归调用是有一定的代价的，但其实每次递归只是传递的两个下标的差异，所以采用栈来拆解递归，进而算法执行的整个流程就不再进行递归调用。这样就能降低成本
双线程和四线程思想
因为我们进行一次partition之后，就会分解成两个序列，在对两个序列进行单独处理。同时也没有处理之后的合并操作。所以可以将两个序列的操作分给两个不同的线程进行处理，然后等待两个线程执行完毕即可。 同样的四线程也是这样，进行了两次partition之后，拆成四段之后在进行分线程。
动态多线程思想
延续前面的多线程方法，前面给线程设计的方法是通过解递归的方式对其所分得的序列进行快排处理，这里改动了一下，为其新增了创建新线程的功能。这样就是说，我们新建立的线程也能接着拆分出新的线程。这样就可以动态的进行线程创建。进而提高效率。
同时考虑到如果序列已经够短了，就不要接着划分了，所以在代码的全局变量加入了长度限制，只对足够长的序列进行下一步的拆分，交给不同的线程。否则就进行普通的解递归的快排处理。
附录----代码和性能比较
另附 从最开始优化，到最后的动态多线程的代码（可直接运行测试性能对比）
综合来看，每一次迭代 性能有提升，同时 在多线程，性能有极大提升
solution1:
// 插入排序 和取中法优化
#include <iostream>
#include <chrono>
#include<stack>
#include<mingw.thread.h>
using namespace std;
int testLength = 1000000;// 测试数据长度
int testNum = 15;// 测试次数
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
if(r-l+1<=10){
for (int i = l+1; i <= r; i++) {
int key = q[i];
int j = i - 1;
while (j >= l && q[j] > key) {
q[j + 1] = q[j];
j--;
}
q[j + 1] = key;
}
return;
}
int i = l - 1, j = r + 1, x =(l + r) >> 1;
int lll = 5;
for (int i = l+1; i <= l+lll; i++) {
int key = q[i];
int j = i - 1;
while (j >= l && q[j] > key) {
q[j + 1] = q[j];
j--;
}
q[j + 1] = key;
}
int te = q[l+lll];
q[l+lll] = q[x];
q[x] = te;
i = l+lll-1;
x = q[x];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j){
int rdf = q[i];
q[i] = q[j];
q[j] = rdf;
}
}
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
int* getRand(int length)
{
int* n = new int[length];
int i;
for(i=0;i<length;i++){
n[i] = rand();
}
return n;
}
int compare(const void *a, const void *b)
{
int *pa = (int*)a;
int *pb = (int*)b;
return (*pa )- (*pb); //从小到大排序
}
void mysort(int *n,int l){
quick_sort(n,0,l-1);
}
void comprehensiveTest()
{// 进行100次测试 算平均时间 计算性能提升
double cAllTime = 0;
double myAllTime = 0;
int i,j;
int total = testLength;
for(i=0;i<testNum;i++){
int *num1 = getRand(total);
int* num2 = new int[total];
for(j=0;j<total;j++){
num2[j] = num1[j];
}
auto start1 = std::chrono::high_resolution_clock::now(); // 记录开始时间
qsort(num1, total, sizeof(int), compare);
auto end1 = std::chrono::high_resolution_clock::now(); // 记录结束时间
auto start2 = std::chrono::high_resolution_clock::now(); // 记录开始时间
mysort(num2 , total);
auto end2 = std::chrono::high_resolution_clock::now(); // 记录结束时间
for(j=0;j<total;j++){
if(num1[i] !=num2[i]){
cout << "出错了" << endl;
break;
}
}
delete[] num1;
delete[] num2;
std::chrono::duration<double, std::milli> cTime = end1 - start1; // 计算执行时间
std::chrono::duration<double, std::milli> myTime = end2 - start2; // 计算执行时间
std::cout << "c++程序执行时间：" << cTime.count() << " 毫秒" << " " << "我的程序执行时间：" << myTime.count() << " 毫秒" ;
double gap = cTime.count()-myTime.count();
if(gap>0){
cout << " 快了 " << gap << " " <<endl;
}else{
cout << " 慢了 " << -1*gap << " " <<endl;
}
cAllTime +=cTime.count();
myAllTime+=myTime.count();
}
cAllTime/=testNum;
myAllTime/=testNum;
cout << "平均快了 " << cAllTime-myAllTime << endl;
cout << "提升比例 " << (cAllTime-myAllTime)/cAllTime << endl;
}
void compareTest(){
int count = 7;
int allLen[count] = {10000,50000,100000,1000000 , 5000000,8000000 , 10000000};
int myScor=0;
// int cScore = myScore = 0;
int i,j;
for(i=0;i<count;i++){
int *num1 = getRand(allLen[i]);
int* num2 = new int[allLen[i]];
for(j=0;j<allLen[i];j++){
num2[j] = num1[j];
}
auto start1 = std::chrono::high_resolution_clock::now(); // 记录开始时间
qsort(num1, allLen[i], sizeof(int), compare);
auto end1 = std::chrono::high_resolution_clock::now(); // 记录结束时间
auto start2 = std::chrono::high_resolution_clock::now(); // 记录开始时间
mysort(num2 , allLen[i]);
auto end2 = std::chrono::high_resolution_clock::now(); // 记录结束时间
for(j=0;j<allLen[i];j++){
if(num1[i] !=num2[i]){
cout << "出错了" << endl;
break;
}
}
delete[] num1;
delete[] num2;
std::chrono::duration<double, std::milli> cTime = end1 - start1; // 计算执行时间
std::chrono::duration<double, std::milli> myTime = end2 - start2; // 计算执行时间
std::cout << "c++程序执行时间：" << cTime.count() << " 毫秒" << " " << "我的程序执行时间：" << myTime.count() << " 毫秒" ;
double gap = cTime.count()-myTime.count();
if(gap>0){
cout << " 快了 " << gap << " " <<endl;
}else{
cout << " 慢了 " << -1*gap << " " <<endl;
}
}
}
int main()
{
srand(time(0));
// compareTest();
comprehensiveTest();
return 0;
}
性能比较输出：
PS E:\c++_project\test\算法实验1\output> cd 'e:\c++_project\test\算法实验1\output'
PS E:\c++_project\test\算法实验1\output> & .\'solution1.exe'
c++程序执行时间：80.034 毫秒 我的程序执行时间：75.85
毫秒 快了 4.184
c++程序执行时间：79.018 毫秒 我的程序执行时间：77.662 毫秒 快了 1.356
c++程序执行时间：79.014 毫秒 我的程序执行时间：76.007 毫秒 快了 3.007
c++程序执行时间：78.297 毫秒 我的程序执行时间：77.185 毫秒 快了 1.112
c++程序执行时间：79.307 毫秒 我的程序执行时间：76.601 毫秒 快了 2.706
c++程序执行时间：79.042 毫秒 我的程序执行时间：76.736 毫秒 快了 2.306
c++程序执行时间：78.652 毫秒 我的程序执行时间：76.327 毫秒 快了 2.325
c++程序执行时间：83.278 毫秒 我的程序执行时间：77.002 毫秒 快了 6.276
c++程序执行时间：79.51 毫秒 我的程序执行时间：77.103
毫秒 快了 2.407
c++程序执行时间：77.844 毫秒 我的程序执行时间：76.903 毫秒 快了 0.941
c++程序执行时间：78.333 毫秒 我的程序执行时间：78.68
毫秒 慢了 0.347
c++程序执行时间：79.051 毫秒 我的程序执行时间：76.808 毫秒 快了 2.243
c++程序执行时间：82.108 毫秒 我的程序执行时间：77.068 毫秒 快了 5.04
c++程序执行时间：78.342 毫秒 我的程序执行时间：77.008 毫秒 快了 1.334
c++程序执行时间：79.231 毫秒 我的程序执行时间：76.034 毫秒 快了 3.197
平均快了 2.53913
提升比例 0.0319774
solution2:
// 解递归
#include <iostream>
#include <chrono>
#include<stack>//
#include<mingw.thread.h>
using namespace std;
int testLength = 1000000;// 测试数据长度
int testNum = 15;// 测试次数
void quick_sort2(int q[], int ll, int rr){
// int ind = 0;
int l,r;
stack<int> sta;
// 也可以用数组 不过还是略慢
// sta[ind++] = ll;
// sta[ind++] = rr;
sta.push(ll);
sta.push(rr);
while(!sta.empty()){
// r = sta[--ind];
// l = sta[--ind];
r = sta.top();
sta.pop();
l = sta.top();
sta.pop();
if (l >= r) continue;
if(r-l+1<=20){
for (int i = l+1; i <= r; i++) {
int key = q[i];
int j = i - 1;
while (j >= l && q[j] > key) {
q[j + 1] = q[j];
j--;
}
q[j + 1] = key;
}
continue;
}
int i = l - 1, j = r + 1, x =(l + r) >> 1;
// 多元取中
int lll = 5;
for (int i = l+1; i <= l+lll; i++) {
int key = q[i];
int j = i - 1;
while (j >= l && q[j] > key) {
q[j + 1] = q[j];
j--;
}
q[j + 1] = key;
}
int te = q[l+lll];
q[l+lll] = q[x];
q[x] = te;
i = l+lll-1;
x = q[x];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j){
int rdf = q[i];
q[i] = q[j];
q[j] = rdf;
}
}
sta.push(l);
sta.push(j);
sta.push(j+1);
sta.push(r);
}
}
int* getRand(int length)
{
int* n = new int[length];
int i;
for(i=0;i<length;i++){
n[i] = rand();
}
return n;
}
int compare(const void *a, const void *b)
{
int *pa = (int*)a;
int *pb = (int*)b;
return (*pa )- (*pb); //从小到大排序
}
void mysort(int *n,int l){
quick_sort2(n,0,l-1);
}
void comprehensiveTest()
{// 进行100次测试 算平均时间 计算性能提升
double cAllTime = 0;
double myAllTime = 0;
int i,j;
int total = testLength;
for(i=0;i<testNum;i++){
int *num1 = getRand(total);
int* num2 = new int[total];
for(j=0;j<total;j++){
num2[j] = num1[j];
}
auto start1 = std::chrono::high_resolution_clock::now(); // 记录开始时间
qsort(num1, total, sizeof(int), compare);
auto end1 = std::chrono::high_resolution_clock::now(); // 记录结束时间
auto start2 = std::chrono::high_resolution_clock::now(); // 记录开始时间
mysort(num2 , total);
auto end2 = std::chrono::high_resolution_clock::now(); // 记录结束时间
for(j=0;j<total;j++){
if(num1[i] !=num2[i]){
cout << "出错了" << endl;
break;
}
}
delete[] num1;
delete[] num2;
std::chrono::duration<double, std::milli> cTime = end1 - start1; // 计算执行时间
std::chrono::duration<double, std::milli> myTime = end2 - start2; // 计算执行时间
std::cout << "c++程序执行时间：" << cTime.count() << " 毫秒" << " " << "我的程序执行时间：" << myTime.count() << " 毫秒" ;
double gap = cTime.count()-myTime.count();
if(gap>0){
cout << " 快了 " << gap << " " <<endl;
}else{
cout << " 慢了 " << -1*gap << " " <<endl;
}
cAllTime +=cTime.count();
myAllTime+=myTime.count();
}
cAllTime/=testNum;
myAllTime/=testNum;
cout << "平均快了 " << cAllTime-myAllTime << endl;
cout << "提升比例 " << (cAllTime-myAllTime)/cAllTime << endl;
}
void compareTest(){
int count = 7;
int allLen[count] = {10000,50000,100000,1000000 , 5000000,8000000 , 10000000};
int myScore;
int cScore = myScore = 0;
int i,j;
for(i=0;i<count;i++){
int *num1 = getRand(allLen[i]);
int* num2 = new int[allLen[i]];
for(j=0;j<allLen[i];j++){
num2[j] = num1[j];
}
auto start1 = std::chrono::high_resolution_clock::now(); // 记录开始时间
qsort(num1, allLen[i], sizeof(int), compare);
auto end1 = std::chrono::high_resolution_clock::now(); // 记录结束时间
auto start2 = std::chrono::high_resolution_clock::now(); // 记录开始时间
mysort(num2 , allLen[i]);
auto end2 = std::chrono::high_resolution_clock::now(); // 记录结束时间
for(j=0;j<allLen[i];j++){
if(num1[i] !=num2[i]){
cout << "出错了" << endl;
break;
}
}
delete[] num1;
delete[] num2;
std::chrono::duration<double, std::milli> cTime = end1 - start1; // 计算执行时间
std::chrono::duration<double, std::milli> myTime = end2 - start2; // 计算执行时间
std::cout << "c++程序执行时间：" << cTime.count() << " 毫秒" << " " << "我的程序执行时间：" << myTime.count() << " 毫秒" ;
double gap = cTime.count()-myTime.count();
if(gap>0){
cout << " 快了 " << gap << " " <<endl;
}else{
cout << " 慢了 " << -1*gap << " " <<endl;
}
}
}
int main()
{
srand(time(0));
// compareTest();
comprehensiveTest();
return 0;
}
性能比较输出：
PS E:\c++_project\test\算法实验1\output> & .\'solution2.exe'
c++程序执行时间：80.02 毫秒 我的程序执行时间：81.006
毫秒 慢了 0.986
c++程序执行时间：81.984 毫秒 我的程序执行时间：80.97
毫秒 快了 1.014
c++程序执行时间：79.043 毫秒 我的程序执行时间：78.169 毫秒 快了 0.874
c++程序执行时间：78.602 毫秒 我的程序执行时间：80.156 毫秒 慢了 1.554
c++程序执行时间：79.379 毫秒 我的程序执行时间：81.455 毫秒 慢了 2.076
c++程序执行时间：78.129 毫秒 我的程序执行时间：80.998 毫秒 慢了 2.869
c++程序执行时间：77.955 毫秒 我的程序执行时间：80.001 毫秒 慢了 2.046
c++程序执行时间：78.999 毫秒 我的程序执行时间：83.083 毫秒 慢了 4.084
c++程序执行时间：77.839 毫秒 我的程序执行时间：80.166 毫秒 慢了 2.327
c++程序执行时间：77.955 毫秒 我的程序执行时间：81.564 毫秒 慢了 3.609
c++程序执行时间：79.192 毫秒 我的程序执行时间：83.518 毫秒 慢了 4.326
c++程序执行时间：83.464 毫秒 我的程序执行时间：79.676 毫秒 快了 3.788
c++程序执行时间：80.032 毫秒 我的程序执行时间：79.001 毫秒 快了 1.031
c++程序执行时间：78.992 毫秒 我的程序执行时间：82.914 毫秒 慢了 3.922
c++程序执行时间：78.137 毫秒 我的程序执行时间：78 毫
秒 快了 0.137
平均快了 -1.397
提升比例 -0.0176134
solution3:
// 多线程之双线程
#include <iostream>
#include <chrono>
#include<stack>//使用stack时需要的头文件
#include<mingw.thread.h> // 我的vscode 如果是别的编译器直接用thread包就可以
using namespace std;
int testLength = 10000000;// 测试数据长度
int testNum = 15;// 测试次数
void threadFunctionA(int q[], int ll, int rr){
// int ind = 0;
int l,r;
stack<int> sta;
// 也可以用数组 不过还是略慢
// sta[ind++] = ll;
// sta[ind++] = rr;
sta.push(ll);
sta.push(rr);
while(!sta.empty()){
// r = sta[--ind];
// l = sta[--ind];
r = sta.top();
sta.pop();
l = sta.top();
sta.pop();
if (l >= r) continue;
if(r-l+1<=20){
for (int i = l+1; i <= r; i++) {
int key = q[i];
int j = i - 1;
while (j >= l && q[j] > key) {
q[j + 1] = q[j];
j--;
}
q[j + 1] = key;
}
continue;
}
int i = l - 1, j = r + 1, x =(l + r) >> 1;
// 多元取中
int lll = 5;
for (int i = l+1; i <= l+lll; i++) {
int key = q[i];
int j = i - 1;
while (j >= l && q[j] > key) {
q[j + 1] = q[j];
j--;
}
q[j + 1] = key;
}
int te = q[l+lll];
q[l+lll] = q[x];
q[x] = te;
i = l+lll-1;
x = q[x];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j){
int rdf = q[i];
q[i] = q[j];
q[j] = rdf;
}
}
// sta[ind++] =l ;
// sta[ind++] =j ;
// sta[ind++] =j+1 ;
// sta[ind++] =r ;
sta.push(l);
sta.push(j);
sta.push(j+1);
sta.push(r);
}
}
void quick_sort3(int q[], int l, int r)
{
// 多线程
if (l >= r) return;
if(r-l+1<=10){
for (int i = l+1; i <= r; i++) {
int key = q[i];
int j = i - 1;
while (j >= l && q[j] > key) {
q[j + 1] = q[j];
j--;
}
q[j + 1] = key;
}
return;
}
int i = l - 1, j = r + 1, x =(l + r) >> 1;
// 另一种取中
int lll = 5;
for (int i = l+1; i <= l+lll; i++) {
int key = q[i];
int j = i - 1;
while (j >= l && q[j] > key) {
q[j + 1] = q[j];
j--;
}
q[j + 1] = key;
}
int te = q[l+lll];
q[l+lll] = q[x];
q[x] = te;
x = q[x];
i = l+lll-1;
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j){
int rdf = q[i];
q[i] = q[j];
q[j] = rdf;
}
}
// quick_sort(q, l, j), quick_sort(q, j + 1, r);
thread newTh1(threadFunctionA, q, l,j);
thread newTh2(threadFunctionA, q, j+1,r);
// 这里是拆分为两个线程
newTh1.join();
newTh2.join();
}
int* getRand(int length)
{
int* n = new int[length];
int i;
for(i=0;i<length;i++){
n[i] = rand();
}
return n;
}
int compare(const void *a, const void *b)
{
int *pa = (int*)a;
int *pb = (int*)b;
return (*pa )- (*pb); //从小到大排序
}
void mysort(int *n,int l){
quick_sort3(n,0,l-1);
}
void comprehensiveTest()
{// 进行100次测试 算平均时间 计算性能提升
double cAllTime = 0;
double myAllTime = 0;
int i,j;
int total = testLength;
for(i=0;i<testNum;i++){
int *num1 = getRand(total);
int* num2 = new int[total];
for(j=0;j<total;j++){
num2[j] = num1[j];
}
auto start1 = std::chrono::high_resolution_clock::now(); // 记录开始时间
qsort(num1, total, sizeof(int), compare);
auto end1 = std::chrono::high_resolution_clock::now(); // 记录结束时间
auto start2 = std::chrono::high_resolution_clock::now(); // 记录开始时间
mysort(num2 , total);
auto end2 = std::chrono::high_resolution_clock::now(); // 记录结束时间
for(j=0;j<total;j++){
if(num1[i] !=num2[i]){
cout << "出错了" << endl;
break;
}
}
delete[] num1;
delete[] num2;
std::chrono::duration<double, std::milli> cTime = end1 - start1; // 计算执行时间
std::chrono::duration<double, std::milli> myTime = end2 - start2; // 计算执行时间
std::cout << "c++程序执行时间：" << cTime.count() << " 毫秒" << " " << "我的程序执行时间：" << myTime.count() << " 毫秒" ;
double gap = cTime.count()-myTime.count();
if(gap>0){
cout << " 快了 " << gap << " " <<endl;
}else{
cout << " 慢了 " << -1*gap << " " <<endl;
}
cAllTime +=cTime.count();
myAllTime+=myTime.count();
}
cAllTime/=testNum;
myAllTime/=testNum;
cout << "平均快了 " << cAllTime-myAllTime << endl;
cout << "提升比例 " << (cAllTime-myAllTime)/cAllTime << endl;
}
void compareTest(){
int count = 7;
int allLen[count] = {10000,50000,100000,1000000 , 5000000,8000000 , 10000000};
// int myScore;
// int cScore = myScore = 0;
int i,j;
for(i=0;i<count;i++){
int *num1 = getRand(allLen[i]);
int* num2 = new int[allLen[i]];
for(j=0;j<allLen[i];j++){
num2[j] = num1[j];
}
auto start1 = std::chrono::high_resolution_clock::now(); // 记录开始时间
qsort(num1, allLen[i], sizeof(int), compare);
auto end1 = std::chrono::high_resolution_clock::now(); // 记录结束时间
auto start2 = std::chrono::high_resolution_clock::now(); // 记录开始时间
mysort(num2 , allLen[i]);
auto end2 = std::chrono::high_resolution_clock::now(); // 记录结束时间
for(j=0;j<allLen[i];j++){
if(num1[i] !=num2[i]){
cout << "出错了" << endl;
break;
}
}
delete[] num1;
delete[] num2;
std::chrono::duration<double, std::milli> cTime = end1 - start1; // 计算执行时间
std::chrono::duration<double, std::milli> myTime = end2 - start2; // 计算执行时间
std::cout << "c++程序执行时间：" << cTime.count() << " 毫秒" << " " << "我的程序执行时间：" << myTime.count() << " 毫秒" ;
double gap = cTime.count()-myTime.count();
if(gap>0){
cout << " 快了 " << gap << " " <<endl;
}else{
cout << " 慢了 " << -1*gap << " " <<endl;
}
}
}
int main()
{
srand(time(0));
// compareTest();
comprehensiveTest();
return 0;
}
性能比较输出：
PS E:\c++_project\test\算法实验1\output> & .\'solution3.exe'
c++程序执行时间：77.988 毫秒 我的程序执行时间：74.044 毫秒 快了 3.944
c++程序执行时间：83.498 毫秒 我的程序执行时间：79.803 毫秒 快了 3.695
c++程序执行时间：79.749 毫秒 我的程序执行时间：52.482 毫秒 快了 27.267
c++程序执行时间：77.736 毫秒 我的程序执行时间：47.673 毫秒 快了 30.063
c++程序执行时间：78.066 毫秒 我的程序执行时间：62.493 毫秒 快了 15.573
c++程序执行时间：80.071 毫秒 我的程序执行时间：78.52
毫秒 快了 1.551
c++程序执行时间：78.476 毫秒 我的程序执行时间：79.85
毫秒 慢了 1.374
c++程序执行时间：79.398 毫秒 我的程序执行时间：75.689 毫秒 快了 3.709
c++程序执行时间：79.142 毫秒 我的程序执行时间：80.422 毫秒 慢了 1.28
c++程序执行时间：81.046 毫秒 我的程序执行时间：74.736 毫秒 快了 6.31
c++程序执行时间：79.603 毫秒 我的程序执行时间：52.47
毫秒 快了 27.133
c++程序执行时间：79.955 毫秒 我的程序执行时间：57.383 毫秒 快了 22.572
c++程序执行时间：84.608 毫秒 我的程序执行时间：75.01
毫秒 快了 9.598
c++程序执行时间：79.721 毫秒 我的程序执行时间：67.263 毫秒 快了 12.458
c++程序执行时间：82.756 毫秒 我的程序执行时间：77.532 毫秒 快了 5.224
平均快了 11.0962
提升比例 0.138493
solution4:
// 四线程并发
#include <iostream>
#include <chrono>
#include<stack>//使用stack时需要的头文件
#include<mingw.thread.h> // 我的vscode 如果是别的编译器直接用thread包就可以
using namespace std;
int testLength = 1000000;// 测试数据长度
int testNum = 15;// 测试次数
int compare(const void *a, const void *b)
{
int *pa = (int*)a;
int *pb = (int*)b;
return (*pa )- (*pb); //从小到大排序
}
int* getRand(int length)
{
int* n = new int[length];
int i;
for(i=0;i<length;i++){
n[i] = rand();
}
return n;
}
void threadForSort(int q[], int ll, int rr)
{
// 消递归
int ind = 0;
int l,r;
int* sta1 = new int[1000000]; // 也可以用stack 没太大差别 所以暂时没优化
sta1[ind++] = ll;
sta1[ind++] = rr;
while(ind>0){
r = sta1[--ind];
l = sta1[--ind];
if (l >= r) continue;
if(r-l+1<=20){
for (int i = l+1; i <= r; i++) {
int key = q[i];
int j = i - 1;
while (j >= l && q[j] > key) {
q[j + 1] = q[j];
j--;
}
q[j + 1] = key;
}
continue;
}
int i = l - 1, j = r + 1, x =(l + r) >> 1;
// 另一种取中
int lll = 5;
for (int i = l+1; i <= l+lll; i++) {
int key = q[i];
int j = i - 1;
while (j >= l && q[j] > key) {
q[j + 1] = q[j];
j--;
}
q[j + 1] = key;
}
int te = q[l+lll];
q[l+lll] = q[x];
q[x] = te;
i = l+lll-1;
x = q[x];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j){
int rdf = q[i];
q[i] = q[j];
q[j] = rdf;
}
}
sta1[ind++] =l ;
sta1[ind++] =j ;
sta1[ind++] =j+1 ;
sta1[ind++] =r ;
// sta.push(l);
// sta.push(j);
// sta.push(j+1);
// sta.push(r);
}
delete[] sta1;
}
// 元素互换
void swap(int* arr,int i,int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 数组分区
int partition(int* arr, int strat, int end) {
// 选取一个分区的-支点
int pivot = arr[strat];
// 左右指针指向
int left = strat, right = end;
while (left < right)
{
// 分别从左右两边遍历数组
while (arr[left] <= pivot && left < right)
left++;
while (arr[right] >= pivot && left < right)
right--;
// 交换左右指针的值
swap(arr, left, right);
}
if (arr[left] < pivot)
{
swap(arr, strat, left);
return left;
}
else if (arr[left] > pivot)
{
swap(arr, strat, left - 1);
return left - 1;
}
}
// 四线程
// 定义快速排序函数，递归实现
void quick_sort4(int* q, int l, int r) {
// 前提条件
if (l >= r)
return;
// 分区,返回分区下标
int mid = partition(q, l, r);
// 现在 拆成四个线程
// 递归调用
// quickSort(q, l, mid - 1); // 这里对应两个线程
int mid1 = partition(q, l, mid - 1);
thread newTh1(threadForSort, q, l,mid1-1);
thread newTh2(threadForSort, q, mid1+1,mid-1);
// quickSort(q, mid + 1, r);// 这里也对应两个线程
mid1 = partition(q, mid + 1, r);
thread newTh3(threadForSort, q, mid+1,mid1-1);
thread newTh4(threadForSort, q, mid1+1,r);
newTh1.join();
newTh2.join();
newTh3.join();
newTh4.join();
}
void mysort(int *n,int l){
quick_sort4(n,0,l-1);
}
void comprehensiveTest()
{// 进行100次测试 算平均时间 计算性能提升
double cAllTime = 0;
double myAllTime = 0;
int i,j;
int total = testLength;
for(i=0;i<testNum;i++){
int *num1 = getRand(total);
int* num2 = new int[total];
for(j=0;j<total;j++){
num2[j] = num1[j];
}
auto start1 = std::chrono::high_resolution_clock::now(); // 记录开始时间
qsort(num1, total, sizeof(int), compare);
auto end1 = std::chrono::high_resolution_clock::now(); // 记录结束时间
auto start2 = std::chrono::high_resolution_clock::now(); // 记录开始时间
mysort(num2 , total);
auto end2 = std::chrono::high_resolution_clock::now(); // 记录结束时间
for(j=0;j<total;j++){
if(num1[i] !=num2[i]){
cout << "出错了" << endl;
break;
}
}
delete[] num1;
delete[] num2;
std::chrono::duration<double, std::milli> cTime = end1 - start1; // 计算执行时间
std::chrono::duration<double, std::milli> myTime = end2 - start2; // 计算执行时间
std::cout << "c++程序执行时间：" << cTime.count() << " 毫秒" << " " << "我的程序执行时间：" << myTime.count() << " 毫秒" ;
double gap = cTime.count()-myTime.count();
if(gap>0){
cout << " 快了 " << gap << " " <<endl;
}else{
cout << " 慢了 " << -1*gap << " " <<endl;
}
cAllTime +=cTime.count();
myAllTime+=myTime.count();
}
cAllTime/=testNum;
myAllTime/=testNum;
cout << "平均快了 " << cAllTime-myAllTime << endl;
cout << "提升比例 " << (cAllTime-myAllTime)/cAllTime << endl;
}
void compareTest(){
int count = 7;
int allLen[count] = {10000,50000,100000,1000000 , 5000000,8000000 , 10000000};
// int myScore;
// int cScore = myScore = 0;
int i,j;
for(i=0;i<count;i++){
int *num1 = getRand(allLen[i]);
int* num2 = new int[allLen[i]];
for(j=0;j<allLen[i];j++){
num2[j] = num1[j];
}
auto start1 = std::chrono::high_resolution_clock::now(); // 记录开始时间
qsort(num1, allLen[i], sizeof(int), compare);
auto end1 = std::chrono::high_resolution_clock::now(); // 记录结束时间
auto start2 = std::chrono::high_resolution_clock::now(); // 记录开始时间
mysort(num2 , allLen[i]);
auto end2 = std::chrono::high_resolution_clock::now(); // 记录结束时间
for(j=0;j<allLen[i];j++){
if(num1[i] !=num2[i]){
cout << "出错了" << endl;
break;
}
}
delete[] num1;
delete[] num2;
std::chrono::duration<double, std::milli> cTime = end1 - start1; // 计算执行时间
std::chrono::duration<double, std::milli> myTime = end2 - start2; // 计算执行时间
std::cout << "c++程序执行时间：" << cTime.count() << " 毫秒" << " " << "我的程序执行时间：" << myTime.count() << " 毫秒" ;
double gap = cTime.count()-myTime.count();
if(gap>0){
cout << " 快了 " << gap << " " <<endl;
}else{
cout << " 慢了 " << -1*gap << " " <<endl;
}
}
}
int main()
{
srand(time(0));
// compareTest();
comprehensiveTest();
return 0;
}
性能比较输出：
PS E:\c++_project\test\算法实验1\output> & .\'solution4.exe'
c++程序执行时间：79.005 毫秒 我的程序执行时间：45.277 毫秒 快了 33.728
c++程序执行时间：80.556 毫秒 我的程序执行时间：42.003 毫秒 快了 38.553
c++程序执行时间：79.536 毫秒 我的程序执行时间：39.296 毫秒 快了 40.24
c++程序执行时间：77.783 毫秒 我的程序执行时间：41.132 毫秒 快了 36.651
c++程序执行时间：80.678 毫秒 我的程序执行时间：41.417 毫秒 快了 39.261
c++程序执行时间：79.392 毫秒 我的程序执行时间：46.027 毫秒 快了 33.365
c++程序执行时间：77.973 毫秒 我的程序执行时间：62.482 毫秒 快了 15.491
c++程序执行时间：78.536 毫秒 我的程序执行时间：44.406 毫秒 快了 34.13
c++程序执行时间：79.521 毫秒 我的程序执行时间：49.285 毫秒 快了 30.236
c++程序执行时间：78.469 毫秒 我的程序执行时间：42.266 毫秒 快了 36.203
c++程序执行时间：79.798 毫秒 我的程序执行时间：48.401 毫秒 快了 31.397
c++程序执行时间：83.086 毫秒 我的程序执行时间：41.221 毫秒 快了 41.865
c++程序执行时间：80.128 毫秒 我的程序执行时间：34.254 毫秒 快了 45.874
c++程序执行时间：83.818 毫秒 我的程序执行时间：35.591 毫秒 快了 48.227
c++程序执行时间：87.433 毫秒 我的程序执行时间：37.273 毫秒 快了 50.16
平均快了 37.0254
提升比例 0.460625
solution5:
// 动态进行多线程划分
#include <iostream>
#include <chrono>
#include<stack>//使用stack时需要的头文件
#include<mingw.thread.h> // 我的vscode 如果是别的编译器直接用thread包就可以
using namespace std;
int maxLength = 1000000;// 测试数据长度
int devideSize = maxLength/100; // 开新线程标准 防止产生太多线程 数据长度大于此数时开启新线程
int testNum = 15;// 测试次数
// volatile int maxThread
int compare(const void *a, const void *b)
{
int *pa = (int*)a;
int *pb = (int*)b;
return (*pa )- (*pb); //从小到大排序
}
int* getRand(int length)
{
int* n = new int[length];
int i;
for(i=0;i<length;i++){
n[i] = rand();
}
return n;
}
void threadForSort(int q[], int ll, int rr)
{
// thread* all[10000];
// int thNum = 0;
// 消递归
int ind = 0;
int l,r;
int* sta1 = new int[1000000]; // 也可以用stack 没太大差别 所以暂时没优化
sta1[ind++] = ll;
sta1[ind++] = rr;
while(ind>0){
r = sta1[--ind];
l = sta1[--ind];
if (l >= r) continue;
if(r-l+1<=20){
for (int i = l+1; i <= r; i++) {
int key = q[i];
int j = i - 1;
while (j >= l && q[j] > key) {
q[j + 1] = q[j];
j--;
}
q[j + 1] = key;
}
continue;
}
int i = l - 1, j = r + 1, x =(l + r) >> 1;
// 另一种取中
int lll = 5;
for (int i = l+1; i <= l+lll; i++) {
int key = q[i];
int j = i - 1;
while (j >= l && q[j] > key) {
q[j + 1] = q[j];
j--;
}
q[j + 1] = key;
}
int te = q[l+lll];
q[l+lll] = q[x];
q[x] = te;
i = l+lll-1;
x = q[x];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j){
int rdf = q[i];
q[i] = q[j];
q[j] = rdf;
}
}
// thread* point1 = NULL;
// thread* point2 = NULL;
if( j-l>devideSize ){
thread newTh1(threadForSort, q, l,j);
// all[thNum++] = &newTh1;
// point1 = &newTh1;
newTh1.join();
}else{
sta1[ind++] =l ;
sta1[ind++] =j ;
}
if( r-j>devideSize ){
thread newTh1(threadForSort, q, l,j);
// point2 = &newTh1;
newTh1.join();
// all[thNum++] = &newTh1;
}else{
sta1[ind++] =j+1 ;
sta1[ind++] =r ;
}
}
delete[] sta1;
}
// 元素互换
void swap(int* arr,int i,int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
void mysort(int *n,int l){
threadForSort(n,0,l-1);
}
void comprehensiveTest()
{// 进行100次测试 算平均时间 计算性能提升
double cAllTime = 0;
double myAllTime = 0;
int i,j;
int total = maxLength;
for(i=0;i<testNum;i++){
int *num1 = getRand(total);
int* num2 = new int[total];
for(j=0;j<total;j++){
num2[j] = num1[j];
}
auto start1 = std::chrono::high_resolution_clock::now(); // 记录开始时间
qsort(num1, total, sizeof(int), compare);
auto end1 = std::chrono::high_resolution_clock::now(); // 记录结束时间
auto start2 = std::chrono::high_resolution_clock::now(); // 记录开始时间
mysort(num2 , total);
auto end2 = std::chrono::high_resolution_clock::now(); // 记录结束时间
for(j=0;j<total;j++){
if(num1[i] !=num2[i]){
cout << "出错了" << endl;
break;
}
}
delete[] num1;
delete[] num2;
std::chrono::duration<double, std::milli> cTime = end1 - start1; // 计算执行时间
std::chrono::duration<double, std::milli> myTime = end2 - start2; // 计算执行时间
std::cout << "c++程序执行时间：" << cTime.count() << " 毫秒" << " " << "我的程序执行时间：" << myTime.count() << " 毫秒" ;
double gap = cTime.count()-myTime.count();
if(gap>0){
cout << " 快了 " << gap << " " <<endl;
}else{
cout << " 慢了 " << -1*gap << " " <<endl;
}
cAllTime +=cTime.count();
myAllTime+=myTime.count();
}
cAllTime/=testNum;
myAllTime/=testNum;
cout << "平均快了 " << cAllTime-myAllTime << endl;
cout << "提升比例 " << (cAllTime-myAllTime)/cAllTime << endl;
}
void compareTest(){
int count = 7;
int allLen[count] = {10000,50000,100000,1000000 , 5000000,8000000 , 10000000};
// int myScore;
// int cScore = myScore = 0;
int i,j;
for(i=0;i<count;i++){
int *num1 = getRand(allLen[i]);
int* num2 = new int[allLen[i]];
for(j=0;j<allLen[i];j++){
num2[j] = num1[j];
}
auto start1 = std::chrono::high_resolution_clock::now(); // 记录开始时间
qsort(num1, allLen[i], sizeof(int), compare);
auto end1 = std::chrono::high_resolution_clock::now(); // 记录结束时间
auto start2 = std::chrono::high_resolution_clock::now(); // 记录开始时间
mysort(num2 , allLen[i]);
auto end2 = std::chrono::high_resolution_clock::now(); // 记录结束时间
for(j=0;j<allLen[i];j++){
if(num1[i] !=num2[i]){
cout << "出错了" << endl;
break;
}
}
delete[] num1;
delete[] num2;
std::chrono::duration<double, std::milli> cTime = end1 - start1; // 计算执行时间
std::chrono::duration<double, std::milli> myTime = end2 - start2; // 计算执行时间
std::cout << "c++程序执行时间：" << cTime.count() << " 毫秒" << " " << "我的程序执行时间：" << myTime.count() << " 毫秒" ;
double gap = cTime.count()-myTime.count();
if(gap>0){
cout << " 快了 " << gap << " " <<endl;
}else{
cout << " 慢了 " << -1*gap << " " <<endl;
}
}
}
int main()
{
srand(time(0));
// compareTest();
comprehensiveTest();
return 0;
}
性能比较输出：
PS E:\c++_project\test\算法实验1\output> cd 'e:\c++_project\test\算法实验1\output'
PS E:\c++_project\test\算法实验1\output> & .\'solution5.exe'
c++程序执行时间：79.938 毫秒 我的程序执行时间：30.877 毫秒 快了 49.061
c++程序执行时间：77.712 毫秒 我的程序执行时间：34.406 毫秒 快了 43.306
c++程序执行时间：80.698 毫秒 我的程序执行时间：28.973 毫秒 快了 51.725
c++程序执行时间：77.65 毫秒 我的程序执行时间：30.457
毫秒 快了 47.193
c++程序执行时间：78.662 毫秒 我的程序执行时间：31.154 毫秒 快了 47.508
c++程序执行时间：79.299 毫秒 我的程序执行时间：22.993 毫秒 快了 56.306
c++程序执行时间：79.999 毫秒 我的程序执行时间：26.001 毫秒 快了 53.998
c++程序执行时间：78.309 毫秒 我的程序执行时间：24.786 毫秒 快了 53.523
c++程序执行时间：79.532 毫秒 我的程序执行时间：31.678 毫秒 快了 47.854
c++程序执行时间：79.489 毫秒 我的程序执行时间：22.993 毫秒 快了 56.496
c++程序执行时间：79.261 毫秒 我的程序执行时间：20.153 毫秒 快了 59.108
c++程序执行时间：79.368 毫秒 我的程序执行时间：26.855 毫秒 快了 52.513
c++程序执行时间：77.946 毫秒 我的程序执行时间：31.01
毫秒 快了 46.936
c++程序执行时间：79 毫秒 我的程序执行时间：26.999 毫
秒 快了 52.001
c++程序执行时间：78.758 毫秒 我的程序执行时间：19 毫
秒 快了 59.758
平均快了 51.8191
提升比例 0.655594