排序可以分为比较排序和非比较排序。比较排序是指在排序过程中，会将所有元素的值进行比较，将小的或者是大的按照一个规律进行“运动”，最终形成一个有序的数组；非比较排序是利用自然数本身递增的特点，记录待排序数组中的元素以及个数，按照自然数进行从小到大输出（该数组存在该自然数一次以上）。
冒泡排序
冒泡排序是比较排序的一种。在两个相邻元素之间进行两两比较，使得比较大的数不断上升到右边，就像是气泡，越往上冒越大，经过每个数字至少冒泡一次的比较，可以使得右边的数从大到小排列。
Bubble-Sort-3.png
Array.prototype.bubbleSort = function() {
let len = this.length;
let count = 0;
if(len<2 || !this) {
return this;
}
while(count < len-1) {
let swapFlag = false;
for(var j=0;j<len-1;j++) {
if(this[j] > this[j+1]) {
var temp = this[j];
this[j] = this[j+1];
this[j+1] = temp;
swapFlag = true;
}
}
if(!swapFlag) break;
}
return this;
}
选择排序
选择排序也是比较排序的一种。从数组第一个元素位置开始，每次将剩余最小的元素放到当前的位置上，这样经过数组长度次数的比较与元素选择，就可以将数组从小到大进行排序。
selection sort.png
Array.prototype.selectSort = function() {
let count = 0;
while(count < this.length) {
let minNum = this[count];
let index = count;
for(let i=count+1; i<this.length;i++) {
if(this[i] <= minNum) {
minNum = this[i];
index = i;
}
}
this[index] = this[count];
this[count] = minNum;
count++;
}
return this;
}
插入排序
插入排序也是比较排序的一种。它的原理和平时生活里起扑克牌一样，每次拿到一张牌，将它插入后面比它大，前面比它小的位置上，每张牌都是如此，当牌拿完后，得到的就是一副从小到大的牌。
insertion-sort-algorithm.jpg
Array.prototype.insertSort = function() {
for(let count = 1;count < this.length; count++) {
let minNum = this[count];
let temp = count -1;
while(temp > 0 && this[temp] > minNum) {
this[temp+1] = this[temp];
temp--;
}
this[temp+1] = minNum;
}
return this;
}
快速排序
快速排序是比较排序的一种。它运用了分治的思想。每次选取数组的第一个作为数字基准，比基准小的排到基准左边，比基准大的，排到基准的右边，这样一来，基准的位置是唯一确定的。然后运用递归，将左边再次作为一个数组进行排序，选取基准，左右分开，不断递归。
javascript-quicksort.jpg
Array.prototype.quickSort = function() {
const len = this.length;
if(len < 2) return this;
let basic = this[0], left = [], right = [];
for(let i =1;i<len; i++) {
if(this[i] <= basic) {
left.push(this[i]);
}else {
right.push(this[i]);
}
}
return left.quickSort().concat(basic, right.quickSort());
}
计数排序
计数排序是非比较排序，它是将所有的数组元素都记录，用数组元素值作为键，元素出现的次数作为值，存储在一个类似于键值对的map类型中，当遍历完后，存储数组中有该值，则将该值从小到大按照次数输出，这样就形成了一个有序的数组。
counting_sort_algorithm.png
Array.prototype.countSort = function() {
const countArr = [];
for(let i=0;i<this.length;i++) {
if(countArr[this[i]]) {
countArr[this[i]]++;
}else {
countArr[this[i]] = 1;
}
}
const resultArr = [];
for(let j =0;j<countArr.length;j++) {
while(countArr[j]>0) {
resultArr.push(j);
countArr[j]--;
}
}
return resultArr;
}
