一、插入排序
直接插入排序，可以用链表，分成有序和无序二部分，
第一步是比较找到位置，第二部插入

            //力扣插入排序超时了。。
    for(int i =1;i<nums.size();i++){
            int temp =nums[i];
            int j =i-1;
            while(j>=0){
                if(temp < nums[j]){
                  nums[j+1] = nums[j]; 
                  j--;  
                }else{
                    break;
                }
            }
            nums[j+1] = temp;
        }

折半插入和希尔排序（不稳定）跳过了
二、交换排序
冒泡排序

 for(int i=nums.size()-1; i>-1;i--){
            int flag =0;
            for(int j =0;j<i;j++){
                if(nums[j]>nums[j+1]){
                    swap(nums[j],nums[j+1]);
                    flag =1;
                }
            }
            if(flag==0){break;}
        }

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
       quickSort(nums,0,nums.size()-1);
        return nums;
    }
    void quickSort(vector<int>& nums,int p,int r) {
        if(p<r){
            int q = partition(nums,p,r);
            quickSort(nums,p,q-1);
            quickSort(nums,q+1,r);
        }
    }
    int partition(vector<int>& nums,int p,int r) {
        int temp =nums[r];
        int i =p-1;
        for(int j =p;j<r;j++){
            if(nums[j]<=temp){
                i++;
                swap(nums[i],nums[j]);
            }
        }
        swap(nums[i+1],nums[r]);
        return i+1;        
    }
};

随机数版本

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
       quickSort(nums,0,nums.size()-1);
        return nums;
    }
    void quickSort(vector<int>& nums,int p,int r) {
        if(p<r){
            int q = randomized_partition(nums,p,r);
            quickSort(nums,p,q-1);
            quickSort(nums,q+1,r);
        }
    }
     int randomized_partition(vector<int>& nums, int l, int r) {
        int i = rand() % (r - l + 1) + l; // 随机选一个作为我们的主元
        swap(nums[r], nums[i]);
        return partition(nums, l, r);
    }
    int partition(vector<int>& nums,int p,int r) {
        int temp =nums[r];
        int i =p-1;
        for(int j =p;j<r;j++){
            if(nums[j]<=temp){
                i++;
                swap(nums[i],nums[j]);
            }
        }
        swap(nums[i+1],nums[r]);
        return i+1;        
    }
};

三、选择排序
堆排序，建堆o(n)，调整n次，每次复杂度o(h)