数据结构--排序基础算法

1.插入排序
时间复杂度O(N^2)
空间复杂度O(1)

vector<int> insertionSort9(vector<int>& nums) {
        if(nums.size <= 1)
            return nums;
        for(int i = 1; i < nums.size(); i++)
        {
            int v = nums[i];        //临时变量保存nums[i]的值
            int j = i - 1;            
            while(j >= 0 && nums[j] > v)  //在已排序部分寻找插入位置
            {
                nums[j + 1] = nums[j];
                j--;
            }
            nums[j + 1] = v;
        }
        return nums;
    }

2.冒泡排序
时间复杂度：O(N^2)
空间复杂度：O(1)

   vector<int> bubbleSort(vector<int>& nums) {
      if(nums.size() <= 1)
          return nums;
      bool flag = true;
      for(int i = 0; flag; i++)
      {
          flag = false;
          for(int j = nums.size() - 1; j >= i + 1; j--)
          {
              if(nums[j - 1] > nums[j])
              {
                  int temp = nums[j - 1];
                  nums[j - 1] = nums[j];
                  nums[j] = temp;
                  flag = true;
              }
          }
      }
      return nums;
  }

3.选择排序
时间复杂度：O(N^2)
空间复杂度：O(1)

   vector<int> sortArray(vector<int>& nums) {
       
       for(int i = 0; i < nums.size() - 1; i++)
       {
           int minNum = i;
           for(int j = i + 1; j < nums.size(); j++)   //从未排序序列中选取最小值，记录最小值位置
           {
               if(nums[j] < nums[minNum])
               {
                   minNum = j;
               }
           }
            int temp = nums[minNum];   
            nums[minNum] = nums[i];
            nums[i] = temp;
       }
       return nums;
   }
};

数据结构--排序基础算法

原文：https://www.cnblogs.com/ZigHello/p/14767988.html