Given an integer array, sort it in ascending order. Use selection sort, bubble sort, insertion sort or any O(n²) algorithm.

 

Example

Given [3, 2, 1, 4, 5], return [1, 2, 3, 4, 5].

 

这道题让我们实现最基本的几个O(n²)的排序算法，选择排序，冒泡排序和插入排序，都是最基本的排序算法。我们一个一个来看，首先来看冒泡排序，算法思路很简单，遍历数组，把当前数字的后面所有的数字都遍历一遍，遇到小的跟当前数字交换，这样遍历的过程中，所有大的数字就像气泡一样都到数组的后面去了，这也是为啥叫冒泡排序的原因，参见代码如下：

 

解法一:

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

 

下面来看插入排序，算法思路是遍历数组，从A[i]开始往前比，如果遇到A[i] < A[i - 1]，那么交换两者并--i，直到i=0位置停止，参见代码如下：

 

解法二：

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

 

选择排序也不难，思路是遍历数组，对于当前位置i，我们定义一个变量min_idx，用来记录当前位置往后的最小值的坐标，我们通过遍历之后所有的数字来找到最小值的坐标，然后交换A[i]和A[min_idx]即可，参见代码如下：

 

解法三：

// Selection sortclass Solution {public:    /**     * @param A an integer array     * @return void     */    void sortIntegers(vector
     
      & 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]);        }    }};
     

 

参考资料：