代碼雖源自抄襲蛔添，自己重寫時(shí)改了一下變量名卷员，消化更好了_
冒泡排序（Bubble Sort）
1. 算法步驟
- 比較相鄰的元素。如果第一個(gè)比第二個(gè)大雷酪，就交換他們兩個(gè)捂龄。
- 對(duì)每一對(duì)相鄰元素作同樣的工作释涛，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后倦沧，最后的元素會(huì)是最大的數(shù)唇撬。
- 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)刀脏。
- 持續(xù)每次對(duì)越
2. 動(dòng)圖演示
3. JavaScript 代碼實(shí)現(xiàn)
function sort(arr){
var len=arr.length;
for(var i=0;i<len;i++){
for(var j=0;j<len-1-i;j++){
if(arr[j]>arr[j+1]){
var temp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
}
}
}
return arr;
}
console.log(sort([2,53,1,16,26]));
選擇排序（selectionSort）
選擇排序是一種簡(jiǎn)單直觀的排序算法局荚，無(wú)論什么數(shù)據(jù)進(jìn)去都是 O(n2) 的時(shí)間復(fù)雜度。所以用到它的時(shí)候愈污，數(shù)據(jù)規(guī)模越小越好耀态。唯一的好處可能就是不占用額外的內(nèi)存空間了吧。
1. 算法步驟
- 首先在未排序序列中找到最性荼ⅰ（大）元素首装，存放到排序序列的起始位置
- 再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小（大）元素杭跪，然后放到已排序序列的末尾
- 重復(fù)第二步仙逻，直到所有元素均排序完畢
2. 動(dòng)圖演示
function sort(arr){
var len=arr.length;
var minId,temp;
for(var i=0;i<len-1;i++){
minId=i;
for(var j=i+1;j<len;j++){
if(arr[j]<arr[minId]){
minId=j;
}
}
temp=arr[i];
arr[i]=arr[minId];
arr[minId]=temp;
}
return arr;
}
console.log(sort([2,5,3,1,4]));
插入排序
1. 算法步驟
- 將第一待排序序列第一個(gè)元素看做一個(gè)有序序列，把第二個(gè)元素到最后一個(gè)元素當(dāng)成是未排序序列涧尿。
- 從頭到尾依次掃描未排序序列系奉，將掃描到的每個(gè)元素插入有序序列的適當(dāng)位置。（如果待插入的元素與有序序列中的某個(gè)元素相等姑廉，則將待插入元素插入到相等元素的后面缺亮。）
2. 動(dòng)圖演示
3. JavaScript 代碼實(shí)現(xiàn)
function sort(arr){
var len=arr.length;
var sortedId,sortingValue;
for(var i=1;i<len;i++){
sortedId=i-1;
sortingValue=arr[i];
while(sortedId>=0 && arr[sortedId]>sortingValue){
arr[sortedId+1]=arr[sortedId];//排序好的依次往后順移
sortedId=sortedId-1;//
}
arr[sortedId+1]=sortingValue;//最后把在排序的值賦給已排好的順下一位
}
return arr;
}
console.log(sort([2,10,3,1,4]));
歸并排序（Merge sort）
1. 算法步驟
- 申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和桥言，該空間用來(lái)存放合并后的序列
- 設(shè)定兩個(gè)指針萌踱，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
- 比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間号阿，并移動(dòng)指針到下一位置
- 重復(fù)步驟 3 直到某一指針達(dá)到序列尾
- 將另一序列剩下的所有元素直接復(fù)制到合并序列尾
2. 動(dòng)圖演示
3. JavaScript 代碼實(shí)現(xiàn)
function sort(arr){
var len=arr.length;
if(len<2){
return arr;
}
var middle=Math.floor(len / 2),
left=arr.slice(0,middle),
right=arr.slice(middle);
return merge(sort(left),sort(right));
}
function merge(left,right){
var result=[];
while(left.length && right.length){
if(left[0]<=right[0]){
result.push(left.shift());
}else{
result.push(right.shift());
}
}
while(left.length)
result.push(left.shift());
while(right.length)
result.push(right.shift());
return result;
}
console.log(sort([2,5,4,9,10,8,1]))
快速排序
1. 算法步驟
- 從數(shù)列中挑出一個(gè)元素并鸵，稱為 “基準(zhǔn)”（pivot）
- 重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面扔涧，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）园担。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作
- 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序
- 遞歸的最底部情形粉铐，是數(shù)列的大小是零或一疼约，也就是永遠(yuǎn)都已經(jīng)被排序好了。雖然一直遞歸下去蝙泼，但是這個(gè)算法總會(huì)退出程剥，因?yàn)樵诿看蔚牡╥teration）中，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去汤踏。
2. 動(dòng)圖演示
3. JavaScript 代碼實(shí)現(xiàn)
<!---表示還沒(méi)弄很懂织鲸，亂啊亂--->
function quickSort(arr, left, right) {
var len = arr.length,
partitionIndex,
left = typeof left != 'number' ? 0 : left,
right = typeof right != 'number' ? len - 1 : right;
if (left < right) {
partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex-1);
quickSort(arr, partitionIndex+1, right);
}
return arr;
}
function partition(arr, left ,right) { // 分區(qū)操作
var pivot = left, // 設(shè)定基準(zhǔn)值（pivot）
index = pivot + 1;
for (var i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index-1；
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function partition2(arr, low, high) {
let pivot = arr[low];
while (low < high) {
while (low < high && arr[high] > pivot) {
--high;
}
arr[low] = arr[high];
while (low < high && arr[low] <= pivot) {
++low;
}
arr[high] = arr[low];
}
arr[low] = pivot;
return low;
}
function quickSort2(arr, low, high) {
if (low < high) {
let pivot = paritition2(arr, low, high);
quickSort2(arr, low, pivot - 1);
quickSort2(arr, pivot + 1, high);
}
return arr;
}
console.log(quickSort([5,4,2,1,3,99]));
借來(lái)同學(xué)一個(gè)快速排序溪胶，很簡(jiǎn)潔
快速排序又稱為自私算法搂擦，它優(yōu)先讓每個(gè)元素找到自己所在的位置，每次排序都實(shí)現(xiàn)“比我大的都在我右邊哗脖，比我小的都在我左邊”而不去計(jì)較它們的位置關(guān)系瀑踢。具體做法為：先找一個(gè)基準(zhǔn)點(diǎn)（一般用第一個(gè)元素或者中間元素）然后數(shù)組被分為兩部分，如果選定值比它小才避，放左邊橱夭；比它大，放右邊桑逝。然后進(jìn)行反復(fù)比較棘劣，就可以實(shí)現(xiàn)效果。
function sort(array){
if(array.length<=1){
return array;
}
var len = Math.floor(array.length/2);
var cur = array.splice(len,1);
var left = [];
var right = [];
for(var i=0;i<array.length;i++){
if(cur>array[i]){
left.push(array[i]);
}else{
right.push(array[i]);
}
}
return sort(left).concat(cur,sort(right));
}
