题解32 | 经典冒泡+快速+归并#排序#

1.冒泡排序

时间复杂度为O(n^2)，空间复杂度为O(1)。

基本算法思想是比较相邻的两个元素，如果顺序错误就交换位置，直到整个数组有序。

#include <algorithm>
#include <fstream>
#include <vector>
class Solution {
public:
    /*
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    //经典冒泡排序
    void bubbleSort(vector<int>& arr){
        int i,j,temp;
        for(i = 1; i < arr.size(); i++){
            for (j = 0; j < i; j++) {
                if (arr[i] < arr[j]) {
                    swap(arr[i],arr[j]);
                }  
            }//for in
        }//for out
    }
   //最终汇总实现
    vector<int> MySort(vector<int>& arr) {
        // write code here
        // bubbleSort(arr);
        // quickSort(arr, 0, arr.size() - 1);
        int left = 0;
        int right = arr.size() - 1;
        vector<int> tmp = arr;
        mergeSort(arr, left, right, tmp);
        return arr;
    }
};

2.快速排序

时间复杂度为O(nlogn)，空间复杂度为O(logn)。

基本算法思想是选择一个基准元素，将数组分为两部分，一部分小于基准元素，一部分大于基准元素，然后对两部分进行递归排序。

//快速排序

 void quickSort(vector<int> &array, int start, int end) {
        if(start < end){
            int key = array[start];
            int i = start;
            int j = start + 1;

            for( ; j <= end; j++){
                if (key > array[j]) {
                    //先进行自增 一个一个往前塞
                    i++;
                    swap(array[i],array[j]);
                }
            }
            //把比key小（大）的极值放到start，然后再把中枢放到指定位置【i】
            array[start] = array[i];
            array[i] = key;
            //递归处理左右剩余部分
            quickSort(array, start, i - 1);
            quickSort(array, i + 1, end);
        } 
    }

3.归并排序

时间复杂度为O(nlogn)，空间复杂度为O(n)。

基本算法思想是将数组不断划分为两个子数组，然后将两个子数组合并成一个有序数组。

//归并排序

 void mergeSort(vector<int> &arr, int left, int right, vector<int> tmp){
       if(left == right)//特殊情况
            return ;
    	//确定中间值
       int mid = (left + right) / 2;

       mergeSort(arr, left, mid, tmp);//左部分到mid
       mergeSort(arr, mid+1, right, tmp);//右部分从mid+1开始

       merge(arr,left,mid,right,tmp);

    }
 void merge(vector<int> &arr, int left, int mid, int right, vector<int> tmp) {
       int i = 0;
       int l = left;//左半数组的下标  
       int m = mid+1;//右半数组的下标
		//先合并存到辅助数组
       while (l <= mid && m <= right) {
            tmp[i++] = arr[l]<arr[m]? arr[l++]:arr[m++];
       }
       while (l <= mid ) {
            tmp[i++] = arr[l++];
       }
       while (m <= right) {
            tmp[i++] = arr[m++];
       }
		//辅助数组再重新复制给原来的arr数组返回
       for(int j = left; j <= right; j++){
            arr[j] = tmp[j];
       }
    }