LeetCode笔记——912.排序数组

给你一个整数数组 nums，请你将该数组升序排列。

class Solution {
public:
    vector sortArray(vector& 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 temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                }
            }
        }
        return nums;
    }
};

利用冒泡排序快排，即相邻数组对比让最大的数字沉底。

1.冒泡排序的时间复杂度为O(n^2)，测试案例中存在一个5000个数的排列。

原因：未经过优化的快排无法通过

2.可用基于随机选取主元的快速排序，堆排序，归并排序，类库。