继上一篇O(n^2)的排序算法后,这一篇主要记录O(n*logn)的排序算法
1.快排(快速排序)
这一算法的核心思想为,先随机选一个数作为标兵或者说是标记(这个数一般来说选择该无序数组的中间那个元素;此处笔者选取第一个实现算法,当选取完毕后以此标兵为参照将比这个数大的放到他的右边,比他小的放到左边.这样一趟排序过后就能让这个标记左边的数比他小,右边的数都比他大.下一趟排序则分别选取他的左半边数组和右半边数组重复之前的操作(此操作一般由递归实现)当传入的区间只有一个元素的时候那么开始返回不再继续调用函数自身(即为递归的终止条件)因为只有一个数字是必定有序的
递归实现代码如下:
//快速排序(递归)
function QuickSort(arr,start = 0,end = arr.length-1){
if(start<end){//递归结束条件
let [key,l,r] = [parseInt((start+end)/2),start,end];//key为标记的值,l和r 分别表示左边的下标和右边的下标
while(l<r){//当左右下标相遇即完成一趟排序,停止循环
while(l<r && arr[r] >= key){//从后往前找,如果对应下标的数比标记大则不做操作,下标继续前移
r--;
}//循环完成此时arr[r]
//而arr[l]的的值已经被key保存所以下一步则应该找出一个比key大却在key的左边的数放入arr[r]的位置
while(l<r && arr[l] <= key){
l++;
}
[arr[r],arr[l]] = [arr[l],arr[r]];
//这样一次循环就可以让一个在key左边比key大的数放到key的右边,比key小的放到左边
}
QuickSort(arr,start,l-1);//递归调用 -1 是为了避免区间重复
QuickSort(arr,l+1,end);
}
}
下图为将十万倒序数组变为正序的耗费时间:
下面列出非递归版本的快排:
function QuickSort2(arr,start = 0,end = arr.length-1){
let mid = [start,end];//建立一个数组用于存放需要快排的区间的参数,这样循环调用即可
if(start<end){
while(mid.length){//当参数数组中没有参数则停止循环
let [l,r] = [mid.shift(),mid.shift()];//取出数组中最前面的两个数,并对此区间上的数进行快排
let [low,height] = [l,r];
let key = arr[parseInt((l+r)/2)];//选取标兵
while(l<r){
while(l<r && arr[r] >= key){
r--;
}
arr[l] = arr[r];
while(l<r && arr[l] <= key){
l++;
}
arr[r] = arr[l];
arr[l] = key;
}
//当两个参数不相等,即该区间不止一个数时,则将下一个区间的参数存入参数数组
if(low<l)
mid.push(low,l);
if(l+1<height)
mid.push(l+1,height);
}
}
}
对十万逆序数组排序耗时如下:
由于非递归版本数组方法调用较多,故此花费时间略久于递归版本
2.希尔排序
希尔排序和快排一样都是不稳定排序,快速排序的不稳定是因为,标兵的选取并不能直接选取到刚好是区间中中间大小的数,所以当每个区间的第一个数刚好都是该区间最小的数,那么达到快排的最坏情况(以区间的第一个数为标兵为例). 而希尔排序其核心是插入排序所以当数组刚好为逆序时其效率最低,此时也就是希尔排序的最坏情况但与快排不同的是最坏情况的希尔排序速率并不会下降明显.
希尔排序算法的和心在于,利用了当待排序数组基本有序的时候插入排序效率极高的原理,即选取不同的步长对其进行插排,当步长为一时则与普通的插排没有区别,而效率的提升在于经过前期数次的插排使数组基本有序
其代码如下:
function ShellSort(arr) {
let steep = parseInt(arr.length / 2);//计算步长
let length = arr.length;
let tarr = [];//用于存放按步长分出的数组的临时数组
while (steep) {
//只有步长大于1才分组 否则直接插排
if ( steep > 1) {
for (let i = 0; i < steep; i++) {
//此循环将数组分组
for (let j = i; j < length; j = j + steep) {
tarr.push(arr[j]);
}
InsertionSort(tarr);//将分好组的数组进行插排
for (let j = i; j < length; j = j + steep) {
arr[j] = tarr.shift();
}
//排好序的数组映射回原数组
tarr.length = 0;//清空临时数组
}
}else
InsertionSort(arr);
steep = parseInt(steep / 2);
}
}
普通插排耗时如下:
希尔排序耗时如下:
3.归并排序
与快排和希尔排序不同的是归并排序是稳定排序
其核心思想在于当数组只有一个数时肯定是有序的,所以现将数组拆分为一个一个的数,然后在合并的过程中对齐排序,其弊端在于需要占用一个与原数组等长的临时数组空间来存放变量
递归版代码如下:
//归并排序(递归)
function Merge(arr,start,mid,end,temp) {//此函数用于合并数组
let [l,r] = [start,mid+1];//l标示左边需合并数组的初始下标,r同理标示右边数组的初始下标
while(l<=mid && r <= end){
if(arr[l]<=arr[r])
temp.push(arr[l++]);
else
temp.push(arr[r++]);
}
while(l<=mid){
temp.push(arr[l++]);
}
while(r<=end){
temp.push(arr[r++]);
}
while(start<=end){//将排好的临时数组中的数据复制回原数组
arr[start++] = temp.shift();
}
}
function RecursiveSort(arr,start = 0,end = arr.length-1,temp = []){
if(start < end){
let mid = parseInt((start+end)/2);//将数组分为两半
RecursiveSort(arr,start,mid,temp);
RecursiveSort(arr,mid+1,end,temp);
Merge(arr,start,mid,end,temp);//递归的回调途中进行数组的合并
}
}
递归版耗时:
非递归代码:
function RecursiveSort2(arr,start = 0,end = arr.length-1){
let mid = [start,end];
let pra = [];
while(mid.length){//获取参数列表
let [l,r] = [mid.shift(),mid.shift()];
pra.push(l,r);
let m = parseInt((l+r)/2);
if(m>l)
mid.push(l,m);
if(r>m+1)
mid.push(m+1,r);
}
while(pra.length){
let [r,l] = [pra.pop(),pra.pop()];
let m = parseInt((l+r)/2);
Merge(arr,l,m,r,[]); //此函数见上文
}
}
非递归耗时如下:
总结:
快排在数据量大时的优势较为明显,希尔排序适用于中量数据,而当空间要求不限时归并也不失为一种选择