排序算法之快排与TIMSORT的比较测试，python-开发者社区

以下提供 Python、Go、C++ 三种语言的性能测试代码，统一测试两种算法在随机数据、部分有序数据、完全有序数据三种场景下的执行时间，数据规模覆盖 1k/10k/100k/1M 元素：

一、Python 性能测试代码

importtimeimportrandomfromtypingimportCallable,List# ---------------------- 待测试算法 ----------------------# 1. 之前的快排变种（原逻辑复现）definsertion_sort(arr:List[int])->List[int]:iflen(arr)<=1:returnarr.copy()arr_copy=arr.copy()n=len(arr_copy)foriinrange(1,n):key=arr_copy[i]j=i-1whilej>=0andarr_copy[j]>key:arr_copy[j+1]=arr_copy[j]j-=1arr_copy[j+1]=keyreturnarr_copydefquick_sort_simple(arr:List[int],threshold_ratio:float=1/16)->List[int]:iflen(arr)<=1:returnarr.copy()ratio=threshold_ratio threshold=max(1,int(len(arr)*ratio))def_sort(sub_arr:List[int])->List[int]:iflen(sub_arr)<=threshold:returninsertion_sort(sub_arr)pivot=sub_arr[len(sub_arr)//2]left=[xforxinsub_arrifx<pivot]middle=[xforxinsub_arrifx==pivot]right=[xforxinsub_arrifx>pivot]return_sort(left)+middle+_sort(right)return_sort(arr.copy())# 2. Timsort（前文实现）importbisectdeftimsort(arr:List[int])->List[int]:arr=arr.copy()n=len(arr)MIN_RUN=32definsertion_sort_sub(arr:List[int],left:int,right:int)->None:foriinrange(left+1,right+1):key=arr[i]j=i-1whilej>=leftandarr[j]>key:arr[j+1]=arr[j]j-=1arr[j+1]=keyforiinrange(0,n,MIN_RUN):end=min(i+MIN_RUN-1,n-1)insertion_sort_sub(arr,i,end)defmerge(a:List[int],b:List[int])->List[int]:res=[]i=j=0len_a,len_b=len(a),len(b)whilei<len_aandj<len_b:ifa[i]<=b[j]:k=bisect.bisect_right(a[i:],b[j])res.extend(a[i:i+k])i+=kelse:k=bisect.bisect_right(b[j:],a[i])res.extend(b[j:j+k])j+=k res.extend(a[i:])res.extend(b[j:])returnres size=MIN_RUNwhilesize<n:forleftinrange(0,n,2*size):mid=min(left+size-1,n-1)right=min(left+2*size-1,n-1)ifmid<right:merged=merge(arr[left:mid+1],arr[mid+1:right+1])arr[left:left+len(merged)]=merged size*=2returnarr# ---------------------- 性能测试工具 ----------------------defgenerate_test_data(size:int,data_type:str)->List[int]:"""生成测试数据：random/partial_sorted/sorted"""random.seed(42)# 固定种子保证可复现arr=list(range(size))ifdata_type=="random":random.shuffle(arr)elifdata_type=="partial_sorted":# 80%有序，20%随机打乱foriinrange(size//5):idx1,idx2=random.randint(0,size-1),random.randint(0,size-1)arr[idx1],arr[idx2]=arr[idx2],arr[idx1]returnarrdeftest_algorithm(func:Callable[[List[int]],List[int]],data:List[int],name:str)->float:"""测试算法执行时间，返回耗时（秒）"""start=time.perf_counter()func(data)end=time.perf_counter()耗时=end-startprint(f"{name:20}耗时:{耗时:.6f}秒")return耗时# ---------------------- 执行测试 ----------------------if__name__=="__main__":数据规模列表=[1000,10000,100000,1000000]数据类型列表=["random","partial_sorted","sorted"]算法列表=[("快排变种",quick_sort_simple),("Timsort",timsort)]for数据规模in数据规模列表:print(f"\n===== 数据规模:{数据规模}元素 =====")for数据类型in数据类型列表:print(f"\n【{数据类型}数据】")测试数据=generate_test_data(数据规模,数据类型)for算法名称,算法函数in算法列表:test_algorithm(算法函数,测试数据,算法名称)

二、Go 性能测试代码

