前端跳槽面试总结之排序算法类

我会带着你远行 2023-02-17 14:26 7阅读 0赞

#### 一、排序算法 ####

1.  十种常见排序算法可以分为两大类，如下所示：

*  非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 `O(nlogn)`，因此称为非线性时间比较类排序。
 *  线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。

1.  算法复杂度相关概念，如下所示：

*  稳定：如果`a`原本在`b`前面，而`a=b`，排序之后`a`仍然在`b`的前面。
 *  不稳定：如果`a`原本在`b`的前面，而`a=b`，排序之后`a` 可能会出现在 `b`的后面。
 *  时间复杂度：对排序数据的总的操作次数。反映当`n`变化时，操作次数呈现什么规律。
 *  空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模`n`的函数。

#### 二、冒泡排序 ####

1.  冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
2.  冒泡排序的算法描述，如下所示：

*  比较相邻的元素。如果第一个比第二个大，就交换它们两个；
 *  对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
 *  针对所有的元素重复以上的步骤，除了最后一个；
 *  重复步骤`1~3`，直到排序完成。

1.  冒泡排序的实现代码，如下所示：

#### 三、选择排序 ####

1.  选择排序`(Selection-sort)`是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
2.  选择排序的算法描述，`n`个记录的直接选择排序可经过`n-1`趟直接选择排序得到有序结果，如下所示：

*  初始状态：无序区为`R[1..n]`，有序区为空；
 *  第i趟排序`(i=1,2,3…n-1)`开始时，当前有序区和无序区分别为`R[1..i-1]`和`R(i..n）`。该趟排序从当前无序区中-选出关键字最小的记录 `R[k]`，将它与无序区的第`1`个记录`R`交换，使`R[1..i]`和`R[i+1..n)`分别变为记录个数增加`1`个的新有序区和记录个数减少`1`个的新无序区；
 *  `n-1`趟结束，数组有序化了。

1.  选择排序的实现代码，如下所示：

1.  对于选择排序，是表现最稳定的排序算法之一，因为无论什么数据进去都是`O(n2)`的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。

#### 四、插入排序 ####

1.  插入排序`（Insertion-Sort）`的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
2.  插入排序的算法描述，插入排序都采用`in-place`在数组上实现，如下所示：

*  从第一个元素开始，该元素可以认为已经被排序；
 *  取出下一个元素，在已经排序的元素序列中从后向前扫描；
 *  如果该元素（已排序）大于新元素，将该元素移到下一位置；
 *  重复步骤`3`，直到找到已排序的元素小于或者等于新元素的位置；
 *  将新元素插入到该位置后；
 *  重复步骤`2~5`。

1.  插入排序的代码实现，如下所示：

1.  插入排序，在实现上，通常采用`in-place`排序（即只需用到`O(1)`的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

#### 五、希尔排序 ####

1.  希尔排序，第一个突破`O(n2)`的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
2.  希尔排序的算法描述，先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，如下所示：

*  选择一个增量序列`t1，t2，…，tk`，其中`ti>tj，tk=1；`
 *  按增量序列个数`k`，对序列进行`k` 趟排序；-
 *  每趟排序，根据对应的增量`ti`，将待排序列分割成若干长度为`m`的子序列，分别对各子表进行直接插入排序。仅增量因子为`1` 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

1.  希尔排序的代码实现，如下所示：

1.  希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者`Robert Sedgewick`提出的。

#### 六、归并排序 ####

1.  归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法`（Divide and Conquer）`的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为`2-路归并`。
2.  归并排序的算法描述，如下所示：

*  把长度为`n`的输入序列分成两个长度为`n/2`的子序列；
 *  对这两个子序列分别采用归并排序；
 *  将两个排序好的子序列合并成一个最终的排序序列。

1.  归并排序的代码实现，如下所示：

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

#### 七、快速排序 ####

