- 冒泡排序
比较两个相邻的数，不过不符合排序规则则交换这两个数的位置（比如升序，前一个比后一个大，则交换位置）。这样一轮下来，最大（或最小）的数就在最后了。在对数组剩下的数重复上述过程，直到排序完成。
function bubbleSort(arr){
for(var i=0; i<arr.length; i++){
for(var j=0; j<(arr.length-i); j++){
if(arr[j] > arr[j+1]){
swap(arr,j,j+1)
}
}
}
return arr
}
function swap(arr,left,right){
var temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
var arr = [1,5,2,9,2,3,45,21,64,23,7,5]
bubbleSort(arr)
console.log(arr)
- 选择排序
与冒泡排序类似，也是比较两个相邻的数，但不交换，只是对最小（或最大）的数进行标记，一轮比较完毕后再将最小（或最大）的数放在正确的位置。
function selectSort(arr){
for(var i=0; i<arr.length; i++){
var min = i;
for(var j=i+1; j<arr.length; j++){
if(arr[j]<arr[min]){
min = j
}
}
if(i!= min){
swap(arr,i,min)
}
}
}
function swap(arr,left,right){
var temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
var arr = [1,5,2,9,2,3,45,21,64,23,7,5]
selectSort(arr)
console.log(arr)
- 插入排序
插入排序有点类似打牌时，我们一张一张的拿牌，按顺序放好，新拿的牌再插入到已经排好序的牌里。
function insertSort(arr){
for(var i=0; i<arr.length; i++){
var value = arr[i];
for(j=i-1; j>-1&&arr[j]>value; j--){
arr[j+1]=arr[j]
}
arr[j+1] = value//因为在执行j--后不满足条件才退出for循环，所以这时是arr[j+1]
}
return arr
}
var arr = [1,5,2,9,2,3,45,21,64,23,7,5]
insertSort(arr)
console.log(arr)
- 合并排序
其基本思想是将两个已经排序好的数组合并，要比对所有的元素排序来的快。因此，可将数组依次拆开，再不断的两两合并，直至排序完成。
function mergeSort(arr){
if(arr.length < 2){
return arr
}
var middle = Math.floor(arr.length/2)
var left = arr.slice(0,middle);
var right = arr.slice(middle);
return merge(mergeSort(left),mergeSort(right))
}
function merge(arrLeft,arrRight){
var result = [];
var i = 0, j = 0;
while(i < arrLeft.length && j < arrRight.length){
if(arrLeft[i] < arrRight[j]){
result.push(arrLeft[i++])
}else{
result.push(arrRight[j++])
}
}
return result.concat(arrLeft.slice(i)).concat(arrRight.slice(j))
}
var arr = [1,5,2,9,2,3,45,21,64,23,7,5]
mergeSort(arr)
console.log(mergeSort(arr))
- 快速排序
先确定一个支点，然后将小于支点的值放在支点左侧，将大于支点的值放于支点的右侧。对左右两侧不断重复该过程，直至排序完成。
function quickSort(arr,left,right){
if(arr.length< 2){
return arr
}
if(typeof left != 'number'){
left = 0
}
if(typeof right != 'number'){
right = arr.length-1
}
var index = partition(arr,left,right)
if(left<index-1){
quickSort(arr,left,index-1)
}
if(index<right){
quickSort(arr,index,right)
}
return arr
}
function partition(arr,left,right){
var middle = Math.floor((left+right)/2)
var pivot = arr[middle]
var i = left, j =right;
while(i<=j){
while(arr[i]<pivot){
i++
}
while(arr[j]>pivot){
j--
}
if(i<=j){
swap(arr,i,j)
i++
j--
}
}
return i
}
function swap(arr,left,right){
var temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
var arr = [1,5,2,9,2,3,45,21,64,23,7,5]
quickSort(arr)
console.log(arr)
(先这样吧，困死，明天在把桶排和基数排序补上)
