许多高级语言中都提供有排序函数，但是掌握一些经典排序算法的基本原理和编码方法还是很有必要，这个学习过程可以帮助我们更好的理解每种排序算法的设计思路，本篇博客将介绍9种十分经典的排序算法，提供了解释性语言JavaScript与编译型语言C的源代码。
一、直接插入排序
直接插入排序是最简单的一种排序算法，也最容易理解。它的核心思想为将元素逐个插入一个有序的数列中。用文字描述可以分为如下几步：
1.把数列中的第一个元素取出，作为有序数列的起始元素。
2.依次拿数列中的其他元素与有序数列中的元素进行比较，将其插入正确的位置。
用图示描述插入排序如下：
直接插入排序的特点是对新元素的每轮插入前，有序数列中的所有元素都是排序好的，即任意时刻，被排序动过的元素组成的数列都是有序的。
用JavaScript实现的简单插入排序：
//插入排序
var array = [1,54,2,64,12,65,76,46,34,98];
for(var i = 0;i<array.length-1;i++){
var temp = array[i+1];
for(var j = i+1;j>0;j--){
if (temp<array[j]) {
array[j+1] = array[j];
array[j] = temp;
}
}
}
console.log(array);//[ 1, 2, 12, 34, 46, 54, 64, 65, 76, 98 ]
用C实现的简单插入排序：
#include <stdio.h>
void mySort(int array[],int size){
for(int i=0;i<size-1;i++){
int temp = array[i+1];
for(int j=i+1;j>0;j--){
if(temp<array[j]){
array[j+1] = array[j];
array[j] = temp;
}
}
}
}
int main(){
int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98 };
mySort(a,10);
for(int i = 0;i<10;i++){
printf("%d\n",a[i]);
}
return 0;
}
二、二分插入排序(折半插入排序)
二分插入排序也是插入排序的一种，其又叫做折半插入排序。它与直接插入排序的唯一不同只在于查找插入位置的方式。直接插入排序是通过遍历来查找要插入元素的位置，二分插入排序则是通过二分法来查找要插入的位置，之后将此位置所有元素后移，将排序的元素进行插入。
JavaScript实现的二分插入排序：
var array = [1,54,2,64,12,65,76,46,34,98];
//二分插入排序
for(var i=0;i<array.length-1;i++){
var temp = array[i+1];
var left = 0;
var right = i;
var middle;
while(left<=right){
middle = Math.round((left+right)/2);
if (array[middle]>temp) {
right=middle-1;
}else{
left = middle+1;
}
}
for(var j=i+1;j>left;j--){
array[j] = array[j-1];
}
array[left] = temp;
}
console.log(array);//[ 1, 2, 12, 34, 46, 54, 64, 65, 76, 98 ];
C实现的二分插入排序：
#include <stdio.h>
//二分插入排序
void mySort(int array[],int size){
for(int i=0;i<size-1;i++){
int temp = array[i+1];
int left=0,right=i,middle;
while(left<=right){
middle = (left+right)/2;
if(array[middle]>temp){
right=middle-1;
}else {
left = middle+1;
}
}
for(int j =i+1;j>left;j--){
array[j] = array[j-1];
}
array[left] = temp;
}
}
int main(){
int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98 };
mySort(a,10);
for(int i = 0;i<10;i++){
printf("%d\n",a[i]);
}
return 0;
}
