常见排序算法（C++）

评判一个排序算法时除了时间复杂度和空间复杂度之外还要考虑对cache的捕获效果如何，cache友好的排序算法应该对数据的访问相对集中，快速排序相较于堆排序优点就是在于对cache的捕获效果好。

堆排序
时间复杂度：O（n log n ）
空间复杂度 O（1） 不稳定
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);}
}

快速排序
时间复杂度O（n log n）- O(n^2)
空间复杂度 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];//这里选值可以优化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);
}

归并排序
时间复杂度 O（n log n）
空间复杂度 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];
}

选择排序
时间复杂度 O（n^2）
空间复杂度 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]);}
}

插入排序
时间复杂度 O（n^2）
空间复杂度 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;}
}

冒泡排序
时间复杂度 O（n^2）
空间复杂度 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;}
}