Ch7 内排序

0. 算法一览

内排序是指”所有排序操作都在内存中完成”，无需额外外部存储空间

|

类别 | |

算法 | 时间开销 | | |

空间开销 |

稳定性 |

原地性 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | | | 平均 | | 最好 | 最坏 | |



比
较
排
序 | 交换 | 冒泡排序 | O(**n2)** | O(**n**) | O(**n2)** | O(**1)** | 是 | 是 | | | | 快速排序 | O(nlog**n)** | O(nlog**n)** | O(**n2)** | O(**logn**) | 否 | 是 | | | 插入 | 插入排序 | O(**n2)** | O(**n**) | O(**n2)** | O(**1)** | 是 | 是 | | | | 希尔排序 | O**(n1.5)** | O(**n**) | O(**n2)** | O(**1)** | 否 | 是 | | | 选择 | 选择排序 | O(**n2)** | O(**n2)** | O(**n2)** | O(**1)** | 否 | 是 | | | | 堆排序 | O(nlog**n)** | O(nlog**n)** | O(nlog**n)** | O(**1)** | 否 | 是 | | | 归并 | 归并排序 | O(nlog**n)** | O(nlog**n)** | O(nlog**n)** | O(n**)** | 是 | 否 | | 非
比
较 | 桶排序 | | O(n+max(MaxKey,n)) | | | O(**n+k)** | 是 | 否 | | | 基数排序 | | O(d*(n+r)) | | | O(**n+k)** | 是 | 否 |

• 快速排序的空间开销来自于递归栈 | 常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置
  - 在冒泡排序之类的排序中，问题规模为 n，又因为需要比较 n 次，所以平均时间复杂度为 O(n²)
  - 在归并排序、快速排序、堆排序中，问题规模通过分治法消减为 logN 次，所以时间复杂度平均 O(nlogn)
  | | | —- | —- | | |
  - 理想条件下的分治：递归层数 log2n 代表分治后的问题规模，同时每一层依旧比较 n 次，因此总复杂度 O(nlogn)
  - 快排最坏情况：归并、堆排、快排都采用分治法，但快排的分治依赖于选择 pivot 后的切分结果；当快排产生极不平衡的切分时，比如每次都只有比 pivot 小的元素，则递归二叉树退化为链表，问题规模回归到 n，总复杂度变为 O(n2)
  | | 基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前应该有多少个元素来排序。针对数组 arr，计算 arr[i] 之前有多少个元素，则唯一确定了 arr[i] 在排序后数组中的位置。
  - 非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度 O(n)，但是非比较排序需要占用空间来确定唯一位置，所以空间复杂度更高
  | |

1. 插入排序（Insertion Sort）

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

