数组十大排序方法及思想

名词解释：
n:数据规模
k:“桶”的个数
In-place:占用常数内存，不占用额外内存
Out-place:占用额外内存
稳定性:排序后2个相等键值的顺序和排序之前它们的顺序相同

一、冒泡排序

冒泡排序算法原理：
1.比较相邻的元素。如果第一zhi个比第二个大，就交换他们dao两个。
2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。。

算法优化：当里面的一层循环在某次扫描中没有交换则说明此时数组已经全部有序，无需再再次扫描。所以可以添加一个标记每交换一次就进行标记，如果某次没有没有标记就说明已经有序了

作为最简单的排序算法之一，冒泡排序给我的感觉就像Abandon在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。。。冒泡排序还有一种优化算法，就是立一个flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。
什么时候最快？
当输入的数据已经是正序时（都已经是正序了，我还要你冒泡排序有何用啊。。。。）
什么时候最慢？
当输入的数据是反序时（写一个for循环反序输出数据不就行了，干嘛要用你冒泡排序呢，我是闲的吗。。。）

<script>
    //1-冒泡排序
    function bubbleSort(arr){
        var len = arr.length;
        for(var i=0; i<len; i++){
            for(var j=0; j<len-1-i; j++){
                if(arr[j] > arr[j+1]){     // 元素比大小
                    var temp = arr[j+1];   // 元素位置交换，从小到大排列
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }
    // 测试
    var arr = [6,2,22,45,1,6,8,200,56,111];
    console.log(bubbleSort(arr).join(','));
    //1,2,6,6,8,22,45,56,111,200
</script>

二、选择排序

表现最稳定的排序算法之一，因为无论什么数据进去都是O(n²)的时间复杂度。。。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

<script>
    //2-选择排序
    function selectionSort(arr){
        var len = arr.length;
        var minIndex, temp;
        for(var i=0; i<len; 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;
        }
        return arr;
    }
    // 测试
    var arr = [6,2,22,45,1,6,8,200,56,111];
    console.log(selectionSort(arr).join(','));
</script>

三、插入排序

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。当然，如果你说你打扑克牌摸牌的时候从来不按牌的大小整理牌，那估计这辈子你对插入排序的算法都不会产生任何兴趣了。。。

插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

    //3-插入排序
    // 插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。
    // 插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。
    function insertSort(arr){
        var len = arr.length;
        var preIndex, current;
        for(var i=0; i<len; i++){
            preIndex = i-1;
            current = arr[i];
            while(preIndex >= 0 && arr[preIndex] > current){
                arr[preIndex+1] = arr[preIndex];
                preIndex--;
            }
            arr[preIndex+1] = current;
        }
        return arr;
    }
    // 测试
    var arr = [6,2,22,45,1,6,8,200,56,111];
    console.log(insertSort(arr).join(','));
</script>

四、希尔排序

希尔排序是插入排序的一种更高效率的实现。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版》的合著者Robert Sedgewick提出的。在这里，我就使用了这种方法。

<script>
    //04-希尔排序
    function shellSort(arr){
        var len = arr.length;
        var temp, gap=1;
        while(gap<len/3){   // 动态定义间隔序列
            gap = gap*3 + 1;
        }
        for(gap; gap>0; gap=Math.floor(gap/3)){
            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;
            }
        }
        return arr;
    }

    // 测试
    var arr = [6,2,22,45,1,6,8,200,56,111];
    console.log(shellSort(arr).join(','));
</script>

五、归并排序

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第2种方法）
自下而上的迭代
在《数据结构与算法JavaScript描述》中，作者给出了自下而上的迭代方法。但是对于递归法，作者却认为：

However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.

然而,在 JavaScript 中这种方式不太可行,因为这个算法的递归深度对它来讲太深了。
说实话，我不太理解这句话。意思是JavaScript编译器内存太小，递归太深容易造成内存溢出吗？还望有大神能够指教。

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。

    //5-归并排序
    function mergeSort(arr){
        var len = arr.length;
        if(len < 2){
            return arr;
        }
        var middle = Math.floor(len/2);
        var left = arr.slice(0,middle);  // 取左半部分数组
        var 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;
    }

    // 测试
    var arr = [6,2,22,45,1,6,8,200,56,111];
    console.log(mergeSort(arr).join(','));
</script>

六、快速排序

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高! 它是处理大数据最快的排序算法之一了。虽然Worst Case的时间复杂度达到了O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为O(n log n) 的排序算法表现要更好，可是这是为什么呢，我也不知道。。。好在我的强迫症又犯了，查了N多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：

快速排序的最坏运行情况是O(n²)，比如说顺序数列的快排。但它的平摊期望时间是O(n log n) ，且O(n log n)记号中隐含的常数因子很小，比复杂度稳定等于O(n log n)的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
快速排序动图演示

<script>
    //6-快速排序
    function quickSort(arr,left,right){
        var len = arr.length;
        var partitionIndex, 
            left = typeof left != 'number' ? 0 : left,
            right = typeof right != 'number' ? len-1 : right;
        if(left<right){
            partitionIndex = partition(arr,left,right);
            quickSort(arr,left,partitionIndex-1);
            quickSort(arr,partitionIndex+1,right);
        }
        return arr;
    }
    function partition(arr,left,right){  // 分区操作
        var pivot = left,    // 设定基准值
            index = pivot+1;
        for(var i=index; i<=right; i++){
            if(arr[i] < arr[pivot]){
                swap(arr,i,index);
                index++;
            }
        }
        swap(arr,pivot,index-1);
        return index-1;
    }
    function swap(arr,i,j){
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 测试
    var arr = [6,2,22,45,1,6,8,200,56,111];
    console.log(quickSort(arr).join(','));
</script>

七、堆排序

堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列

<script>
    //07- 堆排序 
    var len;
    // 建立大顶堆
    function buildMaxHeap(arr){
        len = arr.length;
        for(var i=Math.floor(len/2); i>=0; i--){
            heapify(arr,i);
        }
    }
    // 堆调整
    function heapify(arr,i){
        var left = 2*i + 1;
        var right = 2*i + 2;
        var largest = i;
        if(left<len && arr[left]>arr[largest]){
            largest = left;
        }
        if(right<len && arr[right]>arr[largest]){
            largest = right;
        }
        if(largest != i){
            swap(arr,i,largest);
            heapify(arr,largest);
        }
    }
    // 交换位置
    function swap(arr,i,j){
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    // 推排序
    function heapSort(arr){
        buildMaxHeap(arr);  // 建立大顶堆
        for(var i=arr.length-1; i>0; i--){
            swap(arr,0,i);
            len--;
            heapify(arr,0);
        }
        return arr;
    }

    // 测试
    var arr = [6,2,22,45,1,6,8,200,56,111];
    console.log(heapSort(arr).join(','));
</script>

八、计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

<script>
    // 08-计数排序
    function countingSort(arr,maxValue){
        var bucket = new Array(maxValue+1);
        var sortedIndex = 0;
        var arrLen = arr.length;
        var bucketLen = maxValue+1;
        for(var i=0; i<arrLen; i++){
            if(!bucket[arr[i]]){
                bucket[arr[i]] = 0;
            }
            bucket[arr[i]]++;
        }
        for(var j=0; j<bucketLen; j++){
            while(bucket[j]>0){
                arr[sortedIndex++]=j;
                bucket[j]--;
            }
        }
        return arr;
    }

    // 测试
    var arr = [6,2,22,45,1,6,8,200,56,111];
    console.log(countingSort(arr,200).join(','));
</script>

九、桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。

为了使桶排序更加高效，我们需要做到这两点：

在额外空间充足的情况下，尽量增大桶的数量
使用的映射函数能够将输入的N个数据均匀的分配到K个桶中
同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

什么时候最快
当输入的数据可以均匀的分配到每一个桶中

什么时候最慢
当输入的数据被分配到了同一个桶中

<script>
    // 09-桶排序。
    function bucketSort(arr,bucketSize){  // 桶的数量不能为负
        if(arr.length === 0){
            return arr;
        }
        var i;
        var minValue = arr[0];
        var maxValue = arr[0];
        for(i=1; i<arr.length; i++){
            if(arr[i] < minValue){
                minValue = arr[i];   // 输出最小的值
            }else if(arr[i] > maxValue){
                maxValue = arr[i];   // 输出最大的值
            }
        }

        // 桶的初始化
        var DEFAULT_BUCKET_SIZE = 5;   // 设置桶的默认数量为5
        bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
        var bucketCount = Math.floor((maxValue-minValue)/bucketSize) + 1;
        var buckets = new Array(bucketCount);
        for(i=0; i<buckets.length; i++){
            buckets[i] = [];
        }
        // 利用映射函数将数据分配到各个桶中
        for(var i=0; i<arr.length; i++){
            buckets[Math.floor((arr[i] - minValue)/bucketSize)].push(arr[i]);
        }
        arr.length = 0;
        for(i=0; i<buckets.length; i++){
            insertSort(buckets[i]);  // 对每个桶进行排序，这里使用了插入排序
            for(var j=0; j<buckets[i].length; j++){
                arr.push(buckets[i][j]);
            }
        }
        return arr;
    }
    // 插入排序
    function insertSort(arr){
        var len = arr.length;
        var preIndex, current;
        for(var i=0; i<len; i++){
            preIndex = i-1;
            current = arr[i];
            while(preIndex >= 0 && arr[preIndex] > current){
                arr[preIndex+1] = arr[preIndex];
                preIndex--;
            }
            arr[preIndex+1] = current;
        }
        return arr;
    }

    // 测试
    var arr = [6,2,22,45,1,6,8,200,56,111];
    console.log(bucketSort(arr,9).join(','));
</script>

十、基数排序

基数排序有两种方法

MSD 从高位开始进行排序
LSD 从低位开始进行排序

基数排序 vs 计数排序 vs 桶排序
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

基数排序：根据键值的每位数字来分配桶
计数排序：每个桶只存储单一键值
桶排序：每个桶存储一定范围的数值

<script>
    // 10-基数排序
    var counter = [];
    function radixSort(arr,maxDigit){
        var mod = 10;
        var dev = 1;
        for(var i=0; i<maxDigit; 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;
                    }
                }
            }
        }
        return arr;
    }

    // 测试
    var arr = [6,2,22,45,1,6,8,200,56,111,58,96,300,27,154,39,9,1000];
    console.log(radixSort(arr,6).join(','));
</script>

-- end --

本文系转载 如侵权请联系删除。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 215,723评论 6赞 498
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,003评论 3赞 391
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 161,512评论 0赞 351
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,825评论 1赞 290
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,874评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,841评论 1赞 295
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,812评论 3赞 416
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,582评论 0赞 271
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,033评论 1赞 308
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,309评论 2赞 331
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,450评论 1赞 345
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,158评论 5赞 341
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,789评论 3赞 325
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,409评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,609评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,440评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,357评论 2赞 352