排序算法

1. 排序算法的定义

在计算机科学与数学中，一个排序算法（英语：Sorting algorithm）是一种能将一串资料依照特定排序方式排列的算法。

2. 排序算法的分类标准

计算的时间复杂度：使用大O表示法，也可以实际测试消耗的时间；

内存使用量（甚至是其他电脑资源）：比如外部排序，使用磁盘来存储排序的数据；

稳定性：稳定排序算法会让原本有相等键值的纪录维持相对次序；

排序的方法：插入、交换、选择、合并等等；

3. 常见的排序算法

冒泡排序、 选择排序、 插入排序     【简单，易理解】

归并排序、快速排序                        【非常重要，面试必考】

堆排序、希尔排序                            【了解即可】

计数排序、 桶排序、 基数排序、 内省排序、 平滑排序  【了解即可】

辅助记忆

• 时间复杂度记忆-

1. 冒泡、选择、直接 排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O(n²)）（一遍找元素O(n)，一遍找位置O(n)）

2. 快速、归并、希尔、堆基于二分思想，log以2为底，平均时间复杂度为O(nlogn)（一遍找元素O(n)，一遍找位置O(logn)）

• 稳定性记忆-“快希选堆”（快牺牲稳定性）

1. 排序算法的稳定性：排序前后相同元素的相对位置不变，则称排序算法是稳定的；否则排序算法是不稳定的。

排序算法的时间复杂度和空间复杂度

排序算法	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	稳定性
冒泡排序	O(n²)	O(n²)	O(n)	O(1)	稳定
直接选择排序	O(n²)	O(n²)	O(n)	O(1)	不稳定
直接插入排序	O(n²)	O(n²)	O(n)	O(1)	稳定
快速排序	O(nlogn)	O(n²)	O(nlogn)	O(nlogn)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定
希尔排序	O(nlogn)	O(ns)	O(n)	O(1)	不稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定
计数排序	O(n+k)	O(n+k)	O(n+k)	O(n+k)	稳定
基数排序	O(N*M)	O(N*M)	O(N*M)	O(M)	稳定

1.选择排序

算法思想：

首先在未排序的数列中找到最小元素，然后将其存放到数列的起始位置；

接着，再从剩余未排序的元素中继续寻找最小元素，然后放到已排序序列的末尾。

以此类推，直到所有元素均排序完毕。

2. 流程分析

【默认由小到大排序】

核心：内层的一轮循环比较下来，找到选择出来minIndex的位置，然后看是否需要交换

A. 遍历数组，找到未排序部分的最小值

(1) 首先，将未排序部分的第一个元素标记为最小值

(2) 然后，从未排序部分的第二个元素开始遍历，依次和已知的最小值进行比较

(3) 如果找到了比最小值更小的元素，就更新最小值的位置

B. 将未排序部分的最小值放置到已排序部分的后面

(1) 首先，用解构赋值的方式交换最小值和已排序部分的末尾元素的位置(即调用swap方法)

(2) 然后，已排序部分的长度加一，未排序部分的长度减一

C. 重复执行步骤 1 和 2，直到所有元素都有序

/*
 * 02-选择排序
 * 优化1-内层一轮，最多只交换1次
 * 10万数据 selectionSort1 20s  selectionSort2 7s
 * @param arr 待排序的数组
 * @returns 从小到大排序的数据
 */
