JavaScript排序专题
2019-05-26 本文已影响0人
焦糖大瓜子
冒泡排序
- 冒泡思路：
比较任何两个相邻的项目，如果第一个比第二个大，则交换顺序，这样最大值就是气泡一个，升至表面。
先定义一个数组中用到交换顺序的函数：
// left和right表示索引值
function swap(array, left, right) {
let rightValue = array[right]
array[right] = array[left]
array[left] = rightValue
}
// ES6用法
function swap(array, left, right) {
[array[right], array[left]] = [array[left], array[right]];
}
- 代码实现
冒泡排序两重循环：
- 外循环，循环一圈，用于遍历到数组的每一个元素
- 内循环，用于比较两个元素大小，循环一圈，将最大值放到最后，再循环一圈，将第二大值放到倒数第二的位置。
var array = [12, 22, 2,4, 6, 1,45, 56];
function bubbleSort (array) {
var length = array.length;
for (var i = 0; i < length; i++) {
for (var j = 0; j < length-1; j++) {
if(array[j] > array[j+1]){
swap(array, j, j+1)
}
};
};
console.log(array);
}
- 代码优化
冒泡的优化的地方是内循环，因为内循环没循环一次，将会确定最大值、第二大值，依次类推。所以没有必要比较已经确定顺序的元素，即内循环只需要比较array.length-i个元素，循环次数为array.lenght-i-1;
优化代码如下：
var array = [12, 22, 2,4, 6, 1,45, 56];
function bubbleSort (array) {
var length = array.length;
for (var i = 0; i < length; i++) {
for (var j = 0; j < length-i-1; j++) {
if(array[j] > array[j+1]){
swap(array, j, j+1)
}
};
};
console.log(array);
}
选择排序
- 选择的思路：
选择排序算法是一个原址比较排序算法。大致思路就是，找到数据结构中最小值，然后放到第一位，接着找到第二小的值，放到第二位置。
那么如何通过遍历去寻找数组元素中的最小值？
function selectionSort (array) {
var smallIndex;
for(let i=0; i< array.length-1; i++){
// 循环寻找最小值
smallIndex = i;
for (let j = i + 1; j < array.length; j++) {
if(array[smallIndex] > array[j]){
smallIndex= j;
}
}
if(i !== smallIndex){
swap(array, i, smallIndex)
}
}
console.log(array)
}
- 代码理解：
- 外循环， i=0时，假定array[i]就是最小值，然后拿这个值去跟还没确定排序位置的元素比较。外循环，每循环一次，找出第i小的值（i从0开始算）。
- 内循环，会寻找出当前数组中还没被选中元素的最小值，所以已经被选中的排序的元素，索引值index < i的，是需要被排除在外的，只比较索引值i和比i还大的元素。
插入排序
-
插入排序思路：
想象一下打扑克牌，一上手，从左到右边还是乱序的，现在需要从到小排个序。
假定第一张牌（最左）位置已经确定，
然后看第二张（左2），第2张和第1张比较，如果第2张和第1张比大，则将第2张插入到左1的位置
然后看第三张（左3），跟第1，2张比较，选择插入位置 -
代码实现：
- 使用一次for循环即可为元素找到自己的位置
- 但是数组索引需要重新编号，如何实现
function insertSort (array) {
let newArr = [];
let j;
// 怎么寻找array[i]的位置
for(let i=1; i< array.length; i++){
j = i;
tmp = array[i]
while(j> 0 && array[j-1] < tmp){
array[j] = array[j-1];
j--;
}
array[j] = tmp;
}
console.log(array)
}
- 代码理解：
－ 从第二张牌开始，i=1,那第二张牌（arr[i]）与第一张牌（arr[j-1]）比较, 如果第二张牌比第一张大，将第二张牌放到第一张牌的位置， 重新给第二张牌重新编号。重新编号使用while循环。
归并排序
......
快速排序
......
