一凹炸、插入排序
遍歷數(shù)組的元素洞渤，nums[i]如果比nums[i-1]小雪隧，就說明需要將其插入到nums[0]....nums[i-1]的序列中碍讯。
var sortArray = function(nums) {
var lookout = nums[0]; //監(jiān)視哨悬蔽，提供nums[i]的緩存單元
for(var i=1;i<=nums.length;i++){
if(nums[i] < nums[i-1]){
lookout = nums[i]; // 將nums[i]保存到監(jiān)視哨中
// 逐級后移
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)
二、希爾排序
將待排序數(shù)組根據(jù)一定的增量分組捉兴，每一組都進行插入排序蝎困，再減少增量，每組元素變多倍啥，當增量減至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]，兩元素交換凭峡，這樣最大的元素冒泡到數(shù)組的最右邊拙已。重復上述步驟，直到不存在需要交換的元素摧冀，結束循環(huán)倍踪。
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)
四、快速排序
以序列中第一個元素作為基準索昂，在比較分區(qū)的過程中建车，如果比這個數(shù)小的就放在左邊，比這個數(shù)大的放在右邊椒惨，返回這個基準數(shù)在序列中的位置缤至；在這一趟比較中，比基準數(shù)小的數(shù)就全部在其左邊康谆，大的數(shù)全部在其右邊领斥。對左右區(qū)間分別重復上述步驟嫉到，直到區(qū)間中只有一個元素(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]){
// 向前尋找比基準數(shù)小的元素
high--;
}
if(nums[high] < nums[low]){
// 較小的元素交換到基準數(shù)左邊
pivot = nums[low];
nums[low] = nums[high];
nums[high] = pivot;
}
while(low<high && nums[low]<=nums[high]){
// 向后尋找比基準數(shù)大的元素
low++;
}
if(nums[low]>nums[high]){
// 較大的元素交換到基準數(shù)右邊
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); // 返回基準數(shù)位置
quickSort(nums,low,i-1); // 對左右區(qū)間分別重復操作
quickSort(nums,i+1,high);
}
復雜度O(nlogn)
五月洛、選擇排序
將序列分為排序序列和未排序序列何恶，初始狀態(tài)下排序序列只有一個元素，即原序列的第一個元素嚼黔。選擇未排序序列中最小的元素细层，將它交換到排序序列的最后一位。重復上述操作唬涧。
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, // 序列剩余元素的個數(shù)
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)
