一. 插入排序的定义
插入排序就像是你打扑克牌,你从牌堆顶取一张牌,找到合适的位置插入到已有牌的顺序中,并不断重复这一步骤直到所有的牌都被 插入到合适的位置,最终使得整副牌有序。
与打牌类似,插入排序(Insertion sort)的实现方法是:
- 首先假设第一个数据是已经排好序的,接着取出下一个数据,在已经排好序的数据中从后往前扫描,找到比它小的数的位置,将该位置之后的数整体后移一个单位,然后再将该数插入到该位置。
- 不断重复上述操作,直到所有的数据都插入到已经排好序的数据中,排序完成。
插入排序的优势在于它的性能表现在已经有序的序列上比冒泡排序、选择排序两种算法要好。
- 它的时间复杂度为O(n),因此,如果序列已经被排好,插入排序将会比冒泡排序和选择排序快得多。
- 另外,插入排序空间复杂度为O(1),因此,对于内存限制较小的情况,插入排序也是一个更优的选择。
二. 插入排序的流程
插入排序的流程如下:
- 首先,假设数组的第一个元素已经排好序了,因为它只有一个元素,所以可以认为是有序的。
- 然后,从第二个元素开始,不断与前面的有序数组元素进行比较。
- 如果当前元素小于前面的有序数组元素,则把当前元素插入到前面的合适位置。
- 否则,继续与前面的有序数组元素进行比较。
- 以此类推,直到整个数组都有序。
- 循环步骤2~5,直到最后一个元素。
- 完成排序。
三. 插入排序的图解
四. 插入排序的代码
以下是 TypeScript 实现的插入排序代码,带有详细的注释:
function insertionSort(arr: number[]): number[] { // 对于数组的每一个元素,从它开始到0位置,比较该元素和前一个元素的大小 for (let i = 1; i < arr.length; i++) { let current = arr[i]; let j = i - 1; // 如果该元素小于前一个元素,那么前一个元素向后移动,并继续向前比较 while (j >= 0 && arr[j] > current) { arr[j + 1] = arr[j]; j--; } // 如果该元素大于前一个元素,那么它将放到合适的位置 arr[j + 1] = current; } // 返回排序后的数组 return arr; } // 测试数据 const testArr = [5, 2, 9, 1, 5, 6]; // 调用插入排序函数 const sortedArr = insertionSort(testArr); // 打印结果 console.log(sortedArr);
代码执行的过程:
- 首先我们定义了一个
insertSort
函数,并传入一个数字数组作为参数。 - 接着我们定义一个变量
current
,它将存储当前需要比较的数字。 - 然后我们使用一个循环,将数组的第二项到最后一项依次与前面的数字进行比较。
- 在内层循环中,我们首先将
j
定义为i-1
,然后每次执行循环时,如果j
大于等于 0 并且arr[j]
大于current
,我们就交换arr[j]
和arr[j + 1]
的值。 - 在循环结束后,我们将
current
插入到正确的位置,并继续比较下一个数字。 - 当所有数字都被比较过后,我们就可以返回最终排序好的数组。
五. 插入排序的时间复杂度
插入排序的时间复杂度在最好的情况下为O(n),在最坏的情况下为O(n^2),平均时间复杂度为O(n^2)。
当数据已经有序时,插入排序只需要做n-1次比较和0次移动,运行时间为O(n);
当数据完全逆序时,插入排序需要做n-1趟比较和3/2*(n-1)^2/2次移动,运行时间为O(n^2)。
由于插入排序的最好时间复杂度与最坏时间复杂度都接近O(n^2),所以插入排序适用于数据规模不大的场合,如果数据规模很大,通常使用其他算法。
六. 插入排序的总结
- 插入排序是一种简单而直观的排序算法,它可以快速地对部分有序的数组进行排序。
- 插入排序通过比较相邻的元素并在需要时将其交换,来实现从小到大的排列。
- 插入排序的时间复杂度在最好情况下是线性O(n),最坏情况下是O(n^2)。
总而言之,如果数组部分有序,插入排序可以比冒泡排序和选择排序更快。
- 但是如果数组完全逆序,则插入排序的时间复杂度比较高,不如快速排序或归并排序。
- 因此,在选择排序算法时,应该根据需要选择合适的算法。
以上就是TypeScript十大排序算法插入排序实现示例详解的详细内容,更多关于TypeScript插入排序算法的资料请关注阿兔在线工具其它相关文章!