packagemainimport("bufio""fmt""math/rand""os""sort""time")// ---------------------- 待测试算法 ----------------------// 1. 之前的快排变种（原逻辑复现）funcinsertionSort(arr[]int)[]int{iflen(arr)<=1{returnappend([]int(nil),arr...)}arrCopy:=append([]int(nil),arr...)n:=len(arrCopy)fori:=1;i<n;i++{key:=arrCopy[i]j:=i-1forj>=0&&arrCopy[j]>key{arrCopy[j+1]=arrCopy[j]j--}arrCopy[j+1]=key}returnarrCopy}funcQuickSortSimple(arr[]int)[]int{iflen(arr)<=1{returnappend([]int(nil),arr...)}ratio:=1.0/16.0threshold:=max(1,int(float64(len(arr))*ratio))var_sortfunc([]int)[]int_sort=func(subArr[]int)[]int{iflen(subArr)<=threshold{returninsertionSort(subArr)}pivot:=subArr[len(subArr)/2]varleft,middle,right[]intfor_,x:=rangesubArr{switch{casex<pivot:left=append(left,x)casex==pivot:middle=append(middle,x)default:right=append(right,x)}}returnappend(append(_sort(left),middle...),_sort(right)...)}return_sort(append([]int(nil),arr...))}funcmax(a,bint)int{ifa>b{returna}returnb}// 2. Timsort（前文实现）constminRun=32funcinsertionSortSub(arr[]int,left,rightint){fori:=left+1;i<=right;i++{key:=arr[i]j:=i-1forj>=left&&arr[j]>key{arr[j+1]=arr[j]j--}arr[j+1]=key}}funcmerge(a,b[]int)[]int{res:=make([]int,0,len(a)+len(b))i,j:=0,0lenA,lenB:=len(a),len(b)fori<lenA&&j<lenB{ifa[i]<=b[j]{k:=sort.Search(len(a)-i,func(idxint)bool{returna[i+idx]>b[j]})res=append(res,a[i:i+k]...)i+=k}else{k:=sort.Search(len(b)-j,func(idxint)bool{returnb[j+idx]>a[i]})res=append(res,b[j:j+k]...)j+=k}}res=append(res,a[i:]...)res=append(res,b[j:]...)returnres}funcTimsort(arr[]int)[]int{arrCopy:=make([]int,len(arr))copy(arrCopy,arr)n:=len(arrCopy)ifn<=minRun{insertionSortSub(arrCopy,0,n-1)returnarrCopy}fori:=0;i<n;i+=minRun{end:=i+minRun-1ifend>=n{end=n-1}insertionSortSub(arrCopy,i,end)}size:=minRunforsize<n{forleft:=0;left<n;left+=2*size{mid:=left+size-1right:=left+2*size-1ifmid>=n{break}ifright>=n{right=n-1}ifmid>=right{continue}merged:=merge(arrCopy[left:mid+1],arrCopy[mid+1:right+1])copy(arrCopy[left:left+len(merged)],merged)}size*=2}returnarrCopy}// ---------------------- 性能测试工具 ----------------------funcgenerateTestData(sizeint,dataTypestring)[]int{rand.Seed(42)arr:=make([]int,size)fori:=rangearr{arr[i]=i}switchdataType{case"random":rand.Shuffle(size,func(i,jint){arr[i],arr[j]=arr[j],arr[i]})case"partial_sorted":fori:=0;i<size/5;i++{idx1:=rand.Intn(size)idx2:=rand.Intn(size)arr[idx1],arr[idx2]=arr[idx2],arr[idx1]}}returnarr}functestAlgorithm(funcNamestring,ffunc([]int)[]int,data[]int)float64{start:=time.Now()f(data)elapsed:=time.Since(start).Seconds()fmt.Printf("%-20s 耗时: %.6f 秒\n",funcName,elapsed)returnelapsed}// ---------------------- 执行测试 ----------------------funcmain(){dataSizes:=[]int{1000,10000,100000,1000000}dataTypes:=[]string{"random","partial_sorted","sorted"}algorithms:=[]struct{namestringfnfunc([]int)[]int}{{"快排变种",QuickSortSimple},{"Timsort",Timsort},}for_,size:=rangedataSizes{fmt.Printf("\n===== 数据规模: %d 元素 =====\n",size)for_,dtype:=rangedataTypes{fmt.Printf("\n【%s 数据】\n",dtype)data:=generateTestData(size,dtype)for_,algo:=rangealgorithms{testAlgorithm(algo.name,algo.fn,data)}}}// 防止程序退出（可选）fmt.Println("\n测试完成，按回车退出...")bufio.NewReader(os.Stdin).ReadByte()}

三、C++ 性能测试代码

