排序可以分为比较排序和非比较排序。比较排序是指在排序过程中,会将所有元素的值进行比较,将小的或者是大的按照一个规律进行“运动”,最终形成一个有序的数组;非比较排序是利用自然数本身递增的特点,记录待排序数组中的元素以及个数,按照自然数进行从小到大输出(该数组存在该自然数一次以上)。
冒泡排序
冒泡排序是比较排序的一种。在两个相邻元素之间进行两两比较,使得比较大的数不断上升到右边,就像是气泡,越往上冒越大,经过每个数字至少冒泡一次的比较,可以使得右边的数从大到小排列。
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.pngArray.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.jpgArray.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.jpgArray.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
类型中,当遍历完后,存储数组中有该值,则将该值从小到大按照次数输出,这样就形成了一个有序的数组。
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;
}
网友评论