var sortArray = function(nums) {
    const swap = function(arr, i, j){
        let temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
    const insertSort = function(arr){
        for(let i=1; i<arr.length; i++){
            for(let j=i-1; j>=0 && arr[j+1]<arr[j]; j--){
                swap(arr, j, j+1);
            }
        }
    }
    insertSort(nums);
    return nums;
};

2. 冒泡排序（Bubble Sort）

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

var sortArray = function(nums) {
    const swap = function(arr, i, j){
        let temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
    const bubbleSort = function(arr){
        for(let i=0; i < arr.length-1; i++){
            for(let j=0; j<arr.length-i-1; j++){
                if(arr[j]>arr[j+1]) swap(arr, j, j+1);
            }
        }
    }
    bubbleSort(nums);
    return nums;
};

优化：有序标记

通常资料中都给出冒泡排序的最优时间复杂度为 O(n)，但使用上面的原始算法，即便有序情况下也需要比较 O(n2)，要真正达到 O(n)，需使用一个有序标记：第一次内循环中，如果全体有序，则标记为 true，说明有序，内循环遍历结束后，判断标记为 true，直接跳出外层循环

var sortArray = function(nums) {
    const swap = function(arr, i, j){
        let temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
    const bubbleSort = function(arr){
        let isSorted = true;
        for(let i=0; i<arr.length-1; i++){
            for(let j=0; j<arr.length-i-1; j++){
                if(arr[j]>arr[j+1]){
                    swap(arr, j, j+1);
                    isSorted = false;
                }
            }
            if(isSorted) return;
        }
    }
    bubbleSort(nums,0,nums.length-1);
    return nums;
};

3. 选择排序（Selection Sort）

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趟结束，数组有序化了。

var sortArray = function(nums) {
    const swap = function(arr, i, j){
        let temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
    const selectSort = function(arr){
        for(let i=0; i<arr.length; i++){
            let min = i;
            for(let j=i+1; j<arr.length; j++){
                if(arr[j]<arr[min]) min=j;
            }
            if(min != i) swap(arr, min, i);
        }
    }
    selectSort(nums);
    return nums;
};

4. 希尔排序（Shell Sort）

希尔排序是基于简单插入排序的算法：把记录按一定增量(希尔增量)分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一个有序序列。

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

• 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；[通常选择初始增量i=array。length/2，此后i=i/2]
• 按增量序列个数k，对序列进行k 趟排序；
• 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。

function shellSort(arr) {
    var len = arr.length;
    for (var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
        for (var i = gap; i < len; i++) {
            var j = i;
            var current = arr[i];
            while (j - gap >= 0 && current < arr[j - gap]) {
                 arr[j] = arr[j - gap];
                 j = j - gap;
            }
            arr[j] = current;
        }
    }
    return arr;
}

5. 归并排序（Merge Sort）

归并排序采用分治法（Divide and Conquer）思想，是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

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

var sortArray = function(nums) {
    const swap = function(arr, i, j){
        let temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
    const mergeSort = function(temp, arr, l, r){
        if(l>=r) return;
        let mid = ((r-l)>>1)+l;
        mergeSort(temp, arr, l, mid);
        mergeSort(temp, arr, mid+1, r);
        for(let i=l; i<=r; i++){
            temp[i] = arr[i];
        }
        for(let curr=l, i1=l, i2=mid+1; curr<=r; curr++){
            if(i1 == mid+1 || temp[i2]<temp[i1]) arr[curr]=temp[i2++];
            else if(i2 == r+1 || temp[i1]<= temp[i2]) arr[curr]=temp[i1++];
        }
    }
    mergeSort([], nums, 0, nums.length-1);
    return nums;
};

优化：针对小序列

标准归并排序中对于所有子序列我们都使用了归并排序，实际上可设置Threshold，当子序列长度小于Threshold时就是用插入排序，可节省在小序列排序中的开销

var sortArray = function(nums) {
    const swap = function(arr, i, j){
        let temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
    const insertSort = function(arr, l, r){
        // 注意是 i<=r
        for(let i=l+1; i<=r; i++){
            for(let j=i-1; j>=l && arr[j]>arr[j+1];j--){
                swap(arr, j, j+1);
            }
        }
    }
    const mergeSort = function(temp, arr, l, r){
        // 以4作为threshold
        if(r-l<=4){
            insertSort(arr, l, r);
            return;
        }
        let mid = ((r-l)>>1)+l;
        mergeSort(temp, arr, l, mid);
        mergeSort(temp, arr, mid+1, r);
        for(let i=l; i<=r; i++){
            temp[i] = arr[i];
        }
        for(let curr=l, i1=l, i2=mid+1; curr<=r; curr++){
            if(i1 == mid+1 || temp[i2]<temp[i1]) arr[curr]=temp[i2++];
            else if(i2 == r+1 || temp[i1]<= temp[i2]) arr[curr]=temp[i1++];
        }
    }
    mergeSort([], nums, 0, nums.length-1);
    return nums;
};

6. 快速排序（Quick Sort）

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

快排使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

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

var sortArray = function(nums) {
    const swap = function(arr, i, j){
        let temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
    const quickSort = function(arr, l, r){
        if(l>=r) return;
        let pivot = ((r-l)>>1)+l;
        swap(arr, pivot, r);
        pivot = partition(arr, l-1, r, arr[r]);
        swap(arr, pivot, r);
        quickSort(arr, l, pivot-1);
        quickSort(arr, pivot+1, r);
    }
    const partition = function(arr, l, r, pivotVal){
        while(l<r){
            while(arr[++l]<pivotVal);
            while(r>0 && arr[--r]>pivotVal);
            swap(arr,l,r);
        }
        swap(arr, l ,r);
        return l;
    }
    quickSort(nums,0,nums.length-1);
    return nums;
};

对序列 [15，142，51，68，85，46，57，75，60，89，121] 快速排序，假定初始 pivotindex 为4 1. 初始 privot 移动至末端
2. 第一次分组
3. 第二次分组
3. 第三四次分组
5. 结果

优化：三项切分快排

原始快排的“左右指针”分别找“比 pivotVal 大的元素”和“比 pivotVal 小的元素”，任由“等于 pivotVal 的元素”原地不动，在下一级迭代排序中继续参与排序

// 原始快排左右指针移动
while(l<r){
  while(arr[++l]<pivotVal);
  while(arr[--r]>pivotVal);
  swap(arr,l,r);
}

当序列中存在大量重复数据时，如果能在当前排序中将“等于 pivotVal 的元素”收集在中间，在下一级迭代中只排序中间项“比 pivotVal 大的元素”和“比 pivotVal 小的元素”，就能显著减少每次待排序的元素数，因此产生了三项切分快排

var sortArray = function(nums) {
    const swap = function(arr, i, j){
        let temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
    const quickSort = function(arr, l, r){
        if(l>=r) return;
        let lt = l, curr = l+1, gt = r;
        let pivot = arr[lt]; // 每次排序以arr[l]作为基准，[lt,gt]间保存与之相同的值
        while(curr<=gt){
            if(arr[curr]<pivot) swap(arr, lt++, curr++);
            else if(arr[curr]>pivot)swap(arr, curr, gt--);
            else curr++;
        }
        quickSort(arr, l, lt-1); // [l, lt-1]间元素都小于pivot
        quickSort(arr, gt+1, r); // [gt+1, r]间元素都大于pivot
    }
    quickSort(nums,0,nums.length-1);
    return nums;
};

7. 堆排序（Heap Sort）

堆排序是指利用堆这种数据结构所设计的一种排序算法 Ch5. 二叉树-堆(heap)

• 将初始待排序关键字序列(R1，R2 … Rn)构建成大顶堆，此堆为初始的无序区；
• 执行swap()，此时无序区最大元素移至序列末端构成有序区，无序区size-1，有序区size+1
• 不断执行第二步，直到无序区变空

var sortArray = function(nums) {
    const swap = function(arr, i, j){
        let temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
    // 下沉操作
    const siftdown = function(arr,i,len){
        while(i*2+1<len){
            let j=i*2+1;
            if(j+1<len && arr[j]<arr[j+1]) j++;
            if(arr[i]>arr[j]) return;
            swap(arr, i, j);
            i = j;
        }
    }
    // 建堆
    const buildHeap = function(arr){
        for(let i=((arr.length>>1)-1); i>=0; i--){
            siftdown(arr, i, arr.length);
        }
    }
    // 排序
    const heapSort = function(arr){
        buildHeap(arr);
        for(let i=arr.length-1; i>=0; i--){
            swap(arr, 0, i);
            siftdown(arr, 0, i);
        }
    }
    heapSort(nums);
    return nums;
};

堆排序复杂度分析：
参考链接：堆排序的时间复杂度分析
堆排序流程：

1. 先构造大顶堆
2. 每次交换堆顶（当前最大元素）和无序区最后一个元素，有序区元素加一，无序区元素减一，堆顶重新下沉到合适位置，不断重复，直到无序区只有最后一个元素

复杂度

• 建堆：siftdown() 的复杂度取决于以 a[i] 为 root 的子树高度——O(logn)。从倒数第二层开始建堆（循环次数数 n//2 ），开始树高为1，不断向上，
• 排序重建堆过程：n-1次循环，每次执行siftdown，但结点数也减一，近似为
• 总时间复杂度为

8. 分配排序/桶排序（Bin Sort/Bucket Sort）

• 简单分配

直接把关键值放在对应下标数组元素(一个桶)中：若A[1]=3，则令B[A[1]]=A[1]=3

for (i=0; i<n; i++)
    B[A[i]] = A[i];

局限：

1. 关键字不可重复(1个bin中一个元素)
2. 数组size=关键字最大值MaxKey+1
3. 关键字必须为非负整数

• 扩展分配

构建一个以链表为元素的数组B[]，A[]的重复键值可放入一个元素中，共有(MaxKey+1)个桶，最终从B[]的首元素开始遍历每个链表和链表中的元素，输出序列即为有序序列

function countingSort(arr, maxKey) {
    var bucket = new Array(maxKey + 1),
        sortedIndex = 0;
        arrLen = arr.length,
        bucketLen = maxKey + 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;
}

局限：

1. 数组size=关键字最大值MaxKey+1，当MaxKey很大时B的开销很大

复杂度：

9. 基数排序（Radix Sort）

基数排序也叫按位排序

• 确定关键值 maxDigit 和其位数k
• 从低位到高位进行k趟排序，第i趟根据第i对上一趟结果进行桶排序

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;
}

复杂度：

• d 为位数，r 为基数，n 为原数组个数。
• 在基数排序没有比较操作，所以最好的情况与最坏的情况在时间上是一致的