評(píng)判一個(gè)排序算法時(shí)除了時(shí)間復(fù)雜度和空間復(fù)雜度之外還要考慮對(duì)cache的捕獲效果如何，cache友好的排序算法應(yīng)該對(duì)數(shù)據(jù)的訪問(wèn)相對(duì)集中，快速排序相較于堆排序優(yōu)點(diǎn)就是在于對(duì)cache的捕獲效果好。

堆排序
時(shí)間復(fù)雜度：O（n log n ）
空間復(fù)雜度 O（1） 不穩(wěn)定
cache不友好

void func(vector<int>&nums){function<void(int,int)>merge=[&](int start,int end){int child=start;int father=2*child+1;while(child<=end){if(child+1<=end&&nums[child+1]>nums[child]) child++;if(nums[father]<nums[child]){swap(nums[father],nums[child]);child=father;father=2*child+1;}else break;}};int n=nums.size();for(int i=n/2-1;i>=0;i--){merge(i,n-1);}for(int i=n-1;i>=0;i--){swap(nums[0],nums[i]);merge(0,i-1);}
}

快速排序
時(shí)間復(fù)雜度O（n log n）- O(n^2)
空間復(fù)雜度 O（1）
cache友好

void func(vector<int>&nums,int start,int end){if(start>=end) return;int s=start-1;int e=end+1;int val=nums[start];//這里選值可以優(yōu)化int index=start;while(index<e){if(nums[index]==val) {index++;}else if(nums[index]<val){swap(nums[index],nums[++s]);index++;}else swap(nums[index],nums[--e]);}func(nums,start,s);func(nums,e,end);
}

歸并排序
時(shí)間復(fù)雜度 O（n log n）
空間復(fù)雜度 O（n）
cache友好

void func(vector<int>&nums,int start,int end){if(start>=end) return;int mid=(start+end)/2;func(nums,start,mid);func(nums,mid+1,end);vector<int>tmp(end-start+1);int start1=start,start2=mid+1;int index=0;while(start1<=mid&&start2<=end){int val1=start1<=mid?nums[start1]:INT_MAX;int val2=start2<=end?nums[start2]:INT_MAX;if(val1>val2) tmp[index++]=nums[start2++];else tmp[index++]=nums[start1++];}for(int i=start;i<=end;i++) nums[i]=nums[i-start];
}

選擇排序
時(shí)間復(fù)雜度 O（n^2）
空間復(fù)雜度 O（1）
cache不友好

void func(vector<int>&nums){int n=nums.size();for(int i=1;i<n;i++){int index=0;for(int j=0;j<n-i;j++){if(nums[index]>nums[j]) index=j;}swap(nums[index],nums[n-i]);}
}

插入排序
時(shí)間復(fù)雜度 O（n^2）
空間復(fù)雜度 O（1）
cache友好

void func(vector<int>&nums){int n=nums.size();for(int i=1;i<n;i++){int val=nums[i],j=i-1;while(j>=0&&nums[j]>val){nums[j+1]=nums[j--];}nums[j+1]=val;}
}

冒泡排序
時(shí)間復(fù)雜度 O（n^2）
空間復(fù)雜度 O（1）
cache不友好

void func(vector<int>&nums){int n=nums.size();for(int i=0;i<n;i++){bool b=true;for(int j=i+1;j<n;j++){if(nums[i]>nums[j]) {b=false;swap(nums[i],nums[j]);}}if(b) break;}
}