笔记大全

TypeScript十大排序算法插入排序怎么实现

更新时间：2024-01-07

插入排序算法概述

插入排序算法是一种简单的排序算法，它的基本思想是将待排序的元素插入到已经有序的子序列中。插入排序算法是基于比较的排序算法，时间复杂度为O(n^2)。虽然时间复杂度较高，但是在小规模数据排序和部分有序数据排序的情况下，插入排序算法的效率较高。

function insertionSort(arr: number[]): number[] {
  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 arr: number[] = [5, 2, 4, 6, 1, 3];
const result: number[] = insertionSort(arr);
console.log(result); // Output: [1, 2, 3, 4, 5, 6]

插入排序算法思路

插入排序算法的过程可以描述为：将第一个元素看做有序的自序列，然后依次将后面的元素插入到有序的自序列中。对于未排序自序列中的每一个元素，将其插入到已排序自序列的合适位置中。

以下是插入排序算法的详细步骤：

从第二个元素开始遍历，将当前元素保存在缓存变量current中
将current与已排序的子序列从右向左进行比较，寻找合适的插入位置
移动已排序子序列中比current大的元素，为current腾出插入位置
将current插入到已排序子序列中的合适位置
重复2-4步骤，直到遍历结束，即得到已排好序的序列

插入排序算法代码解释

上面的插入排序算法代码中采用了for循环和while循环两种循环结构，对于循环结构的选择主要根据编程者的编程习惯和个人喜好来决定。首先定义一个current变量，这个变量用来缓存当前需要排序的元素。然后将current逐一与已排序的子序列进行比较，找到合适的插入位置。已排序子序列的比较是从右向左进行，当找到比current大的元素时，需要将这个元素向右移动一位，为current腾出插入位置。最后将current插入到已排序子序列中的合适位置。重复这个过程，直到遍历完所有元素，并得到已排好序的序列。

插入排序算法优化

插入排序算法可以用于部分有序的数据排序，但是对于完全无序的大规模数据排序，效率并不高。为了提高插入排序算法的效率，可以对其进行优化。以下是几种优化方法：

1.二分插入排序算法

对于大规模的数据排序，插入排序算法中最耗时间的操作是元素的移动。在已排好序的子序列中查找合适的插入位置，可以采用二分查找的方式，查找时间可以从O(n)的线性时间降到O(logn)的对数时间。采用二分插入排序算法的时间复杂度为O(n^2)。

function binaryInsertionSort(arr: number[]): number[] {
  for (let i = 1; i < arr.length; i++) {
    let current = arr[i];
    let left = 0,
      right = i - 1;
    while (left <= right) {
      let mid = Math.floor((left + right) / 2);
      if (arr[mid] > current) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    for (let j = i - 1; j >= left; j--) {
      arr[j + 1] = arr[j];
    }
    arr[left] = current;
  }
  return arr;
}

const arr: number[] = [5, 2, 4, 6, 1, 3];
const result: number[] = binaryInsertionSort(arr);
console.log(result); // Output: [1, 2, 3, 4, 5, 6]

2.希尔排序算法

希尔排序算法是对插入排序算法的改进，它引入了一个增量序列，将待排序元素按照一定间隔进行分组，对每个分组采用插入排序算法进行排序。增量的选择是希尔排序算法的关键，不同的增量序列对排序效率的影响也不同。在增量序列为1时，希尔排序算法退化为普通的插入排序算法。希尔排序算法的时间复杂度约为O(n^1.3)。

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

const arr: number[] = [5, 2, 4, 6, 1, 3];
const result: number[] = shellSort(arr);
console.log(result); // Output: [1, 2, 3, 4, 5, 6]

总结

插入排序算法是一种简单但是效率较低的排序算法，适合用于小规模数据或者部分有序数据排序。它的优化算法有二分插入排序算法和希尔排序算法。二分插入排序算法通过减少数据比较次数来提高排序效率，而希尔排序算法通过引入增量序列来将待排序元素分组，从而对每个分组采用插入排序算法进行排序，从而提高排序效率。

c语言编程笔录