JavaScript -- 几种常见的内部排序算法的JavaScript描述

深藏阁楼爱情的钟 2022-04-17 03:52 282阅读 0赞

对计算机中存储的数据执行的两种最常见操作是排序和检索，自从计算机产业伊始便是如此。这也意味着排序和检索在计算机科学中是被研究得最多的操作。

在面试当中，排序算法也是问的比较多的一方面。无论你是前端还是后台，学习算法知识，是IT工程师是必修课，苦行课。

我们要做探索者，不能只会用黑盒子（sort()函数），就像国家一直想做出国产芯片一样，自己明白原理是最好的。

提示：以下排序算法均按照从小到大排序。

1：冒泡排序

冒泡排序简单的说就是每一次循环就是将未排序的数组中最大的数移到数组尾。如何移动了？

每一次与相连的数比较，if (arr\[i\] > arr \[i+1\]) swap (arr\[i\],arr\[i+1\]);

this.bubbleSort = function () {
            for (let i = 0; i < this.length(); i++) {//N个数，循环n次
                for (let j = 0; j < this.length() - 1 - i; j++) {
                    if (this.array[j] > this.array[j+1]) this.swap(j,j+1);//将最大数移到尾部
                }
            }
        };

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

2：选择排序

选择排序从数组的开头开始，将第一个元素和其他元素进行比较。检查完所有元素后，最小的元素会被放到数组的第一个位置，然后算法会从第二个位置继续。这个过程一直进行，当进行到数组的倒数第二个位置时，所有的数据便完成了排序。

this.selectSort = function () {
            for (let i = 0; i < this.length(); i++) {
                for (let j = i + 1; j < this.length(); j++) {//注意前面0到i-1都是排好的，正在觉得i的位置
                    if (this.array[i] > this.array[j]) this.swap(i,j);
                }
            }
        };

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

3：插入排序

插入排序简单的说就是往已经排好序的数组里面插入下一个数，并使得新数组也是有序的。主要看程序。

this.insertSort = function () {
            let temp;
            for (let i = 1; i < this.length(); i++) {//从1开始，往有序数组（其实只有array[0]这一个元素）添加其他数
                if (this.array[i] < this.array[i-1]) {//添加数比它前一个小，安排它去合适的位置
                    temp = this.array[i];//保存它的值
                    this.array[i] = this.array[i-1];//你要让位给比你大的（因为此时前面的数组已经是排好的，它其实是最大值）
                    let j;
                    for (j = i - 2; this.array[j] > temp && j >= 0; j--) {//开始寻找一个比你小的的位置
                        this.array[j+1] = this.array[j];
                    }
                    j = Math.max(0, j);//如果你最小，那么循环结束时j等于-1，所以你应该放在array[0]上
                    this.array[j] = temp;
                }
            }
    
        };

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

4：希尔排序

**希尔排序又称缩小增量排序：**先将整个待排序记录序列分割成为若干子序列分别进行插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次插入排序。

举个栗子

我们选择增量为5 3 1。

对于序列\{12,2,16,30,28,10,16\*,20,6,18\}，增量为5时，我们排序的子序列为下标为1 6与2 7与3 8与4 9与5 10（以1开始）

即\{12，10\} \{2，16\*\}\{16，20\}\{30，6\}\{28，18\}分别对这5个子序列进行排序为\{10，12\} \{2，16\*\}\{16，20\}\{6，30\}\{18，28\}

则原序列变成\{10,2,16,6,18,12,16\*,20,30,28\}

再选增量为3时:我们排序的子序列为1 4 7 10与2 5 8与3 6 9 依次把他们排序好后，原序列变成\{6,2,12,10,18,16,16\*,20,30,30,28\}

我们发现大部分元素的位置关系已经都很对了，最后我们选择增量为1（注意最后一定要选增量为1，即进行直接插入排序）

原序列变成\{2,6,10,12,16,16\*,18,20,18,30\}有序了！

我们都知道直接插入排序很多时间都浪费在查找和移动元素上面，不难发现经过前面俩趟希尔排序，我们的序列已经很有序了，换句话说就是离它应该待的位置很接近了，所以进行直接插入排序时，节省了很多时间！！！**希尔排序优化点**

还有一点：增量是随机选取的吗？很明显不是的，但是没有一个最优的增量选取，一般都是选取互质数，依次递减，最后选取增量为1.

