[LintCode] Sort Integers 整数排序

时间:2022-08-20 23:50:02

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

Example

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

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

解法一:

// Bubble sort
class Solution {
public:
/**
* @param A an integer array
* @return void
*/
void sortIntegers(vector<int>& A) {
for (int i = ; i < A.size(); ++i) {
for (int j = i + ; 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 sort
class Solution {
public:
/**
* @param A an integer array
* @return void
*/
void sortIntegers(vector<int>& A) {
for (int i = ; i < A.size(); ++i) {
while (i > && A[i] < A[i - ]) {
swap(A[i], A[i - ]);
--i;
}
}
}
};

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

解法三:

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

参考资料:

https://luqinblog.wordpress.com/2016/02/29/sort-integers/