一、插入排序
遍历数组的元素，nums[i]如果比nums[i-1]小，就说明需要将其插入到nums[0]....nums[i-1]的序列中。
var sortArray = function(nums) {
var lookout = nums[0]; //监视哨，提供nums[i]的缓存单元
for(var i=1;i<=nums.length;i++){
if(nums[i] < nums[i-1]){
lookout = nums[i]; // 将nums[i]保存到监视哨中
// 逐级后移
for(var j=i-1;j>=0 && nums[j]>lookout;j--){
nums[j+1] = nums[j];
}
// 插入nums[i]
nums[j+1] = lookout;
}
}
return nums;
};
算法复杂度：O(n^2)
二、希尔排序
将待排序数组根据一定的增量分组，每一组都进行插入排序，再减少增量，每组元素变多，当增量减至1时，整个文件恰被分成一组，对该组排序进行微调，算法便终止。
var sortArray = function(nums) {
var len = nums.length;
int temp, gap = len / 2;
while (gap > 0) {
for (int i = gap; i < len; i++) {
temp = nums[i];
int preIndex = i - gap;
while (preIndex >= 0 && nums[preIndex] > temp) {
nums[preIndex + gap] = nums[preIndex];
preIndex -= gap;
}
nums[preIndex + gap] = temp;
}
gap /= 2;
}
return nums;
}
算法复杂度：O(nlogn)
三、冒泡排序
在一趟比较中，比较相邻两个元素nums[j]和nums[j+1]的大小，如果nums[j]>nums[j+1]，两元素交换，这样最大的元素冒泡到数组的最右边。重复上述步骤，直到不存在需要交换的元素，结束循环。
var sortArray = function(nums) {
var tmp;
if(nums.length == 0) return [];
for(var i=0;i<nums.length;i++){
for(var j=0;j<nums.length-i;j++){
if(nums[j] > nums[j+1]){
tmp = nums[j+1];
nums[j+1] = nums[j];
nums[j] = tmp;
}
// console.log(nums)
}
}
return nums;
};
复杂度O(n^2)
四、快速排序
以序列中第一个元素作为基准，在比较分区的过程中，如果比这个数小的就放在左边，比这个数大的放在右边，返回这个基准数在序列中的位置；在这一趟比较中，比基准数小的数就全部在其左边，大的数全部在其右边。对左右区间分别重复上述步骤，直到区间中只有一个元素(low=high=0)。
var sortArray = function(nums) {
// 快速排序
quickSort(nums,0,nums.length-1);
return nums;
};
var getPivot = function(nums,low,high){
var pivot;
while(low<high){
while(low<high && nums[high] >= nums[low]){
// 向前寻找比基准数小的元素
high--;
}
if(nums[high] < nums[low]){
// 较小的元素交换到基准数左边
pivot = nums[low];
nums[low] = nums[high];
nums[high] = pivot;
}
while(low<high && nums[low]<=nums[high]){
// 向后寻找比基准数大的元素
low++;
}
if(nums[low]>nums[high]){
// 较大的元素交换到基准数右边
pivot = nums[low];
nums[low] = nums[high];
nums[high] = pivot;
}
}
return low;
}
var quickSort = function(nums,low,high){
if(low<high){
var i = getPivot(nums,low,high); // 返回基准数位置
quickSort(nums,low,i-1); // 对左右区间分别重复操作
quickSort(nums,i+1,high);
}
复杂度O(nlogn)
五、选择排序
将序列分为排序序列和未排序序列，初始状态下排序序列只有一个元素，即原序列的第一个元素。选择未排序序列中最小的元素，将它交换到排序序列的最后一位。重复上述操作。
var sortArray = function(nums) {
// 选择排序
var sortedNums = nums[0],
index,
mintmp,minindex,
temp;
for(var i=0;i<nums.length;i++){
minindex = i;
mintmp = nums[minindex];
for(var j=i+1;j<nums.length;j++){
if(nums[j]<mintmp){
mintmp = nums[j];
minindex = j;
}
}
temp = nums[i];
nums[i] = nums[minindex];
nums[minindex] = temp;
}
return nums;
};
复杂度O(n^2)
六、归并排序
将待排序列多次二分成小序列，直到每个小序列只有一个元素为止。然后将小序列归并成排好序的较大序列，直到归并成最大的序列。
图分析如下：（来源于https://blog.csdn.net/wojiuguowei/article/details/84321833）
归并排序图解
var sortArray = function(nums) {
// 归并排序
if(nums.length == 1){
return nums;
}
// 拆分子列
var mid = parseInt(nums.length/2),
left = nums.slice(0,mid),
right = nums.slice(mid,nums.length),
sortedNums = new Array();
// 子列不可再分（只有一个元素）后开始归并
sortedNums = merge(sortArray(left),sortArray(right));
return sortedNums;
};
var merge = function(left,right){
var len_l = left.length, // 序列剩余元素的个数
len_r = right.length,
i = 0,
j = 0,
result = [];
// 左右两列开始归并，由于两列都是有序的，只需要比较开始的元素大小后指针后移即可
while(i<left.length && j<right.length){
// if(left[i] == undefined) left[i] = Infinity;
// if(right[i] == undefined) right[i] = Infinity;
if(left[i]<right[j]){
result.push(left[i]);
i++;
len_l--;
}else{
result.push(right[j]);
j++;
len_r--;
}
}
// 考虑到两序列的长度不一样，将剩下的序列直接放入result尾部
while(len_l>0){
result.push(left[i]);
i++;
len_l--;
}
while(len_r>0){
result.push(right[j]);
j++;
len_r--;
}
return result;
}
复杂度O(nlogn)
