原文发表在我的博客：整数排序
求关注、求交流、求意见、求建议。
问题
LintCode：整数排序
描述
给一组整数，按照升序排序，使用选择排序，冒泡排序，插入排序或者任何 O(n2) 的排序算法。
样例
对于数组 [3, 2, 1, 4, 5] ， 排序后为：[1, 2, 3, 4, 5] 。
实现
排序是最常见的算法了，但也不是人人都能信手拈来的。toptal 提供了 Sorting Algorithms Animations 帮助人们理解和对比各种排序，每一种排序都有介绍、伪代码以及不同情况下的动画演示，在这里向大家推荐。
意识排序
意识排序就是潜意识下写出来的排序，并没有一个名字。
class Solution {
public:
void sortIntegers(vector<int>& A) {
// 29ms
int i, j, buffer;
int size = A.size();
for (i = 0; i < size; ++i)
for (j = 0; j < i; ++j) {
if (A[i] < A[j]) {
buffer = A[j];
A[j] = A[i];
A[i] = buffer;
}
}
}
冒泡排序
class Solution {
public:
void sortIntegers(vector<int>& A) {
// 33ms
int i, j, buffer;
bool swapped = true;
int size = A.size();
for (i = 0; i < size && swapped; ++i)
for (j = size - 1, swapped = false; j > i; --j)
if (A[j] < A[j - 1]) {
buffer = A[j];
A[j] = A[j - 1];
A[j - 1] = buffer;
swapped = true;
}
}
}
选择排序
class Solution {
public:
void sortIntegers(vector<int>& A) {
// 28ms
int i, j, key, buffer;
int size = A.size();
for(i = 0; i < size; ++i){
key = i;
for(j = i; j < size; ++j) {
if(A[j] < A[key]) key = j;
}
buffer = A[i];
A[i] = A[key];
A[key] = buffer;
}
}
}
插入排序
class Solution {
public:
void sortIntegers(vector<int>& A) {
// 20ms
int i, j, temp;
int size = A.size();
for(i = 1; i < size; ++i) {
if(A[i] >= A[i - 1]) continue;
temp = A[i];
for (j = i - 1; j >= 0 && A[j] > temp; --j){
A[j + 1] = A[j];
}
A[j + 1] = temp;
}
}
}
快速排序
class Solution {
public:
void sortIntegers(vector<int>& A) {
// 14ms
Qsort(A, 0, A.size() - 1);
}
void Qsort(vector<int>& A, int low, int high) {
if(low >= high) return;
int begin = low;
int end = high;
int temp = A[low];
while (begin < end) {
while(A[end] >= temp) --end;
A[begin] = A[end];
while(begin < end && A[begin] <= temp) ++begin;
A[end] = A[begin];
}
A[begin] = temp;
Qsort(A, low, begin - 1);
Qsort(A, begin + 1, high);
}
}
总结
因为是很常见的排序，就没有写具体的分析，而且 Sorting Algorithms Animations 上给的很清晰。务必要打开看一下，非常好的网站。
虽然排序各种标准库里都有，但是还是要多思考、多了解一点，不仅可以锻炼一下逻辑能力，还可以在某些特殊情况下有奇效。
