摘要：待排序的记录序列中可能存在两个或两个以上的关键字相等的记录，且在排序前在前面即，若在排序后的序列中任然在前面，则称所用的排序算法是稳定的。基数排序留各种排序算法比较以上用到的函数函数返回生成的数组结束
排序 Sorting 排序基本概念
排序是计算机程序设计中的一种重要操作，他的功能是将一个数据元素(或记录)的任意排列，重新排列成一个按关键字有序的序列。
待排序的记录序列中可能存在两个或两个以上的关键字相等的记录，且在排序前Ri在Rj前面(即i
如果按照排序过程中依据的不同原则对内部排序进行分类，则可分为
插入排序
交换排序(快速排序)
选择排序
归并排序
基数排序
如果按照工作量来区分可以分为3类
简单的排序算法，时间复杂度为O(n2)
先进的排序算法，时间复杂度为O(nlogn)
基数排序，时间复杂度为O(d*n)
通常，在排序的过程中需要进行下列两种基本操作，(其中第二种操作可以通过改变记录的存储方式来予以避免)
比较两个关键字大小
将记录从一个位置移动至另一个位置
待排序的记录序列可有下列3种存储方式。
存储在地址连续的一组存储单元上。
静态链表，记录之间的次序由指针指示，则实现排序不需要移动记录
待排序记录存储在一组地址连续的存储单元内，同时，另外设一个指示各个记录存储位置的地址向量，在排序过程中不移动记录本身，而是移动地址向量
中这些记录的“地址”，在排序结束后再按照地址向量中的值调整记录的存储位置。
最为简单的一种排序，基本操作为将一个记录插入到已经排好序的有序表中，从而得到一个新的，记录增1的有序表。
//直接插入排序，更为高效的应该是折半插入排序¬≥
function insertSort (Arr) {
if (Arr.length <= 1) {
return Arr;
}
var temp;
for (var i = 1; i < Arr.length; i++) { //从1开始，第一个不用排序
temp = Arr[i]; //用temp缓存待插入的元素
for (var j = i; j >= 0; j--) {
if (temp < Arr[j]) {
Arr[j + 1] = Arr[j]; //当Arr[i] Arr[j]) {
break; //第一种：如果找到了一个比Arr[i]小的Arr[j],则退出循环，结束
}
//第二种，当j循环，结束
}
//结束j循环，将temp中缓存的待插入元素插入
Arr[j + 1] = temp;
}
}; //insert结束
其他插入排序
折半插入排序 O(n2) 通过减少比较关键字大小次数来优化排序算法。
2路插入排序
表插入排序
希尔排序 O(n3/2)又被称为"缩小增量排序"。基本思想：先将整个待排记录序列分割成若干个子序列分别进行直接插入排序，待整个序列中的记录
“基本有序”时，再对全体记录进行一次直接插入排序。
function shellSort(Arr) {
var gap = Math.floor(Arr.length / 2);
while (gap > 0) {
for (var i = 0; i < Arr.length; i++) {
var temp = Arr[i];
for (var j = i; j >= gap && Arr[j - gap] > temp; j -= gap) {
Arr[j] = Arr[j - gap];
}
Arr[j] = temp;
}
gap = Math.floor(gap / 2);
}
return Arr;
}; //shell结束
快速排序
起泡排序 bubble sort
// 起泡排序,
function bibbleSort(Arr) {
for (var i = Arr.length - 1; i >= 0; i--) {
for (var j = 0; j < i; j++) {
if (Arr[j] > Arr[j + 1]) {
swap(j, j + 1, Arr);
}
}
}
return Arr;
};
快速排序 quick sort