this.shellInsertSort = function (gap) {
            let temp;
            for (let i = 0; i < gap; i++) {//有gap的子序列
                for (let j = i + gap; j < this.length(); j += gap) {//每一次增量是gap
                    if (this.array[j] < this.array[j-gap]) {//后面代码和插入排序代码类似，不过增量是gap
                        temp = this.array[j];
                        this.array[j] = this.array[j-gap];
                        let k;
                        for (k = j - 2*gap; this.array[k] > temp && k >= i; k -= gap) {
                            this.array[k+gap] = this.array[k];
                        }
                        k = Math.max(i, k);
                        this.array[k] = temp;
                    }
                }
            }
        };
        this.shellSort = function () {
            const dlbt = [5,3,1];//增量
            for (let i = 0; i < dlbt.length; i++) {//对每一个增量，进行插入排序
                this.shellInsertSort(dlbt[i]);
            }
        };

希尔排序的时间复杂度是经过大量实验表明为O(n^(3/2))。算法不稳定，有时飞快，看你的增量选取，目前没有数学证明其时间复杂度。

5：归并排序

归并排序是高级排序算法，主要思想是分治，简单的说就是将大数组\[left,right\]分成\[left,mid\] 和\[mid+1,right\]（其中mid = Math.floor((left+right)/2);)分成俩个小数组,将小数组排好序，然后将俩个数组合并。

举个栗子

![Center][]

具体看一下代码：

this.merge = function (left, right) {
            let temp = [].concat(this.array);
            //因为我需要对this.array排序，所以我们复制一份
            let mid =  Math.floor((left + right) / 2), i, j, pos = left;
            //我们将[left,right]分成俩部分[left,mid]和[mid+1,right]
            //然后定义俩个变量i,j分别取数，谁小就先取谁
            for (i = left, j = mid + 1; i <= mid && j <= right;) {
                if (temp[i] <= temp[j]) {//temp[i]小，取它，然后i++
                    this.array[pos++] = temp[i++];//更换pos的位置的值
                } else {
                    this.array[pos++] = temp[j++];
                }
            }
            //检查有没有其他值没有更换
            while (i <= mid) this.array[pos++] = temp[i++];
            while (j <= right) this.array[pos++] = temp[j++];
    
            
        };
        this.mSort = function (left,right) {
            if (left >= right ) return ;//这个时候不应该在迭代了
            let mid = Math.floor((left + right) / 2);//取中间
            this.mSort(left, mid);//对左边继续划分
            this.mSort(mid + 1, right);//对右边继续划分
            this.merge(left, right);//对[left,right]这个部分进行排序
        };
        this.mergeSort = function () {//调用mSort函数，排序范围是[0,length-1]
            this.mSort(0,this.length()-1);
        };

时间复杂度O(nlogn)，空间复杂度O(n)（额外需要一个数组）

6：快速排序(快速排序是处理大数据集最快的排序算法之一)

快速排序通过一趟排序将待排记录分割成独立的俩部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这俩部分记录继续继续进行排序，已到达整个序列有序。

为了方便初始关键字（也可以称为轴）一般选取序列第一个元素。

简单的说，就是选取第一个数（轴），然后将原数组分成左右俩部分。左部分比轴要小，右部分比轴大，然后将俩部分继续这个操作。

![Center 1][]

49左边的比49小，49右边的比49大。

this.partition = function(left,right) {
            let mid = this.array[left];//轴
            while (left < right) {//完成将[left,right]按照mid分成俩部分
                while (right > left && this.array[right] >= mid) right--;//安排右边
                this.array[left] = this.array[right];//找到比mid小的，这个地方为轴准备，然后这个地方的值放到上一个轴的位置
                while (left < right && this.array[left] <= mid ) left++;//安排左边
                this.array[right] = this.array[left];//找到比mid大的，这个地方为轴准备，然后这个地方的值放到上一个轴的位置
            }
            this.array[left] = mid;//将轴的值放到正确的位置
            return left;   
        };
        this.qSort = function (left,right) {
            if (left >= right) return ;
            let mid =  this.partition(left,right);//将[left,right]完成一次快排，返回轴
            this.qSort(left,mid-1);//将轴的左边继续这个操作
            this.qSort(mid+1,right);//将轴的右边继续这个操作
        };
        this.quickSort = function () {//调用qSort函数，排序范围是[0,length-1]
            this.qSort(0,this.length()-1);
        };

