算法-插入排序

一、简介

插入排序是一种排序算法，它在每次迭代中将未排序的元素放置在合适的位置。虽然使用起来很简单，但它不适用于大型数据集，因为插入排序在平均情况和最坏情况下的时间复杂度为O(n 2 )，其中 n 是项目数。插入排序的效率低于其他排序算法，如堆排序、快速排序、合并排序等。

插入排序的工作原理类似于我们在纸牌游戏中对手中的纸牌进行排序。

我们假设第一张卡片已经排序，然后我们选择一张未排序的卡片。如果未排序的卡片大于手牌，则将其放在右侧，否则放在左侧。以同样的方式，其他未分类的卡片被取出并放在正确的位置。

插入排序优点：

• 简单的实现
• 对小型数据集有效
• 自适应，即它适用于已经基本排序的数据集。

二、工作原理

假设我们需要对以下数组进行排序，需要进行以下步骤：

初始化数组

1. 假定数组中的第一个元素已排序。取出第二个元素并将其单独存储在key中，并与第一个元素进行比较。如果第一个元素大于key，则把key放在第一个元素的前面。

如果第一个元素大于 key，则将 key 放在第一个元素的前面

2. 现在，前两个元素已排序。取第三个元素并将其与左侧的元素进行比较。将它放在比它小的元素后面。如果没有比它小的元素，则将其放在数组的开头。

3. 同样，将每个未排序的元素放在正确的位置。

三、JAVA实现

importjava.util.Arrays;
classInsertionSort {
voidinsertionSort(intarray[]) {
intsize=array.length;
for (intstep=1; step<size; step++) {
intkey=array[step];
intj=step-1;
// Compare key with each element on the left of it until an element smaller than// it is found.// For descending order, change key<array[j] to key>array[j].while (j>=0&&key<array[j]) {
array[j+1] =array[j];
--j;
      }
// Place key at after the element just smaller than it.array[j+1] =key;
    }
  }
//由此可以看出插入排序的时间复杂度为O(n 2 )