JS十大排序算法

排序算法说明:
(1)对于评述算法优劣术语的说明
稳定:如果a原本在b前面,而a=b,排序后a仍然在b的前面;
不稳定:如果a原本在b前面,a=b,排序后a可能会出现在b的后面;
内排序:所有排序操作都在内存中完成;
外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;
时间复杂度:一个算法执行所耗费的时间;
空间复杂度:运行完成一个程序所需内存的大小。
(2)排序算法图片总结:

image.png

1、冒泡排序:
解析:
1.比较相邻两个元素,如果前一个比后一个大,则交换位置;
2.第一轮的时候最后一个元素应该是最大的;
3.按照步骤一的方法继续进行相邻两个元素的比较,这个时候由于最后的一个元素已经是最大的了,所以最后一个元素不用比较。

function sort(elements){
    for(var i=0;i<elements.length;i++){
       for(var j=0;j<elements.length-1-i;j++){
          if(elements[j] > elements[j+1]){
               var  swap=elements[j];
               elements[j]=elements[j+1];
               elements[j+1]=swap;
          }
       }
    }
}
var elements=[3,5,6,8,2,4,7,9,1,10];
console.log('before'+elements);
sort(elements);
console.log('after'+elements);

2、快速排序:
解析:快速排序是对冒泡排序的一种改进,第一趟排序时将数据分成两部分,一部分比另一部分的所有数据都要小,然后递归调用,在两边都实行快速排序。

function quickSort(elements){
    if(elements.length <=1){
      return elements;  
    }
  var pivotIndex=Math.floor(elements.length / 2);
  var pivot=elements.splice(pivotIndex,1)[0];
  var left=[];
  var right=[];
  for(var i=0;i<elements.length;i++){
    if(elements[i] < pivot){
        left.push(elements[i]);
    }else{
       right.push(elements[i]);
    }
  } 
return  quickSort(left).concat([pivot],quickSort(right));
//concat()方法用于连接两个或者多个数组;该方法不会改变现有的数组,而仅仅会返回被连接数组的一个副本。
};
var elements=[3,5,6,8,2,4,7,9,1,10];
document.write(quickSort(elements)); 

3、插入排序:
解析:
(1)从第一个元素开始,该元素可以认为已经被排序;
(2)取下一个元素,在已排序的元素序列中从后向前扫描;
(3)如果该元素(已排序)大于新元素,将该元素移动到下一位置;
(4)重复步骤3,直接找打已排序的元素大小或者等于新元素的位置;
(5)将新元素插到下一位置;
(6)重复步骤2

function sort(elements){
    // 假设第0个元素是一个有序数列,第1个以后的是无序数列,
    // 所以从第1个元素开始将无序数列的元素插入到有序数列中去
    for (var i =1; i<=elements.length; i++) {
        // 升序
        if(elements[i] < elements[i-1]){
            // 取出无序数列中的第i个作为被插入元素
            var guard=elements[i];
            //记住有序数列的最后一个位置,并且将有序数列的位置扩大一个
            var j=i-1;
            elements[i]=elements[j];
            // 比大小;找到被插入元素所在位置
            while (j>=0 && guard <elements[j]) {
                elements[j+1]=elements[j];
                j--;
            }
            elements[j+1]=guard; //插入
        }
    }
}
var elements=[3,5,6,8,2,4,7,9,1,10];
document.write('没调用之前:'+elements);
document.write('<br>');
sort(elements);
document.write('被调用之后:'+elements);

2、二分查找
解析:二分查找,也为折半查找,首先要找到一个中间值,通过与中间值的比较,大的放右,小的放左。再向两边中寻找中间值,持续以上操作。直到找到左右位置为止。
(1)递归方式

function binarySearch(data,dest,start,end){
    var end=end || data.length-1;
    var start=start || 0;
    var m=Math.floor((start + end)/2);
        if(data[m]==dest){
            return m;
        }
        if(dest < data[m]){
            return binarySearch(data,dest,0,m-1);
        }else{
            return binarySearch(data,dest,m+1,end);
        }
        return false;
    }
    var arr=[1,2,3,4,5,6,7,8,9,10];
    document.write(binarySearch(arr,4));

(2)非递归方法

function binarySearch(data,dest){
    var h=data.length-1;
    var l=0;
    while (l<=h) {
        var m=Math.floor((h+l)/2);
        if(data[m] ==dest){
            return m;
        }
        if(dest >data[m]){
            l=m+1;
        }else{
            h=m-1;
        }
    }
    return false;
}
var arr=[1,2,3,4,5,6,7,8,9,10];
document.write(binarySearch(arr,4));

4、选择排序:
解析:首先在未排序序列中找到最大(小)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最大(小)元素,放到已排序序列的末尾。以此类推,直到所有元素均排列完毕。

function selectionSort(arr){
        var len=arr.length;
    var minIndex,temp;
    console.time('选择排序耗时');
    for(var i=0;i<len-1;i++){
        minIndex=i;
        for(var j=i+1;j<len;j++){
            if(arr[j]<arr[minIndex]){ //寻找最小数
                minIndex=j; //将最小数的索引保存
            }
        }
        temp=arr[i];
        arr[i]=arr[minIndex];
        arr[minIndex]=temp;
    }
            console.timeEnd('选择排序耗时');
            return arr;
}
var arr=[1,2,3,4,5,6,7,8,9,10];
console.log(selectionSort(arr));

5、希尔排序:
解析:先将这个待排序的记录序列分割成若干子序列分别进行直接插入排序。

