JS 排序算法
浏览 631 | 评论 0
黄文勇
2020年04月22日

好记性不如烂笔头,18年学的排序算法现在基本都忘光了,今天复习复习 ヾ(≧∇≦*)ゝ

冒泡排序

冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。

重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从Z到A)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。

平均时间复杂度:O(n^2)。

var arr =[1,54,11,5,121,4,1,4,13,164,13];
for (var i = 0; i < arr.length - 1; i++) {
      for (var j = 0; j < arr.length - i - 1; j++) {
         if (arr[j] > arr[j + 1]) {
                var swap = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = swap;
           }
      }
 }
//输出 1,1,4,4,5,11,13,13,54,121,164

选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

时间复杂度O(n^2)。

    var arr = [1, 54, 11, 5, 121, 4, 1, 4, 13, 164, 13];
    var swap = null;
    for (var i = 0; i < arr.length; i++) {
        swap = i;
        for (var j = i; j < arr.length; j++) {
            if (arr[swap] < arr[j]) {
                 swap = j;
             }
        }
        var num = arr[i];
        arr[i] = arr[swap];
        arr[swap] = num;
    }
    //输出 164,121,54,13,13,11,5,4,4,1,1

插入排序

插入排序,一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增1的有序表。在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动。

时间复杂度:O(n^2)。

var arr = [1, 1, 4, 11, 5, 4, 13, 54, 13, 164, 121];
var len = arr.length;
var preIndex, current;
for (var i = 1; 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;
}
//输出 1,1,4,4,5,11,13,13,54,121,164

希尔排序

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

时间复杂度为O(n^3/2)

 var arr = [1, 54, 11, 5, 121, 4, 1, 4, 13, 164, 13];
 var len = arr.length;
 for (var a = Math.floor(len / 2); a > 0; a = Math.floor(a / 2)) {
     for (var i = a; i < len; i++) {
         for (var j = i - a; j >= 0 && arr[j] > arr[a + j]; j -= a) {
             var temp = arr[j];
             arr[j] = arr[a + j];
             arr[a + j] = temp;
          }
      }
 }
//输出 1,1,4,4,5,11,13,13,54,121,164
本文作者:黄文勇
本文链接:https://www.3dcw.cn/index.php/archives/493/
最后修改时间:2020-05-29 17:45:11
本站未注明转载的文章均为原创,并采用 CC BY-NC-SA 4.0 授权协议,转载请注明来源,谢谢!
评论
与本文无关评论请发留言板。请不要水评论,谢谢。
textsms
支持 Markdown 语法
email
link
评论列表
暂无评论