js实现排序算法
2018-02-20 本文已影响0人
Jassi
本文实现了冒泡排序 选择排序和快速排序，本文中的优化并不彻底，快速排序的时间 并不一定总是下于其他方法的时间，运行结果在 链接jsbin
首先 随机生成一个list，作为被排序的对象
let list=[];
for(let i=0;i<10;i++){
list.push(randBetween(0,100));
}
function randBetween(L,R){
let num=Math.random()*R;
num=num.toFixed(0);
num=num%(R-L+1)+L
return num;
}
方法一 冒泡排序 ：每轮中两个相邻的数字进行比较 每次比较都进行交换
- 冒泡排序 一般
function bubbleSort1(list){
let length=list.length;
for(let last=length-1 ;last-1;last--){
timer=0;
for(let j=0;j<last;j++){
if(list[j]>list[j+1]){
let temp=list[j];list[j]=list[j+1];list[j+1]=temp;
}
}
}
return list
}
- 冒泡排序 优化 （在一般冒泡排序的基础上 当某一轮的交换次数为0时，说明顺序已经排好了，没有必要在继续剩余的循环）
function bubbleSort2(list){
let length=list.length;
let timer=1;
for(let last=length-1 ;last-1 && timer;last--){
timer=0;
for(let j=0;j<last;j++){
if(list[j]>list[j+1]){
timer++;
let temp=list[j];list[j]=list[j+1];list[j+1]=temp;
}
}
console.log('第'+(length-last)+'轮 交换'+timer+'次');
}
return list
}
- 冒泡排序 加强版（在优化的基础上，优化每一轮的排序，记住莫一轮中最后一个交换的位置，该位置后面的已经排序完成，没有必要继续查找，将次位置作为下一轮循环的终点）
function bubbleSort3(list){
let length=list.length;
let last=length-1;
let timer=1;
while(last && timer){
timer=0;let pos=0;
for(let j=0;j<last;j++){
if(list[j]>list[j+1]){
timer++;
pos=j;
let temp=list[j];list[j]=list[j+1];list[j+1]=temp;
}
}
last=pos;
console.log('第'+(pos)+'轮 交换'+timer+'次');
}
return list
}
方法二 选择排序：在每轮中 将选定位置的数值 与其后的数字进行比较 并狡交换位置
- 选择排序 一般(每次符合条件时 都进行交换)
function selectSort1(list){
let length=list.length;
for(let i=0;i<length-1;i++){
for(let j=i+1;j<length;j++){
if(list[i]>list[j]){
let temp=list[i];list[i]=list[j];list[j]=temp;
}
}
}
return list
}
- 选择排序 优化（在其后的数字中 找到最值，将最值与选定的位置交换顺序，这样在每轮中只进行一起交换）
function selectSort2(list){
let length=list.length;
for(let i=0,min=i;i<length-1;i++){
for(let j=i+1;j<length;j++){
if(list[min]>list[j]){
min=j
}
}
let temp=list[i];list[i]=list[min];list[min]=temp;
}
return list
}
方法三 快速排序：将<=mid（每次将最right的值作为mid值）的值放在left部分，>mid的值放在right部分，然后 分别对left和right部分进行快速排序。mid所指向的位置 就是最终排序完成时 在数组中的位置，所以 下一轮排序中，无需将其放在排序列表中；
var time=1
function quickSort(list, left=0, right=list.length-1) {
if (left < right) {
let mid = left - 1;
for (let i = left; i <= right; i++) {
if (list[i] <= list[right]) { //关键点=，如果不设置等号 rightIndex对应的位置会不参与排序，那么right那半部分会进入死循环
mid++;
console.log(`第${time}轮${mid}和${i}互换${list}`);
let temp = list[mid];
list[mid] = list[i];
list[i] = temp;
}
}
time++
quickSort(list, left, mid-1 );//这里mid-1很关键，不能设为mid,如果设置为mid 那么会造成第二次调用该方法时 left部分的最right的值一直大于 left部分的值，left部分的值进入死循环
quickSort(list, mid + 1, right);
}
return list;
}
console.log('排序后',quickSort(list));
方法四 排序二叉树：
function BinaryTree(){
var Node=function(key){
this.key=key;
this.left=null;
this.right=null;
}
this.insert=function(key){
let node=new Node(key)
if(!this.root){
this.root=node;
}else{
insertNode(this.root,node)
}
}
this.root=null;
var insertNode=function(node,newNode){
if(node.key<newNode.key){
if(!node.right){
node.right=newNode
}else{
insertNode(node.right,newNode)
}
}
if(node.key>newNode.key){
if(!node.left){
node.left=newNode
}else{
insertNode(node.left,newNode)
}
}
}
var inorderTravsNode=function(node,callback){
if(!node){return}
inorderTravsNode(node.left,callback);
callback(node.key);
inorderTravsNode(node.right,callback)
}
this.inorderTravs=function(callback){
inorderTravsNode(this.root,callback)
}
}
var arr=[8,11,13,2,6,17,90,20]
var tree=new BinaryTree()
arr.forEach(key=>{
tree.insert(key)
})
var cb=function(key){
console.log(key)
}
tree.inorderTravs(cb)
方法五 插入排序：
function insertSort(arr){
let n=arr.length;
for(let i=1;i<n;i++){
let tem=arr[i];
let j=i-1;
while((j>=0)&&(arr[j]>tem)){
arr[j+1]=arr[j];
j--
}
arr[j+1]=tem
}
return arr
}
