1. 冒泡排序
冒泡排序的思想就是不断进行相邻交换,较小的数字如同气泡般慢慢浮到上面。
优化:如果在排第i个元素时,没有交换任何元素,则排序已完成,无需继续遍历
function mSort(array){
var flag=true; //是否还要继续排序,排序优化
for(var i=0;i<array.length-1 && flag;i++){
flag=false;
for(var j=array.length-2;j>=i;j--){
if(array[j]>array[j+1]){
var temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
flag=true;
}
}
}
}
最好情况:O(n)
最坏情况:O(n^2)
平均情况:O(n^2)
2. 选择排序
选择排序的思想是每次遍历找到最小的元素,然后和相应位置的元素交换位置。
function sSort(array){
for(var i=0;i<array.length-1;i++){
//查找最小的元素
var min=i;
for(var j=i+1;j<array.length;j++){
if(array[j]<array[min]){
min=j;
}
}
//交换位置
var temp=array[i];
array[i]=array[min];
array[min]=temp;
}
}
最好情况:O(n^2)
最坏情况:O(n^2)
平均情况:O(n^2)
略优于冒泡排序。
3.插入排序
插入排序的主要思想是将一个记录插入到已经安排好的有序表中,需要一个辅助空间来存放这个记录,以方便前面的元素进行右移。
function iSort(array){
for(var i=1;i<array.length;i++){
var temp=array[i];
//将前面大于其的元素右移
for(var j=i-1;array[j]>temp && j>=0;j--){
array[j+1]=array[j];
}
//将记录插入对应位置
array[j+1]=temp;
}
}
最好情况:O(n)
最坏情况:O(n^2)
平均情况:O(n^2)
插入排序比冒泡和简单选择排序的性能要好。
4.快速排序
快速排序的主要思想是,通过一趟排序将待排序的记录分割成独立的两部分,其中一部分的关键字都比另一部分的关键字小,则可以对这两部分继续进行排序,以达到整个序列有序的状态。
最主要的就是要实现一个partition函数,可以选取一个枢轴,并将其放在一个合适的位置,使其左侧值都比它小,右侧值都比它大。
//快速排序
function qSort(array,low,high){
if(low<high){
var pivot=partition(array,low,high);
//递归排序低子表和高子表
qSort(array,low,pivot-1);
qSort(array,pivot+1,high);
}
}
//选取一个关键字,放置到合适的位置,左侧值都比其小,右侧值都比其大
function partition(array,low,high){
//设置枢值为第一个元素
var pivotkey=array[low];
//交替向中间扫描,直到两个指针指向同一个位置,即为枢值的位置
while(low<high){
while(high>low && array[high]>=pivotkey){
high--;
}
swap(array,low,high);
while(low<high && array[low]<=pivotkey){
low++;
}
swap(array,low,high);
}
return low;
}
//交换数组中a和b的位置
function swap(array,a,b){
var temp=array[a];
array[a]=array[b];
array[b]=temp;
}
var array=[5,4,3,2,1];
qSort(array,0,array.length-1);
console.log(array);
快速排序的时间性能取决于其快速排序递归的深度,一般partition每次划分都比较均匀时,其递归树的深度为log2n+1,而每次partition划分时,需要对数组的部分做扫描,每一层的时间复杂度为n,所以其时间复杂度为O(nlogn)。
由于关键词的比较和交换时跳跃进行的,因此,快速排序是一种不稳定的排序方法。
5.归并排序
基本思想为分治策略,先将数组进行划分,然后再进行合并,关键点是实现两个数组的合并
//合并两个数组
function merge(left,right){
var res=[];
while(left.length>0 && right.length>0){
if(left[0]<=right[0]){
res.push(left.shift());
} else {
res.push(right.shift());
}
}
return res.concat(left).concat(right);
}
//归并排序
function sort(arr){
//直到数组的长度为1,则终止递归
if(arr.length===1){
return arr;
}
var mid=Math.floor(arr.length/2);
var left=arr.slice(0,mid);
var right=arr.slice(mid);
return merge(sort(left),sort(right));
}