首页 > 其他分享 >快排优化

快排优化

时间：2023-11-07 21:11:45浏览次数：38  
标签：sta 毫秒 int c++ 程序执行 快排 时间 优化

实验一：快速排序算法及其优化

编程实现快速排序

// 编程实现的快排
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

标签：sta,毫秒,int,c++,程序执行,快排,时间,优化
From： https://www.cnblogs.com/cndccm/p/17816022.html

相关文章

  • 前端性能优化有哪些？
    前端有哪些性能优化？前端性能优化分两部分1、加载性能优化2、渲染性能优化一、加载性能优化本质： •1、减少请求次数； •2、减少请求资源的大小； •3、网络优化；1、减少请求次数方式   1）图片资源 ○CSS雪碧图：把一些常用、重复使用的小图合并成一张大图 ......
  • centos 安装etcd|待优化
    下载https://github.com/etcd-io/etcd/releases/download/v3.5.0/etcd-v3.5.0-linux-amd64.tar.gz安装解压cd/usr/local/srctarzxvfetcd-v3.5.0-linux-amd64.tar.gzmvetcd-v3.5.0-linux-amd64etcd-v3.5.0配置vi/etc/profileexportPATH=$PATH:/usr/local/src/etcd-v3.5......
  • Unity如何优化Drawcall
    降低游戏的Drawcall，是渲染优化很重要的手段，接下来从以下4个方面来分析如何降低DrawCall:(1)降低Drawcall的意义是什么?如何查看游戏的Drawcall;(2)Drawcall合批的常用的技术手段原理与优缺点;(3)组织项目让Drawcall最小需要注意的点;搞清楚这些，Drawcall的优化基本上就能很......
  • Unity性能优化之内存篇
    本文和传统的内存优化不一样，不是讲如何降低内存占用，而是讲编程开发中要注意的内存问题以及一些内存技术的演变与原理。 本文很长，目录如下:(1)Application进程的内存分段;(2)OS动态内存分配与手动内存管理;(3)什么是内存碎片,避免内存碎片常用手段;(4)什么是内存泄漏,预防与......
  • 如何做好Unity项目性能优化
      在面试中，我们经常会被问各种”莫名奇妙”的问题,比如这道:”你是如何做好Unity项目性能优化的?”。“这个问题也太泛了吧，没有具体的优化点,这怎么回答?”瞬间跃入脑海。做面试复盘的时候，你可能会想这个面试官是不是什么都不懂，是个”青铜”啊。没错，能问这道问题的面试官要么......
  • 看我一行代码起飞，Glide加载gif优化实践
    前言最近项目中有使用到gif动画，加上本身已经引入了Glide（支持gif）库，所以便用Glide来加载了；但在使用过程中还是遇到了不少困难，在此记录下，希望可以给遇到类似问题的你一些思考和建议。一、Glide加载gif1.在项目中添加依赖dependencies{compile'com.github.bumptech.glide:glide:4......
  • 云存储/视频监控管理平台EasyCVR，使用sqlite数据库出现卡顿该如何优化？
    视频集中存储/云存储/视频监控管理平台EasyCVR能在复杂的网络环境中，将分散的各类视频资源进行统一汇聚、整合、集中管理，实现视频资源的鉴权管理、按需调阅、全网分发、智能分析等。AI智能大数据视频分析EasyCVR平台已经广泛应用在工地、工厂、园区、楼宇、校园、仓储等场景中。有用......
  • cf1856E2. PermuTree (hard version)（bitset+二进制优化背包+开不同大小bitset）
    https://codeforces.com/contest/1856/problem/E2结论是显然的，关键是有一些科技在里面bitset+二进制优化具体分析可以参考https://codeforces.com/blog/entry/98663简而言之就是可以通过\(O(\frac{C\sqrtC}{w})\)的复杂度判断是否能够获得某种体积开不同大小bitsettemplate......
  • 浙江大学利用 SVM 优化触觉传感器，盲文识别率达 96.12%
    生物传感是人类与机器、人类与环境、机器与环境交互的重要媒介。其中，触觉能够实现精准的环境感知，帮助使用者与复杂环境交互。为模仿人类的触觉，科研人员开发了各种传感器，以模拟皮肤对环境的感知。然而，触觉传感的要求高、参数变化多样，需要大量的研发经验、充分的文献调研和大量的试错......
  • matlab程序性能优化与混合编程技术介绍
    matlab程序代码优化，性能优化 Matlab是一种强大的计算工具，方便的矩阵运算与工具箱为编程人员提供了极大的便利。但是其性能的缺失使得处理一些大计算量问题时显得效率不高，matlab程序的优化应从几个方面展开：1.矩阵提前分配空间，矩阵第一次使用之后避免改变矩阵的维数。2.尽量使用矩......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99