Lintcode--1(463)--整数排序

题目：给一组整数，按照升序排序，使用选择排序，冒泡排序，插入排序或者任何 O(n2) 的排序算法

1、冒泡排序

原理：从第一个整数开始第一趟，比较相邻的两个元素，大的放在后面；一轮结束后，最大的数沉底；重复这一过程，完整n-1趟。
所以有两个循环，外循环决定第几趟、从第几个元素开始比较；内循环是比较相邻两个元素大小，决定要不要交换。

class Solution
{
public:
    /*
     * @param A: an integer array
     * @return: 
     */
    void sortIntegers(vector<int> &A)
    {
        int temp = 0;
        if(A.size()!=0)//判断是否为空数组
        {
        for(int i=0; i<A.size()-1; i++)//外循环只比较A.size()-1趟
            for(int j=i+1; j<A.size(); j++)//内循环从i+1开始
            {
                if(A[i] > A[j])
                  {
                      temp = A[j];//交换
                      A[j] = A[i];
                      A[i] = temp;
                  }
                
            }
        }
    }
};

2、插入排序

原理：第一趟把第一个元素当做有序序列，用第二个和第一个比，将大的放在后面；第二趟把前两个元素当做有序序列，用第三个元素跟第二个比，大的放后面，再用第二个跟第一个比，大的放后面；第三趟把前三个当做有序序列，用第四个元素跟第三个比，再用第三个跟第二个比，第二个跟第一个比；......以此类推。两个循环，外循环决定从无序序列开始，内循环进行从后往前的两两比较和交换。

class Solution 
{
public:
    /**
     * @param A an integer array
     * @return void
     */
    void sortIntegers(vector<int>& A) 
    {
        int temp = 0;
        for (int i = 1; i < A.size(); ++i) //从第二个元素开始
       {
            while (i > 0 && A[i] < A[i - 1])//当该元素前面还有元素，且比前面的数小，就进行下面的交换
           {
                temp = A[i];
                A[i] = A[i-1];
                A[i-1] = temp;
                --i;//递减，往前比较
            }
        }
    }
};

3、选择排序

原理：遍历整个数组，对于当前位置i，定义一个变量min_idx，用来记录当前位置往后的最小的坐标，并通过遍历以后所有的数字来找这个最小的坐标；然后交换A[i]和A[min_idx]。
外循环定义当前位置，内循环找到当前往后最小的元素坐标。从第一个元素开始，选择后面元素里面最小的一个和第一个元素交换，直到最后一个元素。

class Solution 
{
public:
    /**
     * @param A an integer array
     * @return void
     */
    void sortIntegers(vector<int>& A) 
   { 
        for (int i = 0; i < A.size(); ++i) 
       {
            int min_idx = i;
            for (int j = i + 1; j < A.size(); ++j) 
           {
                if (A[j] < A[min_idx]) 
               {
                    min_idx = j;
                }
            }
            swap(A[i], A[min_idx]);
        }
    }
};

参考： lintcode整数排序