463、整数排序

题目要求：

1.插入排序

class Solution {
public:
     //插入排序
    void sortIntegers(vector<int> &A)
    {
        // write your code here
       for(int i =1;i<A.size();++i)  //从1位置开始
         while(i>0 && A[i] < A[i-1]) //如果满足i>0，且当前位置的值比前一个位置值小，则交换位置，
         {                           //并进行--i操作，否则说明满足升序，往后进行查找
             swap(A[i],A[i-1]);
             --i;
         }
    }
};

2.冒泡排序

class Solution {
public:
     //冒泡排序
    void sortIntegers(vector<int> &A)
    {
        // write your code here
       for(int i =0;i<A.size();i++)
       {
           for(int j=0;j<A.size()-i-1;j++) //从第一个开始，相邻元素两两比较，将小者放在大者前面
           {                              //经过第一遍排序，最大元素必然就位，故下次比较次数减一
               if(A[j] > A[j+1])
               {
                   swap(A[j],A[j+1]);
               }
           }
       }
       
         
    }
};

3.选择排序

class Solution {
public:
     //选择排序
    void sortIntegers(vector<int> &A)
    {
        // write your code here
        int mix,temp;
       for(int i =0;i<A.size();i++)  //每次循环找出最小元素放在前面，从而前面的是排序好的
       {
           mix=i;  //先假设一个最小元素mix，接下来不断去寻找最小元素
           for(int j=i+1;j<A.size();j++)//将上面假设的最小元素与接下来个元素比较，交换出最小元素
           {
               if(A[j] < A[mix])  //如果后面的小，将小的元素的位置赋值给最小元素位置参数变量
               {
                   mix=j;   
               }
           }
           if(i != mix)   
           {
               swap(A[i],A[mix]);  //每一轮下来，交换位置
           }
       }
    }
};