搞一搞简单排序算法…
嘿，你好！排序是一种基本而又有用的算法。今天，我们就来聊聊它。
我们的技术员工在被聘请时，必须答出至少80%的算法题目；其中有60%都与排序相关联。在我们看来，排序是一个技术人员在逻辑分析能力、编程掌握基本语法能力、思维能力、想象力、分配能力的重要体现。我们的人力资源部明确表示，未通过70%以上的面试排序算法题目的应聘者不得被聘用。
泽几华斯 · 沃索得，世界500强公司卜寸仔首席技术官（ CTO ）
比如，问你个小问题，这个问题近来一直困扰着我，希望你能帮我解答。
2008年北京奥运会，俄罗斯-24枚金牌、英国-19枚金牌、中国-51枚金牌、美国-36枚金牌。问题来了，哪个国家获得的金牌数量最多？没错，我听到你说是中国。但是，你是怎么判断出的呢？我想你会说，这很简单啊：挨个看一遍这些数字，再比较一遍哪个大不就行了吗？应当还有不少人正在奇怪为什么我对这么愚蠢的问题感到困惑。😂不错，你们的方法很好。那么，我现在给你20,000,000个数字，希望你能按顺序排好，可以吗？
虽然你似乎算不出来，但是别忘了，我们有一个好朋友——计算机。计算机最喜欢的就是相似的、重复性的劳动了。我们现在就把我们的想法告诉计算机吧！
插入排序
你刚才用的这种方法叫做插入排序。其主旨如下：
遍历每个数字 → 如果比前面的数字大就记住它，或者与前面的数字调换 → 重复执行以上直至完成
例如，有5、4、1、3、2这些数字，要从小到大排列：首先看5，比4大，到4的后面；下一个是1,5也比1大，到1的后面……最后到了最后一位。再来看目前的第2个，是4，同理到了第4位，此时，它发现自己没有5大，于是就乖乖地呆在了第4位。以此类推，五个数都排序好了。
这是一种可以说最为基本的简单排序算法了。我们可以轻易地使用C++来实现：
#include<cstdio> //包含printf函数
using namespace std;
int main(){
int i,j,size=6,temp;
int a[]={34,65,87,23,56,18};
for (i=1;i<size;i++){ //遍历
temp=a[i];
j=i-1;
while((j>=0)&&(a[j]>temp)){ //如果左边比右边大……
a[j+1]=a[j]; //……那么就替换
j--;
}
a[j+1]=temp;
}
for(i=0;i<size;i++){
printf("%d ",a[i]); //把排序好的数组一个一个输出
}
return 0;
}
它的时间复杂度是（O·n2）。n的大小与数据多少有关，下同。时间复杂度是算法的一种属性，它标志着算法可能的耗时相对值。
选择排序
这儿还有另一种排序算法。它的主要实现方式为：
遍历所有数，找到最小的，与第一个数替换 → 遍历剩下的数，找到这其中最小的，放在第2位 → 以此类推，直到结束
仍然以上述的数字举例。这次，5和4比较，5比4大，它们调换位置；5到第二位。5和1比较，5比1大，它们调换位置……5调换到了第5位。以此类推。
我们用C++也可以很简单地实现：
#include<cstdio>
using namespace std;
int main(){
int size=5;
int a[size]={23,32,64,67,25};
int i, j, temp;
for (i=0; i<size; i++){
for (j=i+1;j<size;j++){
if (a[j]<a[i]){
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
for (i=0;i<size;i++){
printf("%d ",a[i]);
}
return 0;
}
当然，任何算法都并非只有C++可以实现。比如，闲来无事，用JavaScript写个选择排序试试：
var arr = [3,2123,12,23,1,321,213];
for(var i = 0 ; i <= arr.length-1 -1 ; i++){
var min = i;
for(var j = i+1 ; j <= arr.length-1 ; j++){
if(arr[min] > arr[j] ){
min = j;
}
}
if(min != i){
var m;
m = arr[min];//替换
arr[min] = arr[i];
arr[i] = m;
}
}
console.log(arr); //输出数组
它的时间复杂度也是（O·n2）。
冒泡排序
冒泡排序也是一种简单排序算法。它的实现方式如下：
从第一个数开始，如果比第二个数大就调换 → 第二个数，如果比第三个数大就调换 → 以此类推，直至结束
仍然以上述的数字举例。这次，5和4比较，5比4大，它们调换位置；5到第二位。5和1比较，5比1大，它们调换位置……5调换到了第5位。以此类推。这很像放了一个暑假，同学们都长高了个子，需要重新排列班级列队。你比后面的人高，老师叫你到那个人后面去；不巧，比他再后面的人也高，再到更往后一个去，直到你后面的人比你高了为止。
写到这里感到选择排序和冒泡排序好像……如果我这里写错了或者写反了，请批评指正哈！
好了，总之，C++实现代码如下：
#include<cstdio>
using namespace std;
int main(){
int size=5;
int i,j,temp;
int a[size]={39,89,53,23,70};
for(i=0;i<size-1;i++){
for(j=size-1;j>i;j--){
if(a[j]<a[j-1]){
temp=a[j];
a[j]=a[j-1];
a[j-1]=temp;
}
}
}
for (i=0;i<size;i++){
printf("%d ",a[i]);
}
return 0;
}
冒泡排序的时间复杂度还是 （O·n2） 。
以上就是基本的简单排序算法介绍。感谢你的阅读。限于技术水平有限与时间匆忙，本文必有不少谬误，还请你在评论区提出，或者发邮件告知我。