1.  快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
2.  快速排序的算法描述，使用分治法来把一个串`（list）`分为两个子串`（sub-lists）`，如下所示：

*  从数列中挑出一个元素，称为 “基准”`（pivot）`；
 *  重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区`（partition）`操作；
 *  递归地`（recursive）`把小于基准值元素的子数列和大于基准值元素的子数列排序。

1.  快速排序的代码实现，如下所示：

#### 八、堆排序 ####

1.  堆排序`（Heapsort）`是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
2.  堆排序的算法描述，如下所示：

*  将初始待排序关键字序列`(R1,R2….Rn)`构建成大顶堆，此堆为初始的无序区；
 *  将堆顶元素`R[1]`与最后一个元素`R[n]`交换，此时得到新的无序区`(R1,R2,……Rn-1)`和新的有序区`(Rn)`,且满足`R[1,2…n-1]<=R[n]；`
 *  由于交换后新的堆顶`R[1]`可能违反堆的性质，因此需要对当前无序区`(R1,R2,……Rn-1)`调整为新堆，然后再次将`R[1]`与无序区最后一个元素交换，得到新的无序区`(R1,R2….Rn-2)`和新的有序区`(Rn-1,Rn)`。不断重复此过程直到有序区的元素个数为`n-1`，则整个排序过程完成。

1.  堆排序的代码实现，如下所示：

var len;   // 因为声明的多个函数都需要数据长度，所以把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,
            right = 2 * i + 2,
            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;
    }

#### 九、计数排序 ####

1.  计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
2.  计数排序的算法描述，如下所示：

*  找出待排序的数组中最大和最小的元素；
 *  统计数组中每个值为i的元素出现的次数，存入数组`C`的第`i`项；
 *  对所有的计数累加（从`C`中的第一个元素开始，每一项和前一项相加）；
 *  反向填充目标数组：将每个元素`i`放在新数组的第`C(i)`项，每放一个元素就将`C(i)`减去`1`。

1.  计数排序的代码实现，如下所示：

1.  计数排序是一个稳定的排序算法。当输入的元素是 `n` 个 `0`到 `k` 之间的整数时，时间复杂度是`O(n+k)`，空间复杂度也是`O(n+k)`，其排序速度快于任何比较排序算法。当`k`不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

#### 十、桶排序 ####

1.  桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 `(Bucket sort)`的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
2.  桶排序的算法描述，如下所示：

*  设置一个定量的数组当作空桶；
 *  遍历输入数据，并且把数据一个一个放到对应的桶里去；
 *  对每个不是空的桶进行排序；
 *  从不是空的桶里把排好序的数据拼接起来。

1.  桶排序的代码实现，如下所示：

unction 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 (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++) { 
            insertionSort(buckets[i]);                     // 对每个桶进行排序，这里使用了插入排序
            for (var j = 0; j < buckets[i].length; j++) { 
                arr.push(buckets[i][j]);                     
            }
        }
     
        return arr;
    }

1.  桶排序最好情况下使用线性时间`O(n)`，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为`O(n)`。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

#### 十一、基数排序 ####

1.  基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
2.  基数排序的算法描述，如下所示：

*  取得数组中的最大数，并取得位数；
 *  `arr`为原始数组，从最低位开始取每个位组成`radix`数组；
 *  对`radix`进行计数排序（利用计数排序适用于小范围数的特点）；

1.  基数排序的代码实现，如下所示：

/ LSD Radix Sort
    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;
    }

1.  基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要`O(n)`的时间复杂度，而且分配之后得到新的关键字序列又需要`O(n)`的时间复杂度。假如待排数据可以分为`d`个关键字，则基数排序的时间复杂度将是`O(d*2n)`，当然`d`要远远小于`n`，因此基本上还是线性级别的。基数排序的空间复杂度为`O(n+k)`，其中`k`为桶的数量。一般来说`n>>k`，因此额外空间需要大概`n`个左右。