一. 归并排序的定义
归并排序(merge sort)是一种常见的排序算法:
- 它的基本思想是将待排序数组分成若干个子数组。
- 然后将相邻的子数组归并成一个有序数组。
- 最后再将这些有序数组归并(merge)成一个整体有序的数组。
这个算法最早出现在1945年,由约翰·冯·诺伊曼(John von Neumann)(又一个天才,现代计算机之父,冯·诺依曼结构、普林斯顿结构)首次提出。
- 当时他在为美国政 府工作,研究原子弹的问题。
- 由于当时计算机,他在研究中提出了一种高效计算的方法,这个方法就是归并排序。
归并排序的基本思路是先将待排序数组递归地拆分成两个子数组,然后对每个子数组进行排序,最后将两个有序子数组合并成一个有序数组。
- 在实现中,我们可以使用“分治法”来完成这个过程,即将大问题分解成小问题来解决。
归并排序的算法复杂度为 O(nlogn),是一种比较高效的排序算法,因此在实际应用中被广泛使用。
虽然归并排序看起来比较复杂,但是只要理解了基本思路,实现起来并不困难,而且它还是一个非常有趣的算法。
二. 归并排序的流程
归并排序是一种基于分治思想的排序算法,其基本思路可以分为三个步骤:
步骤一:分解(Divide):归并排序使用递归算法来实现分解过程,具体实现中可以分为以下几个步骤:
- 如果待排序数组长度为1,认为这个数组已经有序,直接返回;
- 将待排序数组分成两个长度相等的子数组,分别对这两个子数组进行递归排序;
- 将两个排好序的子数组合并成一个有序数组,返回这个有序数组。
步骤二:合并(Merge):合并过程中,需要比较每个子数组的元素并将它们有序地合并成一个新的数组:
- 可以使用两个指针 i 和 j 分别指向两个子数组的开头,比较它们的元素大小,并将小的元素插入到新的有序数组中。
- 如果其中一个子数组已经遍历完,就将另一个子数组的剩余部分直接插入到新的有序数组中。
- 最后返回这个有序数组。
步骤三:归并排序的递归终止条件:
- 归并排序使用递归算法来实现分解过程,当子数组的长度为1时,认为这个子数组已经有序,递归结束。
总体来看,归并排序的基本思路是分治法,分成子问题分别解决,然后将子问题的解合并成整体的解。
三. 归并排序的图解
四. 归并排序的代码
下面是TypeScript实现的归并排序代码,带有详细的注释:
// 定义函数mergeSort,参数是待排序数组arr function mergeSort(arr: number[]): number[] { // 计算数组长度 const n = arr.length; // 如果数组长度小于等于1,则直接返回该数组 if (n <= 1) { return arr; } // 计算中间位置 const middle = Math.floor(n / 2); // 对左边的数组进行归并排序 const left = mergeSort(arr.slice(0, middle)); // 对右边的数组进行归并排序 const right = mergeSort(arr.slice(middle)); // 合并两个排好序的数组 return merge(left, right); } // 定义函数merge,参数是两个排好序的数组left和right function merge(left: number[], right: number[]): number[] { // 定义指针变量,分别指向两个数组的开头 let i = 0, j = 0; // 定义一个空数组,用来存放合并后的数组 const result = []; // 比较两个数组的第一个元素,将较小的放入result数组 while (i < left.length && j < right.length) { if (left[i] < right[j]) { result.push(left[i++]); } else { result.push(right[j++]); } } // 将没有比较完的剩余元素放入result数组 while (i < left.length) { result.push(left[i++]); } while (j < right.length) { result.push(right[j++]); } // 返回合并后的数组 return result; } // 测试数据 const testArr = [5, 2, 9, 1, 5, 6]; // 调用插入排序函数 const sortedArr = mergeSort(testArr); // 打印结果 console.log(sortedArr);
代码执行的过程:
mergeSort
函数实现归并排序的递归调用,在该函数内,如果数组的长度小于等于1,直接返回该数组。- 如果数组的长度大于1,那么执行以下代码:
- 先计算数组的中点,并将数组分为左右两半。
- 递归调用左边和右边的数组,最终得到两个有序的数组。
merge
函数实现将两个有序的数组合并为一个有序的数组。
五. 归并排序的时间复杂度
复杂度的分析过程:
- 假设数组长度为 n,需要进行 logn 次归并操作;
- 每次归并操作需要 O(n) 的时间复杂度;
- 因此,归并排序的时间复杂度为 O(nlogn)。
最好情况: O(log n)
- 最好情况下,待排序数组已经是有序的了,那么每个子数组都只需要合并一次,即只需要进行一次归并操作。
- 因此,此时的时间复杂度是 O(log n)。
最坏情况: O(nlogn)
最坏情况下,待排序数组是逆序的,那么每个子数组都需要进行多次合并。
因此,此时的时间复杂度为 O(nlogn)。
平均情况: O(nlogn)
- 在平均情况下,我们假设待排序数组中任意两个元素都是等概率出现的。
- 此时,可以证明归并排序的时间复杂度为 O(nlogn)。
六. 归并排序的总结
归并排序是一种分治策略的排序算法,是利用分治的思想将一个大问题分成小问题,并在适当的地方合并它们以解决该问题的方法。
它是一种稳定的排序算法,时间复杂度为O(nlogn)。
归并排序使用了额外的空间,因此更适合处理大数据。
- 归并排序的基本流程是通过递归将数组分成两半,分别进行递归排序,最终再进行合并。
- 具体来说,将数组的中间元素作为分界点,分别对左右两边的数组进行排序,并在排序完成后进行合并。
归并排序的代码实现较为简单,但要注意关于递归函数和合并函数的实现。
归并排序是一种不需要过多研究的算法,适合于所有的排序场景。
以上就是TypeScript实现十大排序算法之归并排序示例详解的详细内容,更多关于TypeScript算法归并排序的资料请关注本站其它相关文章!