时间复杂度O(nlogn) ，有一个最坏的时间复杂度O(n^2) (正好是逆序）

7：堆排序

堆排序：利用堆结构的一种树形选择排序，每次取堆顶，然后把剩下的n-1个元素维护成堆。反复操作得到一个有序序列。

n个元素的序列\{k1,k2,k3,,,kn\}当且仅当满足以下关系时，称为堆。

ki<=k2\*i               或    ki>=k2\*i

ki<=k2\*i+1                   ki>=k2\*i+1

简单的来说，如果把堆看成树形结构的话，那么它是一棵完全二叉树且每个节点比他的俩个儿子都大（称为大顶堆）或者都小（称为小顶堆）。

以小顶堆为例：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d1c3RfY3ls_size_16_color_FFFFFF_t_70][]

堆排序的难点在于，堆的建立和堆的维护。

因为我们的数组是从0开始的，**所以左右儿子是2\*i+1和2\*i+2**

堆排序的过程就不难理解了，因为根节点肯定是最大或者最小，每次把根节点移出，然后把剩下的元素维护成堆，重复操作。有点像冒泡排序对吧！但是它比冒泡排序要快很多。冒泡排序是将一个元素与其他的未排序的所有元素都进行比较了，很浪费时间，而堆排序不一样，因为堆的特殊性，例如大顶堆，节点总比儿子节点大，把根节点与最后一个元素交换后，我们只需要在儿子节点当中找比它大的最大儿子节点，找到了就替换，一直到儿子节点比小。log(n)的深度。

建堆操作：我们从序列lenth/2开始往前面调整，把每个节点i与它们的儿子节点2\*i+1和2\*i+2比较，如果儿子节点比它大就互换，然后重复操作。

this.heapAdjust = function (pos, len) {//维护操作，维护第pos个节点，长度为len的数组，后面不用维护了
            let temp = this.array[pos];//取值
            let flag = true;//标记，是否找到了
            for (let i = 2 * pos; i <= len ; i = i * 2) {
                let x1 = ((this.array[i+1] == undefined || (i + 1) > len ) ? Number.MIN_VALUE : this.array[i+1]);
                let x2 = ((this.array[i+2] == undefined || (i + 2) > len ) ? Number.MIN_VALUE : this.array[i+2]);
                //左右儿子必须有意义且在len范围内，不然就是赋最小值（无意义的值）
                let  maxValue, s;
                if (x1 >= x2) {//找左右儿子的最大值
                    s = i + 1,  maxValue = x1;
                }
                else {
                    s = i + 2,  maxValue = x2;
                }
                if (temp > maxValue) {//如果比左右儿子都大，那么就应该放在这里
                    this.array[pos] = temp;
                    flag = false;//找到了
                    break;
                }
                else {//有儿子比你大，那么就应该替换你的位置
                    this.array[pos] = maxValue;
                    i = s;
                    pos = s;
                }
            }
            if (flag) this.array[pos] = temp;
        }
        this.heapSort = function () {
            for (let i = Math.floor((this.length() - 1) / 2); i >= 0; i--) {//建堆操作
                this.heapAdjust(i,this.length()-1);
            };
            
            for (let i = this.length() - 1; i > 0; i--) {
                this.swap(0,i);//将最大值放到堆尾
                this.heapAdjust(0, i - 1 );//维护前面是堆，后面的已经是排好序的数组
            }
        }

时间复杂度O(nlogn)。

可以随机10个数试试。

let app = new myArray();
    for (let i = 0; i < 10; i++) {
        app.add(Math.floor(Math.random()*100));
        
    } 
    
    // app.heapSort(); //排序方法，任选
    app.show();

哈哈，介绍完了，如果你还不清楚可以留言，如果你还喜欢其他排序算法，欢迎留言。

[Center]: /images/20220417/9b572eb340ba4fb3a75c15255252995b.png
[Center 1]: /images/20220417/9f10fe60d525447782b07c0efe2529dd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d1c3RfY3ls_size_16_color_FFFFFF_t_70]: /images/20220417/ee4bc94c2ba3477dbd52295ce4a603be.png