冒泡排序插入排序选择排序快速排序归并排序C++详细代码

冒泡排序

算法描述：比较相邻的元素，如果第一个比第二个大，就相互交换，对每一对相邻的元素做相同的工作，第一次排序使最大的元素移动到最右端；进行第二次排序，同样的步骤使次大的元素移动到n-1的位置上；重复上述步骤，直到排序完成。

时间复杂度：O(n^2)   (这里说的都是平均情况，待排序列近似有序时，冒泡排序的时间复杂度能达到O(n))

空间复杂度：O(1)

稳定性：稳定

class Solution {
public:
    vector BubbleSort(vector& arr) {   //冒泡排序
        int n = arr.size();
        for(int i=1; i arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        return arr;
    }
};

 

插入排序

算法描述：分为已排序和未排序两部分，初始已排序区间只有第一个元素，依次遍历未排序的每一个元素，并在已排序的区间里找到合适的位置（比左大比右小）插入。

时间复杂度：O(n^2)   (时间复杂度为O(n^2) 的方法里，插入排序最好,待排序列近似有序时，插入排序的时间复杂度能达到O(n))

空间复杂度：O(1)

稳定性：稳定

class Solution {
public:
    vector InsertSort(vector& arr) {     //插入排序
        int n = arr.size();
        for(int i = 1; i < n; ++i){
            for(int j = i; j > 0; --j){
                if(arr[j] < arr[j-1]){
                    int temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp; 
                }
            }
        }
        return arr;
    }
};

 

选择排序

 算法描述：分为已排序和未排序两部分，每次都会从未排序区间中找到最小的元素，并将其放到已排序区间的末尾。

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：不稳定

class Solution {
public:
    vector SelectSort(vector& arr) {   //选择排序
        int n = arr.size();
        for(int i = 0; i < n; ++i){
            int min = i;               //每次排序记录最小元素的下标
            for(int j = i + 1; j < n; ++j){      //寻找每次排序的最小元素
                if(arr[j] < arr[min]){
                    min = j;
                }
            }
            int temp = arr[i];         //将最小元素放到已排序区间的末尾
            arr[i] = arr[min];
            arr[min] = temp;
        }
        return arr;
    }
};

 

快速排序

算法描述：先找到一个枢纽（待排序区间的第一个元素），将待排序元素根据这个枢纽划分，比枢纽小的元素放枢纽前面，比枢纽大的元素放枢纽后面；对枢纽两边的序列用同样的方法依次递归的排序下去直到有序。

时间复杂度：O(nlogn)      (时间复杂度为O(nlogn) 的方法里，快速排序最好，但是待排序列近似有序时，快速排序的时间复杂度会退化至O(n^2))

空间复杂度： O(nlogn)

稳定性：不稳定

class Solution {
public:
    int oncesort(vector& nums, int left, int right){ //每次排序
        int temp = nums[left];       //枢纽
        while(left < right){
            while(left < right && nums[right] >= temp) {  //比枢纽大的元素放右边（因为枢纽 
                                                     选的是最左边的元素，所以一定要先右再左）
                --right;
            }
            nums[left] = nums[right];
            while(left < right && nums[left] <=temp){     //比枢纽小的元素放左边
                ++left;
            }
            nums[right] = nums[left];
        }
        nums[left] = temp;         //将枢纽放在中间空缺的位置上
        return left;               //返回枢纽的下标
    }
    
    void quicksort(vector& nums, int left, int right){    //快速排序
        if(left < right){
            int mid = oncesort(nums, left, right);    //枢纽下标
            quicksort(nums, left, mid - 1);           //以枢纽为中间点，左右两区间递归排序
            quicksort(nums, mid + 1, right);
        }
    }
    
    vector MySort(vector& arr) {       //主函数
        quicksort(arr, 0, arr.size()-1);
        return arr;
    }
};

 

归并排序

算法描述：假设待排序列有n 个元素，可将其拆分成n个长度为1的子序列，然后两两归并，得到n/2个长度为2或1的有序子序列，再两两归并，如此重复，直到得到一个长度为n的有序序列。

时间复杂度：O(nlogn)

空间复杂度：O(n)

稳定性：稳定

class Solution {
public:
    void merge(vector& nums, int left, int mid, int right){
       int i = left;
       int j = mid+1;
       int k =0;          //新建数组的下标        
       int *L = new int[right - left +1]; //新建数组存放每次合并后的有序序列（空间复杂度为N）
        while(i <= mid && j <= right){   //左右两子序列的合并（较小优先）
            if(nums[i] < nums[j]){
                L[k++] = nums[i++];
            }
            else{
                L[k++] = nums[j++];
            }
        }
        while(i <= mid){           //左右两子序列有一方为空，另一方直接复制到L
            L[k++] = nums[i++];
        }
        while(j <= right){
            L[k++] = nums[j++];
        }
        for(int p = 0; p < k; ++p){  //将合并后的有序序列还原到原序列，在部分有序的基础上进行下一次合并
            nums[left + p] = L[p];
        }
        delete [] L;
    
    }
    
    void mergesort(vector& nums, int left, int right){
        if(left == right){      //将原序列拆分成n个长度为1的子序列
            return;
        }
        else{
            int mid = (right - left) / 2 + left;
            mergesort(nums, left, mid);       //对左子序列归并排序（递归）
            mergesort(nums, mid+1, right);    //对右子序列归并排序（递归）
            merge(nums, left, mid, right);
        }
    }
    
    vector MySort(vector& arr) {    //归并排序
        mergesort(arr, 0, arr.size()-1);
        return arr;
    }
};