前端复习企划13-排序算法
排序算法
比较
对于评述算法优劣术语的说明
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
内排序：所有排序操作都在内存中完成；
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
时间复杂度: 一个算法执行所耗费的时间。
空间复杂度: 运行完一个程序所需内存的大小。
算法比较：
二分查找
假设一个数组已经排好序了，现在要在数组里找一个数flag的位置。
首先先找到长度中间位置，通过与中间位置的数比较，比中间值大在右边找，比中间值小在左边找。然后再在两边各自寻找中间值，持续进行，直到找到全部位置。
//arr排好序
function binarySearch(arr,flag,Start,End){
let end =End||arr.length-1;
let start=Start||0;
let m=Math.floor((start+end)/2);
if(arr[m]==flag){
return m;
}
if(flag<arr[m]){
return binarySearch(arr,flag,0,m-1);
}else{
return binarySearch(arr,flag,m+1,end);
}
return false;
} 非递归的方法也写一个吧
function binarySearch(arr,flag){
let r=arr.length-1,//数组下标长度减一
l=0;
while(l<=r){
let m=Math.floor((h+1)/2);
if(data[m]==flag){
return m;
}
if(flag>data[m]){
l=m+1;
}else{
r=m-1;
}
}
return false;
} 冒泡排序
比较相邻两个元素的，如果前一个比后面的大，就交换位置，第一轮之后最后一个元素是最大的一个，按照这种方法依次比较。
function bubbleSort(arr){
for(let i=arr.length-1;i>=0;i--){
for(j=0;j<i;j++){
if(arr[j]>arr[j+1]){
let tmp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=tmp;
}
}
}
return arr;
} 快速排序
是利用二分查找对冒泡排序的改进，选一个元素作为基准，把数字分为两部分，一部分全部比它小，一部分全部比它大，然后递归调用，在两部分都进行快排。
function quickSort(arr){
if(arr.length<=1){
return arr;
}
//中间位置
let middle=Math.floor(arr.length/2);
let flag=arr.splice(middle,1)[0];//取出中间元素
let left=[],right=[];
for(let i=0;i<arr.length;i++){
if(arr[i]<flag){
left.push(arr[i]);
}else{
right.push(arr[i]);
}
}
return quickSort(left).cocat([flag],quickSort(right));
} 插入排序
从第一个元素开始，该元素认为已经被排序了，取出下一个元素。在已经排序的元素序列中从后向前扫描，如果大于新元素，那么就把这个元素移动到下一个位置。直到找到已排序的元素小于或者等于新元素的位置，将新元素插入下一个位置。依次进行。（其实就是最开头的元素当作是有序数列，后面的元素是无序的，然后从第一个开始往前面插入）
function insertSort(arr){
//从第一个开始（遍历无序数列）
for(let i=1;i<arr.length;i++){
if(arr[i]<arr[i-1]){
let guard=arr[i];//无序数列中的第i个元素
let j=i-1;//有序数列的最后一个位置
arr[i]=arr[j];
while(j>=0&&guard<arr[j]){
arr[j+1]=arr[j];
j--;
}
arr[j+1]=guard;
}
}
} 选择排序
首先在未排序的队里找到最小的元素，存放到排序序列中的起始位置，然后从剩下没有排序的元素中找最小的元素，放到已排序的队尾
function selectionSort(arr){
let len=arr.lengrh;
let index,temp;
for(let i=0;i<len-1;i++){
index=i;
for(let j=i+1;j<len;j++){
if(arr[j]<arr[index]){
index=j;//存最小索引
}
}
tmp=arr[j];
arr[i]=arr[index];
arr[index]=temp;
}
return arr;
} 希尔排序
用于较大规模无序数据。
先将整个待排序的数据集分割为若干组，然后对每一个组分别进行直接插入排序。此时每个组内插入排序所作用的数据量小，效率比较高。
排序完后基本上数组，小元素大体在前，大元素大体在后，然后缩小增量，继续分组，此时虽然每个分组元素个数变多了，但是数组变有序了，效率也是比较高的。
用的比较少，篇幅稍微长一些。
这个算法的图解可以看这篇博客，用一问一答的方式把它描述得非常有趣了。专业一点的描述可以看这篇博客，动图把过程说的非常清楚。
也可以直接看下面的动图（摘自上面的博客）
function shellSort(arr){
var len=arr.length;
var tmp,gap=1;
while(gap<len/5){
gap=gap*5+1;
}
for(gap;gap>0;gap=Math.floor(gap/5)){
for(var i=gap;i<len;i++){
tmp=arr[i];
for(var j=i-gap;j>=0&&arr[j]>tmp;j-=gap){
arr[j+gap]=arr[j];
}
arr[j+gap]=tmp;
}
}
return arr;
} 归并排序
一种稳定排序方法，将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使序列段间有序。
其实也是二分的思想，只不过是在二分的基础上，先分段，段内再排，然后把每一段拼接起来。
这篇博客里有非常仔细的图片分析。这个需要新申请一个数组来做，所以自然是O(n)的空间复杂度啦！
从上面这篇博客偷了个动图帮助理解：
function mergeSort(arr){
//自上而下递归
var len =arr.length;
if(len<2){return arr}
var middle=Math.floor(len/2),
left=arr.slice(0,middle),
right=arr.slice(middle);
return merge(mergeSort(left),mergeSort(right));
}
function merge(left,right){
var 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;
} 堆排序
堆排序利用堆的数据结果设计的排序算法。堆是一个近似完全二叉树的结构，同时满足：子节点的键值或索引总是小于/大于父节点。
function heapSort(arr){
if(Object.prototype.toString.call(arr).slice(8,-1)==='Array'){
var heapSize=arr.length,temp;//建堆
for(var i=Math.floor(heapSize/2)-1;i>=0;i--){
heapify(arr,i,heapSize);
}
for(var j=heapSize-1;j>=1;j--){
//堆排序
temp=arr[0];
arr[0]=arr[j];
arr[j]=temp;
heapify(arr,0,--heapSize);
}
return arr;
}else{
throw TypeError('Input not Array');
}
}
function heapify(arr,x,len){
if(Object.prototype.toString.call(arr).slice(8,-1)==='Array'&&typeof x==='number'){
var l=x*2+1,
r=x*2+2,
largest=x,
temp;
if(l<len&&arr[l]>arr[largest]){
largest=l;
}
if(r<len&&arr[r]>arr[largest]){
largest=r;
}
if(largest!=x){
temp=arr[x];
arr[x]=arr[largest];
arr[largest]=temp;
heapify(arr,largest,len);
}
}else{
throw TypeError('Input Illegal');
}
} 计数排序
使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数，然后根据数组C来将A中的元素排到正确位置。（只能对整数排序）
function countingSort(arr){
var len=arr.length,B=[],C=[],min=max=arr[0];
for(var i=0;i<len;i++){
min=min<arr[i]? min:arr[i];
max=max>arr[i]? max:arr[i];
C[arr[i]]=C[arr[i]]?C[arr[i]]+1:1;
}
for(var j=min;j<max;j++){
C[j+1]=(C[j+1]||0)+(C[j]||0);
}
for(var k=len-1;k>=0;k--){
B[C[arr[k]]-1]=arr[k];
C[arr[k]]--;
}
return B;
} 桶排序
假设输入的数据服从均匀分布，将数据分到有限数量的桶里。每个桶再分别排序。（可以再使用别的排序算法，或者递归继续用桶排序）
function bucketSort(arr,num){
if(arr.length<=1) return arr;
let len=arr.length;
let buckets=[],result=[],space,n=0;
min=max=arr[0];
let regex='/^[1-9]+[0-9]*$/';
for(let i=1;i<len;i++){
min=min<=arr[i]?min:arr[i];
max=max>=arr[i]?max:arr[i];
}
space=(max-min+1)/num;//索引减法+1
for(let j=0;j<len;j++){
let index=Math.floor((arr[j]-min)/space);
if(buckets[index]){
//不是空桶的话，就插入排序
var k=buckets[index].length-1;
while(k>=0&&buckets[index][k]>arr[j]){
buckets[index][k+1]=buckets[index][k];
k--;
}
buckets[index][k+1]=arr[j];
}else{
//空桶，初始化
buckets[index]=[]
buckets[index].push(arr[j]);
}
}
while(n<num){
result=result.concat(buckets[n]);
n++;
}
return result;
} 基数排序
基数排序是按照地位先排序，然后收集；再按照高位排序，然后收集；以此类推，直到最高位。有时候有些属性有优先级顺序，先按低优先级排序，在按高优先级排序。
最后次序就是高优先级在前，高优先级相同的低优先级高的在前。
大意就是说：比如[53 3 542 748 14]
先按个位排序就是[542 053 003 014 748]
然后按照十位排序，[003 014 542 748 053]
然后按照百位排序，[003 014 053 542 748]
因为它是分别排序分别收集的，所以是稳定的。
function radixSort(arr,maxDigit){
let mod=10,dev=1,counter=[];
for(let i=0;i<maxDigit;i++,dev*=10,mod *=10){
for(let j=0;j<arr.length;j++){
let bucket=parseInt((arr[j]%mod)/dev);
if(counter[bucket]==null){
counter[bucket]=[];
}
counter[bucket].push(arr[j]);
}
var pos=0;
for(let j=0;j<counter.length;j++){
let value=null;
if(counter[j]!=null){
while((value=counter[j].shift())!=null){
arr[pos++]=value;
}
}
}
}
return arr;
} 注：这三种算法用到的比较少，但上面这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
- 基数排序：根据键值的每位数字来分配桶
- 计数排序：每个桶只存储单一键值
- 桶排序：每个桶存储一定范围的数值
