十大经典排序算法整理汇总（附代码）

classSolution {
public:   
vector<int>sortArray(vector<int>&nums) { 
returnquickSort(nums);    }
// 冒泡排序（超时）vector<int>bubbleSort(vector<int>&nums) {  
intn=nums.size();    
for (inti=0; i<n; ++i) {   
for (intj=n-2; j>=i; --j) {  
if (nums[j] >nums[j+1]) {   
swap(nums[j], nums[j+1]); 
                }      
            }      
        }    
returnnums; 
    }
// 选择排序（超时）vector<int>selectSort(vector<int>&nums) {  
intn=nums.size();   
for (inti=0; i<n; ++i) {
intidx=i;     
for (intj=i; j<n; ++j) {  
if (nums[j] <nums[idx]) {  
idx=j;      
                }         
            }      
swap(nums[i], nums[idx]); 
        }     
returnnums;   
    }
// 插入排序（超时）  vector<int>insertSort(vector<int>&nums) {    
intn=nums.size();  
for (inti=0; i<n; ++i) {   
for (intj=i; j>0&&nums[j] <nums[j-1]; --j) { 
swap(nums[j], nums[j-1]);
        }     
    }    
returnnums; 
}
// 快速排序（24 ms） voidqSort(vector<int>&nums, intl, intr) {   
if (l>=r) return;   
intm=l; 
for (inti=l; i<r; ++i) {   
if (nums[i] <nums[r]) {  
swap(nums[m++], nums[i]); 
            }     
        }    
swap(nums[m], nums[r]); 
qSort(nums, l, m-1);  
qSort(nums, m+1, r);  
    }
vector<int>quickSort(vector<int>&nums) { 
intn=nums.size();   
qSort(nums, 0, n-1);   
returnnums;  
    }
// 归并排序（192 ms）vector<int>mSort(vector<int>&nums, intl, intr) {  
if (l>=r) return {nums[l]}; 
intm=l+(r-l)/2;   
vector<int>lnums=mSort(nums, l, m); 
vector<int>rnums=mSort(nums, m+1, r); 
vector<int>res;    
inti=0, j=0;  
while (i<=m-l&&j<=r-m-1) {    
if (lnums[i] <rnums[j]) {   
res.push_back(lnums[i++]); 
            } else {      
res.push_back(rnums[j++]);
            }     
        }      
while (i<=m-l) {  
res.push_back(lnums[i++]); 
        }       
while (j<=r-m-1) {   
res.push_back(rnums[j++]);  
        }      
returnres;    }
vector<int>mergeSort(vector<int>&nums) {   
intn=nums.size(); 
nums=mSort(nums, 0, n-1);
returnnums; 
    }
// 归并排序 + 非递归（80 ms）vector<int>mergeSortNR(vector<int>&nums) {  
intn=nums.size();     
for (intlen=1; len<n; len<<=1) {      
for (intl=0; l<n-len; l+=2*len) {  
intm=l+len-1;   
intr=min(n-1, l+2*len-1);
vector<int>res;  
inti=l, j=m+1; 
while (i<=m&&j<=r) {    
if (nums[i] <nums[j]) { 
res.push_back(nums[i++]);   
                    } else {       
res.push_back(nums[j++]); 
                    }    
                }       
while (i<=m) {  
res.push_back(nums[i++]);   
                }         
while (j<=r) {  
res.push_back(nums[j++]); 
                }         
for (inti=l; i<=r; ++i) {   
nums[i] =res[i-l];  
                }         
            }       
        }    
returnnums;
    }
// 希尔排序（40 ms）vector<int>shellSort(vector<int>&nums) {  
intn=nums.size();   
for (intgap=n/2; gap>0; gap/=2) {      
for (inti=gap; i<n; ++i) {   
for (intj=i; j-gap>=0&&nums[j-gap] >nums[j]; j-=gap) {    
swap(nums[j-gap], nums[j]); 
                }         
            }      
        }    
returnnums; 
    }
// 计数排序（32 ms） vector<int>countSort(vector<int>&nums) {     
intn=nums.size();      
if (!n) return {};    
intminv=*min_element(nums.begin(), nums.end());  
intmaxv=*max_element(nums.begin(), nums.end()); 
intm=maxv-minv+1;     
vector<int>count(m, 0);  
for (inti=0; i<n; ++i) {    
count[nums[i]-minv]++;    
        }
vector<int>res; 
for (inti=0; i<m; ++i) {   
for (intj=0; j<count[i]; ++j) {  
res.push_back(i+minv);   
            }      
        }      
returnres;    }
// 基数排序（不适用于负数） vector<int>radixSort(vector<int>&nums) {  
intn=nums.size();    
intmaxv=*max_element(nums.begin(), nums.end()); 
intmaxd=0;  
while (maxv>0) {  
maxv/=10;     
maxd++;      
        }       
vector<int>count(10, 0), rank(n, 0);  
intbase=1;    
while (maxd>0) {     
count.assign(10, 0);    
for (inti=0; i<n; ++i) {    
count[(nums[i]/base)%10]++;  
            }         
for (inti=1; i<10; ++i) {     
count[i] +=count[i-1];   
            }           
for (inti=n-1; i>=0; --i) {    
rank[--count[(nums[i]/base)%10]] =nums[i];            }          
for (inti=0; i<n; ++i) {       
nums[i] =rank[i]; 
            }          
maxd--;       
base*=10;     
        }     
returnnums;  
    }
// 桶排序 (20 ms) vector<int>bucketSort(vector<int>&nums) {     
intn=nums.size();   
intmaxv=*max_element(nums.begin(), nums.end());  
intminv=*min_element(nums.begin(), nums.end());     
intbs=1000;    
intm= (maxv-minv)/bs+1;  
vector<vector<int>>bucket(m);  
for (inti=0; i<n; ++i) {  
bucket[(nums[i]-minv)/bs].push_back(nums[i]);  
        }    
intidx=0;    
for (inti=0; i<m; ++i) {   
intsz=bucket[i].size();  
bucket[i] =quickSort(bucket[i]);   
for (intj=0; j<sz; ++j) {   
nums[idx++] =bucket[i][j];  
            }   
        }    
returnnums;   
    }
// 堆排序（32 ms）  voidadjust(vector<int>&nums, intp, ints) {   
while (2*p+1<s) {      
intc1=2*p+1;   
intc2=2*p+2;   
intc= (c2<s&&nums[c2]>nums[c1]) ?c2 : c1;  
if (nums[c] >nums[p]) swap(nums[c], nums[p]);    
elsebreak;      
p=c;     
        }   
    }
vector<int>heapSort(vector<int>&nums) {    
intn=nums.size(); 
for (inti=n/2-1; i>=0; --i) {     
adjust(nums, i, n);    
        }       
for (inti=n-1; i>0; --i) { 
swap(nums[0], nums[i]);   
adjust(nums, 0, i); 
        }    
returnnums;  
    }
};