15.1 选择排序
class Solution {public:void swap(int& a,int &b){int temp=a;a=b;b=temp;}vector<int> sortArray(vector<int>& nums) {int n=nums.size();for(int i=0;i<n-1;i++){//找最小的元素int min=i;for(int j=i+1;j<n;j++){if(nums[j]<nums[min]){min=j;}}//交换swap(nums[min],nums[i]);}return nums;}};
15.2 插入排序
超时，适合数据量小或部分有序数据
class Solution {public:vector<int> sortArray(vector<int>& nums) {if(nums.size()<2){return nums;}int n=nums.size();for(int i=1;i<n;i++){int temp=nums[i];//从后到前扫描已排好序的集合，找到合适位置为k+1int k=i-1;while(k>=0&&nums[k]>temp){k--;}//腾出位置，从k之后全部后移一位,直到ifor(int j=i;j>k+1;j--){nums[j]=nums[j-1];}nums[k+1]=temp;}return nums;}};
15.3 冒泡排序
class Solution {public:void swap(int& a,int& b){int t=a;a=b;b=t;}vector<int> sortArray(vector<int>& nums) {if(nums.size()<2){return nums;}int n=nums.size();//比较n-1轮for(int i=0;i<n-1;i++){//第i+1趟时比较n-1-i次,从头开始比较for(int j=0;j<n-i-1;j++){if(nums[j+1]<nums[j]){swap(nums[j+1],nums[j]);}}}return nums;}};
15.4 希尔排序
class Solution {public:vector<int> sortArray(vector<int>& nums) {if(nums.size()<2){return nums;}int n=nums.size();// 对每组间隔为 gap 的分组进行排序，刚开始 gap = n / 2;for(int gap=n/2;gap>0;gap/=2){//对每个局部分组进行插入排序//轮流对每个组进行插入排序,并不是先对一个组排序完了再来对另一个组排序for(int i=gap;i<n;i++){insertSort(nums,gap,i);}}return nums;}//gap为增量//arr[i]] 所在的分组为 ... arr[i-2*gap],arr[i-gap], arr[i+gap] ...void insertSort(vector<int>& nums,int gap,int i){int temp=nums[i];int k;//从后往前扫描，找到合适位置插入for(k=i-gap;k>=0&&temp<nums[k];k-=gap){nums[k+gap]=nums[k];}nums[k+gap]=temp;}};
15.5 合并排序
class Solution {public:vector<int> sortArray(vector<int>& nums) {if(nums.size()<2){return nums;}int n=nums.size();mergeSort(nums,0,n-1);return nums;}//递归，终止条件，只有一个元素时left==rightvoid mergeSort(vector<int>& nums,int left,int right){if(left<right){//分成两部分int mid=left+(right-left)/2;mergeSort(nums,left,mid);mergeSort(nums,mid+1,right);//合并两个有序队列merge(nums,left,mid,right);}}void merge(vector<int>& nums,int left,int mid,int right){//从两个有序数组中分别取数比较大小，结果放到辅助数组中。int i=left,j=mid+1,k=0;vector<int> temp(nums.size());while(i<=mid&&j<=right){if(nums[i]<=nums[j]){temp[k++]=nums[i++];}else{temp[k++]=nums[j++];}}while(i<=mid){temp[k++]=nums[i++];}while(j<=right){temp[k++]=nums[j++];}//复制到原数组for(int i=0;i<k;i++){nums[left++]=temp[i];}}};
//非递归
vector<int> mergeSort(vector<int>& nums){
int n=nums.size();
// 子数组的大小分别为1，2，4，8...
// 刚开始合并的数组大小是1，接着是2，接着4....
for(int i=1;i<n;i+=i){
int left=0;
int mid=left+i-1;
int right=mid+i;
while(right<n){
merge(nums,left,mid,right);
left=right+1;
mid=left+i-1;
right=mid+i;
}
// 还有一些被遗漏的数组没合并，千万别忘了
// 因为不可能每个字数组的大小都刚好为 i
if(left<n&&mid<n){
merge(nums,left,mid,n-1);
}
}
return nums;
}
15.6 快速排序
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
if(nums.size()<2){
return nums;
}
quickSort(nums,0,nums.size()-1);
return nums;
}
void quickSort(vector<int>& nums,int left,int right){
if(left<right){
//获取中轴元素的位置
int mid=partition(nums,left,right);
quickSort(nums,left,mid-1);
quickSort(nums,mid+1,right);
}
}
int partition(vector<int>& nums,int left,int right){
int pivot=nums[left];
int i=left+1,j=right;
while(1){
//i从前往后找，j从后往前找
while(i<=j&&nums[i]<=pivot) i++;
while(i<=j&&nums[j]>=pivot) j--;
//i==j退出
if(i>=j) break;
//交换i j元素
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
//交换有序的位置nums[j]和中轴元素nums[left]
nums[left]=nums[j];
nums[j]=pivot;
return j;
}
};
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
srand(time(0));
if(nums.size()<2) return nums;
quickSort(nums,0,nums.size()-1);
return nums;
}
void quickSort(vector<int>& nums,int left,int right){
if(left<right){
int mid=partition(nums,left,right);
quickSort(nums,left,mid-1);
quickSort(nums,mid+1,right);
}
}
int partition(vector<int>& nums,int left,int right){
int a=rand()%(right-left+1)+left;
swap(nums[a],nums[left]);
int priot=nums[left];
int i=left+1,j=right;
while(1){
while(i<=j && nums[i]<=priot) i++;
while(i<=j && nums[j]>=priot) j--;
if(i>=j) break;
swap(nums[i],nums[j]);
}
nums[left]=nums[j];
nums[j]=priot;
return j;
}
};
15.7 堆排序
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
if(nums.size()<2){
return nums;
}
heapSort(nums);
return nums;
}
vector<int> heapSort(vector<int>& nums){
//构建大顶堆
int n=nums.size();
//对所有非叶子节点进行下沉
for(int i=(n-2)/2;i>=0;i--){
downAdjust(nums,i,n-1);
}
//堆排序：堆顶元素为最小的元素，取出保存起来，为节约空间，直接保存在堆的末尾
//即：交换堆顶与末尾元素
for(int i=n-1;i>=1;i--){
int temp=nums[i];
nums[i]=nums[0];
nums[0]=temp;
//交换后调整剩余的堆
downAdgust(nums,0,i-1);
}
return nums;
}
//下沉
void downAdjust(vector<int>& nums,int parent,int length){
//左孩子
int child=parent*2+1;
//临时保存要下沉的元素用于后续比较
int temp=nums[parent];
while(child<=length){
//左右孩子中更小的一个与父交换
if(child+1<=length && nums[child]<nums[child+1]){
child++;
}
if(temp>=nums[child]){
break;
}
//交换
nums[parent]=nums[child];
//下沉后下标改变
parent=child;
child=2*parent+1;
}
//已经下沉，赋值
nums[parent]=temp;
}
};
15.8 计数排序
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
if(nums.size()<2){
return nums;
}
//优化做法：根据最大最小值之差来确定临时数组大小
int m_max=nums[0];
int m_min=nums[0];
int n=nums.size();
for(int i=1;i<n;i++){
if(m_max<nums[i]){
m_max=nums[i];
}
if(m_min>nums[i]){
m_min=nums[i];
}
}
//创建临时数组
int d=m_max-m_min+1;
vector<int> temp(d);
//统计每个元素出现的次数
for(int i=0;i<n;i++){
temp[nums[i]-m_min]++;
}
//根据临时数组汇总到原数组
int k=0;
for(int i=0;i<d;i++){
for(int j=temp[i];j>0;j--){
nums[k++]=i+m_min;
}
}
return nums;
}
};
15.9 桶排序
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
if(nums.size()<2){
return nums;
}
int m_max=nums[0];
int m_min=nums[0];
int n=nums.size();
for(int i=1;i<n;i++){
if(m_max<nums[i]){
m_max=nums[i];
}
if(m_min>nums[i]){
m_min=nums[i];
}
}
int d=m_max-m_min;
//初始化桶,创建 d / 5 + 1 个桶，第 i 桶存放 5*i ~ 5*i+5-1范围的数
int bucketNum=d/5+1;
//gap为5，或者当bucketNum为时，gap为 (m_max-m_min)/(bucketNum-1),序号为(num[i]-m_min)/d
vector<list<int>> bucketList(bucketNum);
for(int i=0;i<n;i++){
//计算bucket序号
int num=(double)(nums[i]-m_min)/5;
//将元素装入对应桶中
bucketList[num].push_back(nums[i]-m_min);
}
//每个桶中进行排序
for(int i=0;i<bucketNum;i++){
bucketList[i].sort();
}
//放回原数组
int k=0;
for(int i=0;i<bucketNum;i++){
for(auto& b:bucketList[i] ){
nums[k++]=b+m_min;
}
}
return nums;
}
};
15.10 基数排序
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
if(nums.size()<2){
return nums;
}
int n=nums.size();
//计算需要几轮，找最大元素，看其是几位数
int num=nums[0];
int m_max=0;
for(int i=0;i<n;i++){
m_max=max(m_max,nums[i]);
}
while(m_max/10>0){
num++;
m_max=m_max/10;
}
vector<list<int>> bucketList(10);
//每一轮,进行每一趟的排序，从个位数开始
for(int m=0;m<num;m++){
for(int i=0;i<n;i++){
int temp=nums[i];
//求个位数、十位数、百位数
for(int j=0;j<m;j++){
temp/=10;
}
//temp%10为桶序号，放到对应桶中
bucketList[temp%10].push_back(nums[i]);
}
//放回原数组
int k=0;
for(int j=0;j<10;j++){
for(auto& b:bucketList[j] ){
nums[k++]=b;
}
//取出后把桶清空
bucketList[j].clear();
}
}
return nums;
}
};
若有收获，就点个赞吧
0 人点赞
