排序对比
冒泡排序
- 设置两个变量
i,j，i从0~length-1，j从0~length-i-1，进行遍历，外部循环i执行一次，内部循环j执行多次，每次都是从0开始比较当前元素和后一个元素，如果当前元素较大，则交换 - 结果：每次都是找到当前序列的最大一个元素放在末尾的固定位置，所以内部循环的
length=length-i-1，因为后面的元素已经不需要在遍历，i共执行length-1次
function bubblesort(array) {
let len = array.length;
for (let i = 0; i < len - 1; i++) {
for (let j = 0; j < len - i - 1; j++) {
if (array[j] > array[j + 1]) {
let temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
return array
}
let array = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 4];
console.log(bubblesort(array));
选择排序
- 设置三个变量
i,j,minIndex,i从0~length-1,j从i+1~length，minIndex每次循环开始都指向当前的i,内部循环比较j指向的元素与minIdex指向的元素的大小，然后将minIndex指向找到的最小元素，如果minIndex!=i说明找到，则交minIndex与i所指的元素 - 结果是每次都会在未排序列中找到最小元素，然后放到未排序列的首部
function selectSort(array) {
let len = array.length;
let minIndex,temp;
for(let i = 0;i<len-1;i++){
minIndex = i;
for(let j = i+1;j<len;j++){
if(array[j]<array[minIndex]){
minIndex=j;
}
}
if(minIndex!=i){
temp=array[i];
array[i]=array[minIndex];
array[minIndex]=temp;
}
}
return array;
}
let array = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 4];
console.log(selectSort(array));
直接插入排序
- 设置三个变量
i,j,key，默认第一个有序，所以i从1~length，每次循环都将j = i - 1，key = arr[i]，key保存当前的值，j指向前一个值，在j>=0的时候，比较前一个值和当前值的大小，如果前一个值大，则往后挪，同时j--，直到j<0或者前一个值小，说明当前元素已经找到了正确位置，就把key赋值给当前有序序列的末尾也就是j+1 - 结果是每次循环都是将当前元素从后往前插入到前面的有序序列中，每次循环有序序列个数+1
function insertSort(array) {
let len = array.length;
let key;
for (let i = 1; i < len; i++) {
key = array[i];
let j = i - 1;
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
}
return array;
}
let array = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 4];
console.log(insertSort(array));
快速排序
- 首先判断，如何数组中只有一个元素，则返回，否则，就找到中间元素为基准，比基准小的放
left数组，比基准大的放right数组，然后递归调用
function quicksort(array) {
if(array.length<=1){
return array;
}
let index = Math.floor(array.length/2);
let num = array.splice(index,1);
let left=[],right=[];
for(let i = 0;i<array.length;i++){
if(array[i]<num){
left.push(array[i]);
}
else {
right.push(array[i]);
}
}
return quicksort(left).concat(num,quicksort(right));
}
let array = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 4];
console.log(quicksort(array));
归并排序（自上而下）
- 采用分治法，把长度为
n的序列分成两个长度为n/2的子序列，然后对这两个子序列分别采用归并排序，最终再进行合并
function mergeSort(array) {
if (array.length < 2) {
return array;
}
let middle = parseInt(array.length / 2);
let left = array.slice(0, middle);
let right = array.slice(middle);
return merge(mergeSort(left), mergeSort(right))
}
function merge(left,right) {
let 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;
}
let array = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 4];
console.log(mergeSort(array));
参考文章推荐
十大经典排序算法的 JS 版
