排序算法一览

总览

排序算法	时间复杂度	空间复杂度	稳定性	原地排序？
冒泡排序	$O(n^2)$	$O(1)$	稳定	是
选择排序	$O(n^2)$	$O(1)$	不稳定	是
插入排序	$O(n^2)$	$O(1)$	稳定	是
希尔排序	$O(nlogn)$	$O(1)$	不稳定	是
快速排序	$O(nlogn)$	$O(logn)$	不稳定	是
归并排序	$O(nlogn)$	$O(n)$	稳定	否
基数排序	$O (d*(n+r))$	$O(n+r)$	稳定	否
堆排序	O(nlogn)	O(1)	不稳定	是

冒泡排序

/**
 * @brief 冒泡排序
 * 时间复杂度 O(n^2)
 * 空间复杂度 O(1)
 * 原地排序 稳定
 * 
 * @param nums 
 */
void bubbleSort(vector<int>& nums){
    int n=nums.size();
    for(int i=0;i<n-1;++i){
        for(int j=0;j<n-i-1;++j){
            if(nums[j]>nums[j+1]){
                int t=nums[j];
                nums[j]=nums[j+1];
                nums[j+1]=t;
            }
        }
    }
}
/*优化*/
void bubbleSort(vector<int>& nums){
    int n=nums.size();
    for(int i=0;i<n-1;++i){
        int flag=1;                //标记位，为1表示已经有序，为0表示尚未有序
        for(int j=0;j<n-i-1;++j){
            if(nums[j]>nums[j+1]){
                int t=nums[j];
                nums[j]=nums[j+1];
                nums[j+1]=t;
                flag=0;
            }
        }
        if(flag) break;
    }
}

选择排序

/**
 * @brief 选择排序
 * 时间复杂度 O(n^2)
 * 空间复杂度 O(1)
 * 原地排序 不稳定（会将重复的后面的较小值交换到前面来）
 * @param nums 
 */
void selectSort(vector<int>& nums){
    int n=nums.size();
    for(int i=0;i<n-1;++i){
        int mini=i;
        for(int j=i+1;j<n;++j){
            if(nums[mini]>nums[j]){
                mini=j;
            }
        }
        if(mini!=i){
            int t=nums[mini];
            nums[mini]=nums[i];
            nums[i]=t;
        }
    }
}

插入排序

/**
 * @brief 插入排序
 * 时间复杂度 O(n^2)
 * 空间复杂度 O(1);
 * 原地排序 稳定
 * 
 * @param nums 
 */
void insertSort(vector<int>& nums){
    int n=nums.size();
    for(int i=1;i<n;++i){
        if(nums[i]<nums[i-1]){
            int temp=nums[i];
            int j;
            for(j=i;nums[j-1]>temp&&j>0;--j){
                nums[j]=nums[j-1];
            }
            nums[j]=temp;
        }
    }
}

希尔排序

/**
 * @brief 希尔排序
 *时间复杂度  O(nlogn) 最坏 O(n^s)
 *空间复杂度 O(1)
 *原地排序 不稳定
 * @param nums 
 */
void sheelSort(vector<int> &nums){
    int n=nums.size();
    int gap=1,i,j;
    while(gap<n/3){
        gap=3*gap+1;
    }
    while(gap>=1){
        for(i=gap;i<n;i++){
            if(nums[i]<nums[i-gap]){
                int temp=nums[i];
                for( j=i-gap;j>=0&&nums[j]>temp;j-=gap){
                    nums[j+gap]=nums[j];
                }
                nums[j+gap]=temp;
            }
        }
        gap=gap/3;

    }
}

快速排序

/**
 * @brief 快速排序
 * 时间复杂度 O(nlogn); 最坏O(n^2)
 * 空间复杂度 O(logn)
 * 原地排序，不稳定
 */
void quickSort(vector<int>& nums,int left,int right){
    if(left>=right){
        return;
    }
    int temp=nums[left];
    int i=left,j=right;
    while(i!=j){
        while(nums[j]>=temp&&i<j){
            --j;
        }
        while(nums[i]<=temp&&i<j){ //i及左侧必然小于等于temp
            ++i;
        }
        if(i<j){
            int t=nums[i];
            nums[i]=nums[j];
            nums[j]=t;
        }
    }
    nums[left]=nums[i];
    nums[i]=temp;
    quickSort(nums,left,i-1);
    quickSort(nums,i+1,right);
}