#include<vector>#include<algorithm>#include<iostream>#include<chrono>#include<random>#include<iomanip>usingnamespacestd;usingnamespacechrono;// ---------------------- 待测试算法 ----------------------// 1. 之前的快排变种（原逻辑复现）vector<int>insertionSort(vector<int>arr){if(arr.size()<=1)returnarr;intn=arr.size();for(inti=1;i<n;++i){intkey=arr[i];intj=i-1;while(j>=0&&arr[j]>key){arr[j+1]=arr[j];--j;}arr[j+1]=key;}returnarr;}vector<int>quickSortSimple(vector<int>arr,floatthresholdRatio=1.0/16.0){if(arr.size()<=1)returnarr;intthreshold=max(1,(int)(arr.size()*thresholdRatio));function<vector<int>(vector<int>)>_sort=[&](vector<int>subArr)->vector<int>{if(subArr.size()<=threshold){returninsertionSort(subArr);}intpivot=subArr[subArr.size()/2];vector<int>left,middle,right;for(intx:subArr){if(x<pivot)left.push_back(x);elseif(x==pivot)middle.push_back(x);elseright.push_back(x);}vector<int>res=_sort(left);res.insert(res.end(),middle.begin(),middle.end());vector<int>rightSorted=_sort(right);res.insert(res.end(),rightSorted.begin(),rightSorted.end());returnres;};return_sort(arr);}// 2. Timsort（前文实现）constexprintMIN_RUN=32;voidinsertionSortSub(vector<int>&arr,intleft,intright){for(inti=left+1;i<=right;++i){intkey=arr[i];intj=i-1;while(j>=left&&arr[j]>key){arr[j+1]=arr[j];--j;}arr[j+1]=key;}}vector<int>merge(vector<int>&a,vector<int>&b){vector<int>res;res.reserve(a.size()+b.size());inti=0,j=0;intlenA=a.size(),lenB=b.size();while(i<lenA&&j<lenB){if(a[i]<=b[j]){autoit=upper_bound(a.begin()+i,a.end(),b[j]);res.insert(res.end(),a.begin()+i,it);i=it-a.begin();}else{autoit=upper_bound(b.begin()+j,b.end(),a[i]);res.insert(res.end(),b.begin()+j,it);j=it-b.begin();}}res.insert(res.end(),a.begin()+i,a.end());res.insert(res.end(),b.begin()+j,b.end());returnres;}vector<int>timsort(vector<int>arr){intn=arr.size();if(n<=MIN_RUN){insertionSortSub(arr,0,n-1);returnarr;}for(inti=0;i<n;i+=MIN_RUN){intend=min(i+MIN_RUN-1,n-1);insertionSortSub(arr,i,end);}intsize=MIN_RUN;while(size<n){for(intleft=0;left<n;left+=2*size){intmid=left+size-1;intright=min(left+2*size-1,n-1);if(mid>=n)break;if(mid>=right)continue;vector<int>a(arr.begin()+left,arr.begin()+mid+1);vector<int>b(arr.begin()+mid+1,arr.begin()+right+1);vector<int>merged=merge(a,b);copy(merged.begin(),merged.end(),arr.begin()+left);}size*=2;}returnarr;}// ---------------------- 性能测试工具 ----------------------vector<int>generateTestData(intsize,conststring&dataType){vector<int>arr(size);iota(arr.begin(),arr.end(),0);// 生成0~size-1的有序数组mt19937rng(42);// 固定种子if(dataType=="random"){shuffle(arr.begin(),arr.end(),rng);}elseif(dataType=="partial_sorted"){// 80%有序，20%随机打乱for(inti=0;i<size/5;++i){uniform_int_distribution<>dist(0,size-1);intidx1=dist(rng);intidx2=dist(rng);swap(arr[idx1],arr[idx2]);}}returnarr;}doubletestAlgorithm(conststring&funcName,function<vector<int>(vector<int>)>func,constvector<int>&data){autostart=high_resolution_clock::now();func(data);autoend=high_resolution_clock::now();duration<double>elapsed=end-start;cout<<left<<setw(20)<<funcName<<" 耗时: "<<fixed<<setprecision(6)<<elapsed.count()<<" 秒"<<endl;returnelapsed.count();}// ---------------------- 执行测试 ----------------------intmain(){vector<int>dataSizes={1000,10000,100000,1000000};vector<string>dataTypes={"random","partial_sorted","sorted"};vector<pair<string,function<vector<int>(vector<int>)>>>algorithms={{"快排变种",quickSortSimple},{"Timsort",timsort}};for(intsize:dataSizes){cout<<"\n===== 数据规模: "<<size<<" 元素 ====="<<endl;for(conststring&dtype:dataTypes){cout<<"\n【"<<dtype<<" 数据】"<<endl;vector<int>data=generateTestData(size,dtype);for(auto&algo:algorithms){testAlgorithm(algo.first,algo.second,data);}}}return0;}