function shellSort(arr){
    var len=arr.length,temp,gap=1;
    console.time('希尔排序耗时:');
    while (gap<len/5) { //动态定义间隔序列
        gap=gap*5+1;
    }
    for(gap;gap>0;gap=Math.floor(gap /5)){
        for(var i=gap;i<len;i++){
            temp=arr[i];
            for (var j = i-gap; j >=0 && arr[j] > temp; j-=gap){
                arr[j+gap]=arr[j];
            }
            arr[j+gap]=temp;
        }
    }
      console.timeEnd('希尔排序耗时:');
      return arr;
}
var arr=[1,2,3,4,5,6,7,8,9,10];
console.log(shellSort(arr));

6、归并排序:
解析:归并排序是一种稳定的排序方法,将以有序的子序列合并,得到完全有序的序列,即先使每个子序列有序,再使子序列段有序。

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=[];
    console.time('归并排序耗时:');
    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());
    }
    console.timeEnd('归并排序耗时:');
            return result;
    }
    var arr=[3,5,6,8,2,4,7,9,1,10];
    document.write(mergeSort(arr));

7、堆排序
解析:堆排序(Heapsort)是指利用堆这种数据结构所设计的一种【】排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质,即子节点的键值或索引总是小于(或者大于)它的节点。

function heapSort(array){
    console.log('堆排序耗时:');
    if(Object.prototype.toString.call(array).slice(8,-1)==='Array'){
        var heapSize=array.length,temp;//建堆
        for (var i=Math.floor(heapSize / 2) -1; i>=0; i--) {
            heapify(array,i,heapSize);
        }
        for(var j=heapSize-1;j>=1;j--){//堆排序
            temp=array[0];
            array[0]=array[j];
            array[j]=temp;
            heapify(array,0,--heapSize);
        }
        console.log('堆排序耗时:');
        return array;
    }else{
        return 'array is not an Array!';
    }
}

function heapify(arr,x,len){
    if(Object.prototype.toString.call(arr).slice(8,-1)==='Array' && typeof x==='number'){
        var l = 2 * x + 1,
            r = 2 * x + 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{
        return 'arr is not Array or x is not a number!';
    }
}
var arr=[91,60,96,86,13,73,63,40,30,71,88];
document.write(heapSort(arr));

8、计数排序
解析:计数排序使用一种额外的数组C,其中第一个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将数组A中的元素排序到正确的位置。它只能对整数进行排序。

function countingSort(array){
    var len = array.length, B = [],C = [],
         min = max =array[0];
    console.time('计数排序耗时:');
    for (var i = 0; i < len; i++) {
        min = min <= array[i] ? min : array[i];
        max = max >= array[i] ? max : array[i];
        C[array[i]] = C[array[i]] ? C[array[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[array[k]] - 1] =array[k];
        C[array[k]]--;
    }
    console.timeEnd('计数排序耗时:');
    return B;
}
var arr=[2,2,3,5,4,2,8,6,7,69,5,2,1,3,4,7,3,6];
document.write(countingSort(arr));

9、桶排序:
解析:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是yidigui以递归的方式继续使用桶排序进行排)。

function bucketSort(array,num){
    if(array.length <= 1){
        return array;
    }
    var len = array.length,buckets = [],result = [],
    min = max =array[0],regex ='/^[1-9]+[0-9]*$/',space,n=0;
    num = num || ((num > 1 && regex.test(num))?num : 10);
    for(var i = 1; i < len; i++){
        min = min <= array[i] ? min :array[i];
        max = max >=array[i] ? max : array[i];
    }
    space = (max - min + 1) / num;
    for(var j =0; j < len; j++){
        var index = Math.floor((array[j] - min) / space);
        if(buckets[index]){//非空桶,插入排序
            var k = buckets[index].length - 1;
            while (k >= 0 && buckets[index][k] > array[j]) {
                buckets[index][k+1] = buckets[index][k];
                k--;
            }
            buckets[index][k+1]=array[j];
        }else{//空桶,初始化
            buckets[index] = [];
            buckets[index].push(array[j]);
        }
    }
    while (n < num) {
        result = result.concat(buckets[n]);
        n++;
    }
    return result;
}
var arr=[3,55,4,2,45,33,87,98,68,58,70,66];
document.write(bucketSort(arr,4));

10、基数排序:
解析:基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集,以此类推,直到最高位,有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序,最后的次序就是高优先级高的在前,高优先级相同的低优先级高的排在前面,基数排序基于分别排序,分别收集,所以是稳定的。

function radixSort(arr,maxDight){
    var mod = 10;
    var dev =1;
    var counter = [];
    console.time('基数排序耗时:');
    for (var i = 0; i < maxDight; i++, dev *= 10, mod *= 10) {
        for (var j = 0; j < arr.length; j++) {
            var bucket= parseInt((arr[j] % mod) / dev);
            if(counter[bucket] == null){
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }
        var pos = 0;
        for (var j = 0; j< counter.length; j++) {
            var value = null;
            if(counter[j] != null){
                while ((value = counter[j].shift())!=null) {
                    arr[pos++] = value;
                }
            }
        }
    }
    console.timeEnd('基数排序耗时:');
    return arr;
}
var arr=[3,55,4,2,45,33,87,98,68,58,70,66];
document.write(radixSort(arr,2));
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 216,287评论 6 498
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,346评论 3 392
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 162,277评论 0 353
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,132评论 1 292
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,147评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,106评论 1 295
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,019评论 3 417
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,862评论 0 274
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,301评论 1 310
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,521评论 2 332
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,682评论 1 348
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,405评论 5 343
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,996评论 3 325
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,651评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,803评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,674评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,563评论 2 352

推荐阅读更多精彩内容