void quickSortP(vector<int>& nums,int left,int right){
    if(left>=right){
        return;
    }
    int temp=nums[left];
    int i=left,j=right;
    while(i<j){
        while(nums[j]>=temp&&i<j){
            --j;
        }
        while(nums[i]<=temp&&i<j){ //i及左侧必然小于等于temp
            ++i;
        }
        if(i<j){
            int t=nums[i];
            nums[i]=nums[j];
            nums[j]=t;
        }
    }
    nums[left]=nums[i];
    nums[i]=temp;
    quickSortP(nums,left,i-1);
    quickSortP(nums,i+1,right);
}

归并排序

/**
 * @brief 归并排序
 * 时间复杂度 O(nlogn)
 * 空间复杂度 O(n)
 * 非原地排序 稳定
 * 
 * @param nums 
 */
//递归计算
void mergeSort(vector<int>& nums,int left,int right){
    if(left>=right){
        return;
    }
    int mid=(left+right)/2;
    mergeSort(nums,left,mid);
    mergeSort(nums,mid+1,right);

    vector<int> temp(right-left+1);
    int i=left,j=mid+1,k=0;
    while(i<=mid||j<=right){
        if(i>mid){
            temp[k++]=nums[j++];
        }
        else if(j>right){
            temp[k++]=nums[i++];
        }
        else{
            if(nums[i]<=nums[j]){
                temp[k++]=nums[i++];
            }
            else{
                temp[k++]=nums[j++];
            }
        }
    }
    for(int t=0;t<temp.size();++t){
        nums[left+t]=temp[t];
    }
}
//迭代计算
void mergeSortD(vector<int>& nums){
    int n=nums.size();
    int left,right;
    vector<int> temp(n,0);
    for(int i=2;i<n;i*=2){
        for(left=0;left<n-i;left+=i){
            right=left+i-1;
            if(right>=n) right=n-1;
            int mid=(left+right)/2;
            int l=left,r=mid+1,k=0;
            while(l<=mid||r<=right){
                if(l>mid){
                    temp[k++]=nums[r++];
                }
                else if(r>right){
                    temp[k++]=nums[l++];
                }
                else{
                    if(nums[l]<=nums[r]){
                        temp[k++]=nums[l++];
                    }
                    else{
                        temp[k++]=nums[r++];
                    }
                }
            }
            for(k=0;k<right-left+1;++k){
                nums[left+k]=temp[k];
            }
        }
    }
    return;
}

基数排序

/**
 * @brief 基数排序
 * 
 */
void lsdSort(vector<int>& nums){
    int n=nums.size();
    int digit=0;
    for(int i=0;i<n;++i){
        while(nums[i]>(pow(10,digit))){
            digit++;
        }
    }
    int flag=1;
    for(int j=1;j<=digit;++j){
        vector<int> count(10);
        for(int i=0;i<n;++i){
           count[(nums[i]/flag)%10]++;
        }
        vector<int> index(10);
        for(int i=1;i<10;++i){
            index[i]=index[i-1]+count[i-1];
        }

        vector<int> temp(n);
        for(int i=0;i<n;++i){
            int begin=(nums[i]/flag)%10;
            temp[index[begin]++]=nums[i];
        }
        for(int i=0;i<n;++i){
            nums[i]=temp[i];
        }
        flag*=10;
    }
}

堆排序

/**
 * @brief 堆排序
 * 
 * @param s 
 * @param nums 
 */
void heapSort(vector<int> &nums){
    int n=nums.size();
    auto swap=[](int &a,int &b){
        int t=a;
        a=b;
        b=t;
    };
    auto sink=[&](int s,int len){
        int temp=nums[s-1];
        for(int i=2*s;i<=len;i*=2){
            if(i<len&&nums[i-1]<nums[i]){
                i++;
            }
            if(temp>=nums[i-1]){
                break;
            }
            nums[s-1]=nums[i-1];
            s=i;
        }
        nums[s-1]=temp;
    };
    for(int i=n/2;i>0;i--){ //从下向上，从右向左调整
        sink(i,n);
    }
    for(int i=n;i>1;--i){
        swap(nums[0],nums[i-1]);
        sink(1,i-1);  
    }
}