基础版 快排:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<sstream>
#include<map>
#include<set>
#include<vector>
#include<unordered_map>
#include<time.h>
#include<stdint.h>
#include<queue>
#include<unordered_set>
#include<stack>
using namespace std;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f;
void quick_sort_v1(int *arr,int l,int r){
if(l=r){
int x =l,y=r,base = arr[l];
while(x<y){
while(x<y&&arr[y]>=base)y--;
if(x<y)arr[x++] = arr[y];
while(x<y&&arr[x]<base)x++;
if(x<y)arr[y--] = arr[x];
}
arr[x]= base;
quick_sort_v1(arr,l,x-1);
quick_sort_v1(arr,x+1,r);
return ;
}
}
int main(){
int arr[10] = {3,1,4,5,9,10};
quick_sort_v1(arr,0,6);
for(int i=0;i<7;i++){
cout<<arr[i]<<"";
}
cout<<endl;
return 0;
}
快速排序时间复杂度根据选定的基准值来决定
o(logn) ~ o(nlogn) ~ o(n^2) ;
堆排序(稳定时间复杂度)o(nlogn)
当数组趋于有序时,通过使用插入排序尽量减少时间复杂度 最快o(n) 一般o(n^2)
所以logn时使用快速排序当快速排序阈值超过2logn时使用堆排序,当数据量比较小或者趋于有序的时候使用插入排序。
C++STL中sort跳过了快速排序、插入排序、堆排序缺点
STL中__introsort_loop(__first,__last,__VALUE_TYPE(__first),__lg(__last - __first)*2);//混合排序:快速排序+堆排序
__final_insertion_sort(__first,__last);//插入排序
升级版:
void quick_sort_v2(int *arr,int l,int r){//排序左递归法
while(l<r){
int x = l,y =r,base = arr[l];
while(x<y){
while(x<y&&arr[y]>=base)y--;
if(x<y)arr[x++]=arr[y];
while(x<y&&arr[x]<base)x++;
if(x<y)arr[y--]=arr[x];
}
arr[x] = base;
quick_sort_v2(arr,x+1,r);
r = x-1;
}
return ;
}
STL排序:
const int threshold = 16;
inline int getmid(int a,int b,int c){
if(a>b)swap(a,b);
if(a>c)swap(a,c);
if(b>c)swap(b,c);
return b;
}
void __quick_sort_v3(int *arr,int l,int r){
while(r-l>threshold){
int x=l,y=r,base=getmid(arr[l],arr[(l+r)/2],arr[r]);
do{
while(arr[x]<base)x++;
while(arr[y]>base)y--;
if(x<=y){
swap(arr[x],arr[y]);
x++,y--;
}
}while(x<=y);
__quick_sort_v3(arr,x,r);
r=y;
}
return ;
}
//无监督插入排序
void final_insert_sort(int *arr,int l,int r){
int ind = l;
for(int i=l+1;i<=r;i++){
if(arr[i]<arr[ind])ind = i;
}
while(ind>l){
swap(arr[ind],arr[ind-1]);
ind--;
}
for(int i =l+2;i<=r;i++){
int j =i;
while(arr[j]<arr[j-1]){
swap(arr[j],arr[j-1]);
j--;
}
}
return ;
}
void quick_sort_v3(int *arr,int l,int r){
__quick_sort_v3(arr,l,r);
final_insert_sort(arr,l,r);
}
例题:
leetcode912
剑指offer21.调整数组顺序使奇数位于偶数前面
148.排序链表
class Solution {
public:
//链表排序最好的方式是归并排序
//这里使用快排:思路
//找到一个partition将链表分成两份(一份大于,一分小于),分别再对每部分进行快排
ListNode* sortList(ListNode* head) {
if(head==NULL) return head;
//这里平均值最为partation
int l=head->val,r=head->val;
double mid;
ListNode *p =head,*q,*h1=NULL,*h2=NULL;
//遍历链表找到最小值与最大值
while(p){
l=min(p->val,l);
r=max(p->val,r);
p=p->next;
}
//优化
if(l==r) return head;
mid=(l+r)/2.0;
p = head;
while(p){
q = p->next;//需要对p指向的变换但是不能直接操作这个p就会使得这个链表丢失。
if(p->val<=mid){
p->next = h1;
h1=p;
}else{
p->next =h2;
h2=p;
}
p=q;
}//上面实现小的放h1,大的放h2;
h1=sortList(h1);
h2=sortList(h2);
p=h1;
while(p->next) p = p->next;
p->next = h2;
return h1;
}
};
75.颜色分类
class Solution {
public:
//三路快排
void three_partition(vector<int>&arr,int l,int r,int mid){
if(l>=r) return ;
int x =-1,y = r+1,i =l;
while(i<y){
if(arr[i] == mid) i++;
else if(arr[i]<mid){
x++;
swap(arr[x],arr[i]);
i++;
}else if(arr[i]>mid){
y--;
swap(arr[y],arr[i]);
}
}
}
void sortColors(vector<int>& arr) {
three_partition(arr,0,arr.size()-1,1);
return ;
}
};
面试题 17.14. 最小K个数
class Solution {
public:
int getmid(int a,int b,int c){
if(a>b)swap(a,b);
if(a>c)swap(a,c);
if(b>c)swap(b,c);
return b;
}
void quick_select(vector<int>&arr,int l,int r,int k){
if(l>=r) return ;
int x= l,y=r,mid = getmid(arr[l],arr[(l+r)/2],arr[r]);
do{
while(arr[x]<mid) x++;
while(arr[y]>mid) y--;
if(x<=y){
swap(arr[x],arr[y]);
x++,y--;
}
}while(x<=y);//上面标准快排
if(y-l == k-1)return ;//当左区间数量等于k,直接返回。
if(y-l>=k){//左区间数量大于k,继续扩大
quick_select(arr,l,y,k);
}else{//左区间小于k就要增加k-x+l个元素
quick_select(arr,x,r,k-(x-l));
}
return ;
}
vector<int> smallestK(vector<int>& arr, int k) {
vector<int>ans;
if(k==0)return ans;
quick_select(arr,0,arr.size()-1,k);
while(k) ans.push_back(arr[--k]);
return ans;
}
};
- 不同的二叉搜索树 II
class Solution {
public:
vector<TreeNode*>dfs(int l,int r){
vector<TreeNode*>ans;
if(l>r){
ans.push_back(nullptr);
return ans;
}
for(int i=l;i<=r;i++){
//把i作为根结点看左右结点的递归
vector<TreeNode*> left_tree =dfs(l,i-1);
vector<TreeNode*> right_tree = dfs(i+1,r);
//排列组合 eg i=3
for(TreeNode* left:left_tree){//遍历left_tree{1,null,2}{2,1,null}
for(TreeNode* right:right_tree){//{4}
TreeNode* t = new TreeNode(i,left,right);
ans.push_back(t);
}
}
}
return ans;
}
vector<TreeNode*> generateTrees(int n) {
vector<TreeNode*> ans;
if(n==0) return ans;
return dfs(1,n);
}
};
- 字符串解码
class Solution {
public:
string decodeString(string s) {
string ret;
int i=0;
while(s[i]){
if(s[i]<'0'||s[i]>'9'){//如果s[i]不是一个数字
ret +=s[i];
i++;
}else{
int num = 0;
while(s[i]>='0'&&s[i]<='9'){
num = num*10+(s[i++]-'0');//将数字记录下来
}
i++;
int l=i,r=i,cnt=1;
while(cnt){
r+=1;
if(s[r] =='[')cnt++;
else if(s[r]==']') cnt--;
}
string tmp = decodeString(s.substr(l,r-l));
while(num--) ret+=tmp;
i=r+1;
}
}
return ret;
}
};
- 盛最多水的容器
class Solution {
public:
int maxArea(vector<int>& height) {
//双指针 ,i指向最左边,j指向最右边
int ans =0 ,i=0,j=height.size()-1;
//像求partation,不断求最大值
while(i<j){
ans = max(ans,(j-i)*min(height[i],height[j]));
if(height[i]<height[j])i++;
else j--;
}
return ans;
}
};
- 用 Rand7() 实现 Rand10()
剑指 Offer 59 - I. 滑动窗口的最大值
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> ans;
if(k==0) return ans;
//双端队列
deque<int> q;
int idx = 0;
while(idx<nums.size()){
if(!q.empty()&&q.front()+k<=idx){
q.pop_front();
}
while(!q.empty()&&nums[q.back()]<nums[idx]){
q.pop_back();
}
q.push_back(idx);
idx++;
if(idx>=k) ans.push_back(nums[q.front()]);
}
return ans;
}
};
写的内容可能存在漏洞 欢迎杂砖。