不知道你所指的排序是哪种规则排序。排序算法分类 比较排序，时间复杂度为O(nlogn) ~ O(n^2)，主要有冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等 非比较排序，时间复杂度可以达到O(n)，主要有计数排序，基数排序，桶排序等。
选择排序每次比较的是数组中特定索引的值与全数组中每个值的大小比较，每次都选出一个最小(最大)值，如果当前索引的值大于之后索引的值，则两者进行交换。
冒泡排序每次从数组的最开始索引处与后一个值进行比较，如果当前值比较大，则交换位置。这样一次循环下来，最大的值就会排入到的位置。
插入排序类似于扑克牌的插入方法，选取待排列数组中的任意一个数字作为已排序的基准，再依次从待排序数组中取出数字，根据依次比较，将这个数字插入到已排序的数组中。
二分插入排序是直接插入排序的一个变种，利用二分查找法找出下一个插入数字对应的索引，然后进行插入。当n较大时，二分插入排序的比较次数比直接插入排序的最差情况好得多，但比直接插入排序的最好情况要差，所当以元素初始序列已经接近升序时，直接插入排序比二分插入排序比较次数少。二分插入排序元素移动次数与直接插入排序相同，依赖于元素初始序列。
希尔排序是一种更高效的插入排序，通过设计步长(gap)将数组分组，然后每组中单独采用排序算法将每组排序，然后在缩小步长，进行重复的分组排序工作，直到gap变为1的时候，整个数组分为一组，算法结束。
例如数组 [1, 4, 5, 2, 3, 9, 0, 7, 6]，如果每次以数组长度的一半来作为步长，可以分解为以下步骤
1. gap: Math.floor(9 / 2) = 4;
分为四组，分组为
{ 1, 3 }, { 4, 9 }, { 5, 0 }, { 2, 7 }
一个数字 6 需要等到第5个数字排序完成，也就是3，可以得出3依旧还处在第4索引的位置，一个分组为 { 3, 6 }
完成一轮分组以及排序后的数组为[ 1, 4, 0, 2, 3, 9, 5, 7, 6 ]
2. gap: Math.floor(4 / 2) = 2;
分为两组，分组为
{ 1, 0, 3, 5, 6 }, { 4, 2, 9, 7 }
完成第二轮分组以及排序后的数组为[ 0, 2, 1, 4, 3, 7, 5, 9, 6 ]
3. gap: Math.floor(2 / 2) = 1;
分为一组，即为{ 0, 2, 1, 4, 3, 7, 5, 9, 6 }
完成第三轮分组以及排序后的数组为[ 0, 1, 2, 3, 4, 5, 6, 7, 9 ]
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- 根据步长序列的不同而不同。已知最好的为O(n(logn)^2)
// 最优时间复杂度 ---- O(n)
// 平均时间复杂度 ---- 根据步长序列的不同而不同。
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 不稳定
var arr = [1, 4, 5, 2, 3, 9, 0, 7, 6];
var gap = Math.floor(arr.length / 2);
function swap(arr, i, j) {
var t;
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
for (; gap > 0; gap = Math.floor(gap / 2)) {
//从第gap个元素，逐个对其所在组进行直接插入排序操作
for(var i = gap; i < arr.length; i++) {
var j = i;
// 这里采用的其实是冒泡排序
while(j - gap >= 0 && arr[j] < arr[j-gap]) {
//插入排序采用交换法
swap(arr, j, j-gap);
j -= gap;
}
// 或者插入排序
var temp = arr[j];
if (arr[j] < arr[j-gap]) {
while (j-gap >= 0 && temp < arr[j-gap]) {
arr[j] = arr[j-gap];
j -= gap;
}
arr[j] = temp;
}
}
}
console.log(arr);