function selectionSort2(arr: number[]): number[] {
    let length = arr.length;
    //假设长度length为4  [5,3,7,1], 最外层循环为3次, 即length-1, 剩下的最后一个一定是最大的
    for (let i = 0; i < length - 1; i++) {
        let minIndex = i;
        //内层：决定从哪个位置开始选择，直到渠道最后一个元素结束
        for (let j = i + 1; j < length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        //判断比较
        if (minIndex !== i) {
         let temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
    return arr;
}

4. 时间复杂度

(1).最好情况时间复杂度：O(n^2)

最好情况是指待排序的数组本身就是有序的。

在这种情况下，内层循环每次都需要比较 n-1 次，因此比较次数为 n(n-1)/2，交换次数为 0。 所以，选择排序的时间复杂度为 O(n^2)。

(2).最坏情况时间复杂度：O(n^2)

最坏情况是指待排序的数组是倒序排列的。

在这种情况下，每次内层循环都需要比较 n-i-1 次，因此比较次数为 n(n-1)/2，交换次数也为 n(n-1)/2。所以，选择排序的时间复杂度为 O(n^2)。

(3).平均情况时间复杂度：O(n^2)

平均情况是指待排序的数组是随机排列的。

在这种情况下，每个元素在内层循环中的位置是等概率的，因此比较次数和交换次数的期望值都是 n(n-1)/4。所以，选择排序的时间复杂度为 O(n^2)。

5. 总结

虽然选择排序的实现非常简单，但是它的时间复杂度较高，对于大规模的数据排序效率较低。

如果需要对大规模的数据进行排序，通常会选择其他更为高效的排序算法，例如快速排序、归并排序等。

总的来说，选择排序适用于小规模数据的排序和排序算法的入门学习，对于需要高效排序的场合，可以选择其他更为高效的排序算法。

2.冒泡排序

算法思想：冒泡排序（bubble sort）通过连续地比较与交换相邻元素实现排序。这个过程就像气泡从底部升到顶部一样，因此得名冒泡排序。

冒泡排序的工作原理是重复地遍历待排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

从第一个元素开始，逐一比较相邻元素的大小。

如果前一个元素比后一个元素大，则交换位置。

在第一轮比较结束后，最大的元素被移动到了最后一个位置。

在下一轮比较中，不再考虑最后一个位置的元素，重复上述操作。

每轮比较结束后，需要排序的元素数量减一，直到没有需要排序的元素。

排序结束。

这个流程会一直循环，直到所有元素都有序排列为止。

算法代码

javascript
function bubbleSort(arr) {  
    let len = arr.length;  
    for (let i = 0; i < len - 1; i++) {  
        for (let j = 0; j < len - 1 - i; j++) {  
            if (arr[j] > arr[j + 1]) { // 相邻元素两两对比  
                let temp = arr[j + 1]; // 元素交换  
                arr[j + 1] = arr[j];  
                arr[j] = temp;  
            }  
        }  
    }  
    return arr;  
}  

// 测试冒泡排序函数  
let arr = [3, 2, 4, 1, 5];  
console.log('原始数组：', arr);  
let sortedArr = bubbleSort(arr);  
console.log('排序后的数组：', sortedArr);
在这个实现中，
* 外层循环控制所有需要遍历的次
* 内层循环则负责每次遍历中的相邻元素比较和交换。
当没有需要交换的元素时，排序就完成了。

3. 推导过程

(1). 假设数组的长度length=4, 需要对其进行排序

(2). 显而易见, 需要进行3轮排序，即length-1轮

(3). 第1轮需要两两比较3次(length-1), 第2轮两两比较2次(length-1-1)，第3轮两两比较1次(length-1-2)，即length-1-i (i依次0,1,2)

(4). 以第1轮为例，为什么是length，而不是length-1？(这里指的是内层循环)

因为：arr[j+1]中的j+1最大只能是3,如果这里用length就越界了，所以此处是length-1

(5).上述进行三轮的代码可以总结为两个for循环，最外层决定需要进行几轮排序,内层决定两两比较几次和交换

(6). 补充：外层循环写成i<length 是否可以呢？

答：是可以的。还是以length=4为例,显而易见进行3轮排序即可, 虽然这里用的i<length，但是当i=3的时候，内层 j=length-1-i=0, 根本不走内层循环了

所以还是进行了3轮排序。

冒泡排序的平均时间复杂度是 O(n^2)，冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。

/**
 * 01-冒泡的推导过程
 * @param arr 待排序的数组
 * @returns 返回从小到大排序后的数组
 */
function BundleSort1(arr: number[]): number[] {
    let length = arr.length; //测试的长度为4,只需要进行3轮比较即可

    //第1轮循环比较(arr[j+1]中的j+1最大只能是3,否则越界，所以此处是length-1)
    for (let j = 0; j < length - 1; j++) {
        if (arr[j] > arr[j + 1]) {
            //交换
            let temp = arr[j + 1];
            arr[j + 1] = arr[j];
            arr[j] = temp;
        }
    }
    //第2轮循环比较
    for (let j = 0; j < length - 1 - 1; j++) {
        if (arr[j] > arr[j + 1]) {
            //交换
            let temp = arr[j + 1];
            arr[j + 1] = arr[j];
            arr[j] = temp;
        }
    }
    //第3轮循环比较
    for (let j = 0; j < length - 1 - 2; j++) {
        if (arr[j] > arr[j + 1]) {
            //交换
            let temp = arr[j + 1];
            arr[j + 1] = arr[j];
            arr[j] = temp;
        }
    }
    return arr;
}

/**
 * 02-冒泡排序，合并推导
 * @param arr 待排序的数组
 * @returns 返回从小到大排序后的数组
 */
function BundleSort2(arr: number[]): number[] {
    let length = arr.length; // 测试的长度为4,只需要进行3轮比较即可
    //最外层：决定需要进行几轮比较
    for (let i = 0; i < length - 1; i++) {
        //内层：决定需要进行哪些两两大小比较
        for (let j = 0; j < length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                //交换
                let temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

4. 代码优化

(2).优化循环次数

如果再第二层循环中没有进行交换操作，就说明现在已经排序好了，直接跳出外层循环即可

/**
 * 04-冒泡排序
 * 优化2：减少最外层循环的轮数
 * @param arr 待排序的数组
 * @returns 返回从小到大排序后的数组
 */
function BundleSort4(arr: number[]): number[] {
    let length = arr.length; // 测试的长度为4,只需要进行3轮比较即可
    //最外层：决定需要进行几轮比较
    for (let i = 0; i < length - 1; i++) {
        let isSwap = false;
        //内层：决定需要进行哪些两两大小比较
        for (let j = 0; j < length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1); //交换
                isSwap = true;
            }
        }
        //只要前一轮没有进行交换,就不需要进行了
        if (isSwap == false) {
            console.log(`常规需要进行${length - 1}轮,优化后${i}轮`);
            break; //退出最外层循环
        }
    }
    return arr;
}

5. 改为由小到大

PS:直接一步到位，最佳写法， 实际上就是改为 arr[j] < arr[j+1]

/**
 * 04-冒泡排序
 * 改为：从大到小排序
 * @param arr 待排序的数组
 * @returns 返回从小到大排序后的数组
 */
function BundleSort5(arr: number[]): number[] {
    let length = arr.length; // 测试的长度为4,只需要进行3轮比较即可
    //最外层：决定需要进行几轮比较
    for (let i = 0; i < length - 1; i++) {
        let isSwap = false;
        //内层：决定需要进行哪些两两大小比较
        for (let j = 0; j < length - 1 - i; j++) {
            if (arr[j] < arr[j + 1]) {
                swap(arr, j, j + 1); //交换
                isSwap = true;
            }
        }
        //只要前一轮没有进行交换,就不需要进行了
        if (isSwap == false) {
            console.log(`常规需要进行${length - 1}轮,优化后${i}轮`);
            break; //退出最外层循环
        }
    }
    return arr;
}

6. 时间复杂度分析

(1). 最好 O(n)

即待排序的序列已经是有序的。 此时仅需遍历一遍序列，不需要进行交换操作。

(2) .最坏 O(n^2)

即待排序的序列是逆序的。需要进行n-1轮排序，每一轮中需要进行n-1-i次比较和交换操作。

(3).平均 O(n^2)

即待排序的序列是随机排列的。每一对元素的比较和交换都有1/2的概率发生，因此需要进行n-1轮排序，每一轮中需要进行n-i-1次比较和交换操作。

总结：冒泡排序的时间复杂度主要取决于数据的初始顺序，最坏情况下时间复杂度是O(n^2)，不适用于大规模数据的排序。

8. 总结

冒泡排序适用于数据规模较小的情况，因为它的时间复杂度为O(n^2)，对于大数据量的排序会变得很慢。

◼ 同时，它的实现简单，代码实现也容易理解，适用于学习排序算法的初学者。

◼ 但是，在实际的应用中，冒泡排序并不常用，因为它的效率较低。

◼ 因此，在实际应用中，冒泡排序通常被更高效的排序算法代替，如快速排序、归并排序等。

3.插入排序

1. 定义

(1).首先假设第一个数据是已经排好序的，接着取出下一个数据，在已经排好序的数据中从后往前扫描，找到比它小的数的位置，将该位置之后的数整体后移一个单位，然后再将该数插入到该位置。

(2).不断重复上述操作，直到所有的数据都插入到已经排好序的数据中，排序完成。

2. 流程分析

① 首先，假设数组的第一个元素已经排好序了，因为它只有一个元素，所以可以认为是有序的。

② 然后，从第二个元素开始，不断与前面的有序数组元素进行比较。

③ 找到比它小的数的位置，将该位置之后的数整体后移一个单位。然后再将该数插入到该位置。

④ 否则，继续与前面的有序数组元素进行比较。

⑤ 以此类推，直到整个数组都有序。

⑥ 循环步骤2~5，

3. 代码实操

最后为什么是 arr[j + 1] = insertItem;

可以从这个角度理解，假设insetItem比arr[0]还小，此时跳出while后j=-1，肯定是j+1=0 来赋值了

function insertionSort(arr: number[]): number[] {
    let length = arr.length;
    //第一层：表示从第i个元素,(表示需要进行几轮比较)
    for (let i = 1; i < length; i++) {
        //第二层：依次与前面有序数组进行比较
        let j = i - 1;
        let insertItem = arr[i];
        while (arr[j] > insertItem && j >= 0) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = insertItem;
    }
    return arr;
}

4. 时间复杂度

(1) 最好情况： O(n)

 如果待排序数组已经排好序

 那么每个元素只需要比较一次就可以确定它的位置，因此比较的次数为 n-1，移动的次数为 0。

 所以最好情况下，插入排序的时间复杂度为线性级别，即 O(n)。

(2) 最坏情况： O(n^2)

 如果待排序数组是倒序排列的

 那么每个元素都需要比较和移动 i 次，其中 i 是元素在数组中的位置。

 因此比较的次数为 n(n-1)/2，移动的次数也为 n(n-1)/2。

 所以最坏情况下，插入排序的时间复杂度为平方级别，即 O(n^2)。

(3) 平均情况  O(n^2)：

 对于一个随机排列的数组，插入排序的时间复杂度也为平方级别，即 O(n^2)。

5. 总结

(1) 如果数组部分有序，插入排序可以比冒泡排序和选择排序更快。但是如果数组完全逆序，则插入排序的时间复杂度比较高，不如快速排序或归并排序。

(2) 插入排序虽然没有快速排序和归并排序等高级排序算法的复杂性和高效性，但是它的实现非常简单，而且在一些特定的场景下表现也很好。

4、归并排序

1. 定义

它的基本思想是将待排序数组分成若干个子数组。然后将相邻的子数组归并成一个有序数组。最后再将这些有序数组归并（merge）成一个整体有序的数组。

2. 流程

步骤一： 分解（Divide）：归并排序使用递归算法来实现分解过程，具体实现中可以分为以下几个步骤：

① 如果待排序数组长度为1，认为这个数组已经有序，直接返回；

② 将待排序数组分成两个长度相等的子数组，分别对这两个子数组进行递归排序；

③ 将两个排好序的子数组合并成一个有序数组，返回这个有序数组。

步骤二： 合并（Merge）：合并过程中，需要比较每个子数组的元素并将它们有序地合并成一个新的数组：

① 可以使用两个指针 i 和 j 分别指向两个子数组的开头，比较它们的元素大小，并将小的元素插入到新的有序数组中。

② 如果其中一个子数组已经遍历完，就将另一个子数组的剩余部分直接插入到新的有序数组中。

③ 最后返回这个有序数组。

步骤三： 归并排序的递归终止条件：

归并排序使用递归算法来实现分解过程，当子数组的长度为1时，认为这个子数组已经有序，递归结束。

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    var list = mergeSort(nums)
    return list
};

var mergeSort = function(nums){
    if(nums.length<2){
        return nums
    }
    var mid = Math.floor(nums.length/2)
    var left = mergeSort(nums.slice(0,mid))
    var right =mergeSort( nums.slice(mid))
    return megeList(left,right)
}

var megeList = function(l1,l2){
    var lIndex = 0,rIndex =0;
    var list = []
    while(lIndex<l1.length&&rIndex<l2.length){
        if(l1[lIndex]<l2[rIndex]){
            list.push(l1[lIndex++])
        } else {
            list.push(l2[rIndex++])
        }
    }
    while(lIndex<l1.length){
     list.push(l1[lIndex++])
    }
    while(rIndex<l2.length){
        list.push(l2[rIndex++])
    }
    return list
}

4. 时间复杂度

◼ 复杂度的分析过程：

 假设数组长度为 n，需要进行 logn 次归并操作；

 每次归并操作需要 O(n) 的时间复杂度；

 因此，归并排序的时间复杂度为 O(nlogn)。

◼ 最好情况： O(log n)

 最好情况下，待排序数组已经是有序的了，那么每个子数组都只需要合并一次，即只需要进行一次归并操作。

 因此，此时的时间复杂度是 O(log n)。

◼ 最坏情况： O(nlogn)

 最坏情况下，待排序数组是逆序的，那么每个子数组都需要进行多次合并。

 因此，此时的时间复杂度为 O(nlogn)。

◼ 平均情况： O(nlogn)

 在平均情况下，我们假设待排序数组中任意两个元素都是等概率出现的。

 此时，可以证明归并排序的时间复杂度为 O(nlogn)。

5.总结

(1).归并排序是一种非常高效的排序算法，它的核心思想是分治，即将待排序数组分成若干个子数组，分别对这些子数组进行排序，   最后将排好序的子数组合并成一个有序数组。

(2).归并排序的时间复杂度为 O(nlogn)，并且在最好、最坏和平均情况下都可以达到这个时间复杂度。

(3).虽然归并排序看起来比较复杂，但是只要理解了基本思路，实现起来并不困难，而且它是一种非常高效的排序算法

5.快速排序

1.定义

快速排序（Quick Sort）是一种基于分治思想的排序算法：

(1).基本思路是将一个大数组分成两个小数组，然后递归地对两个小数组进行排序。

(2) 具体实现方式是通过选择一个基准元素（pivot），将数组分成左右两部分，左部分的元素都小于或等于基准元素，右部分的元素都大于基准元素。

(3) 然后，对左右两部分分别进行递归调用快速排序，最终将整个数组排序。

2. 流程

① 首先，我们需要选择一个基准元素，通常选择第一个或最后一个元素作为基准元素。

② 然后，我们定义两个指针 i 和 j，分别指向数组的左右两端。(j指向是right-1的位置,right代表pivot的位置)

③ 接下来，我们从右侧开始，向左移动 j 指针，直到找到一个小于或等于基准元素的值。

④ 然后，我们从左侧开始，向右移动 i 指针，直到找到一个大于或等于基准元素的值。

⑤ 如果 i 指针小于或等于 j 指针，交换 i 和 j 指针所指向的元素。

⑥ 重复步骤 3-5，直到 i 指针大于 j 指针，这时，我们将基准元素与 j 指针所指向的元素交换位置，将基准元素放到中间位置。

⑦ 接着，我们将数组分为两部分，左侧部分包含小于或等于基准元素的元素，右侧部分包含大于基准元素的元素。

⑧ 然后，对左右两部分分别进行递归调用快速排序，直到左右两部分只剩下一个元素。

⑨ 最终，整个数组就变得有序了。

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
   var list = quickSort(nums,0,nums.length-1)
    return list
};

var quickSort = function(list,left,right){
   if(left<right){
       var pivot = getPivot(list,left,right)
       quickSort(list,left,pivot-1)
       quickSort(list,pivot+1,right)
   }
   return list
}


var getPivot = function(list,left,right){
    var obj = list[left]
    while(left<right){
        mid = Math.floor(left+(right-left)/2)
        while(left<right&&obj<=list[right]){
            right --
        }
         swapArray(list,left,right)
        while(left<right&&obj>=list[left]){
           left++
        }
        swapArray(list,left,right)
    }
    return left
}

var swapArray = function(list,left,right){
    var temp = list[left]
    list[left] = list[right]
    list[right] = temp
}

3. 时间复杂度

(1) 最好情况： O(nlogn)

当每次划分后，两部分的大小都相等，即基准元素恰好位于数组的中间位置，此时递归的深度为 O(log n)。

每一层需要进行 n 次比较，因此最好情况下的时间复杂度为 O(nlogn)。

(2) 最坏情况： O(n^2)

当每次划分后，其中一部分为空，即基准元素是数组中的最大或最小值，此时递归的深度为 O(n)。

每一层需要进行 n 次比较，因此最坏情况下的时间复杂度为 O(n^2)。

需要注意的是，采用三数取中法或随机选择基准元素可以有效避免最坏情况的发生。

(3) 平均情况： O(nlogn)

在平均情况下，每次划分后，两部分的大小大致相等，此时递归的深度为 O(log n)

每一层需要进行大约 n 次比较，因此平均情况下的时间复杂度为 O(nlogn)。

注：快速排序是一个原地排序算法，不需要额外的数组空间。

4. 总结

快速排序的性能优于许多其他排序算法，因为它具有良好的局部性和使用原地排序的优点。

它在大多数情况下的时间复杂度为 O(n log n)，但在最坏情况下会退化到 O(n^2)。

为了避免最坏情况的发生，可以使用一些优化策略，比如随机选择基准元素和三数取中法。