Java中的插入排序

如果你是一名程序员，你一定已经听说过很多排序。排序基本上是按升序或降序排列元素。有很多排序算法可用于对元素进行排序，并且每种算法都有不同的排序方式、不同的复杂度。所以使用哪种算法取决于具体的场景和元素的数量。插入也是常用的排序算法之一，复杂度为 O(n^2)，就像我们对手中的扑克牌进行排序一样。在本主题中，我们将学习 Java 中的插入排序。

开始您的免费软件开发课程

网络开发、编程语言、软件测试及其他

Java 中插入排序是如何工作的？

让我们通过一个例子来了解插入排序的工作原理。

假设有一个名为 arr 的数组，其中包含以下元素：

10 5 8 20 30 2 9 7

步骤#1 – 插入排序从数组的第二个元素（即 5）开始，考虑数组的第一个元素本身。现在将元素 5 与 10 进行比较，因为 5 小于 10，所以将 10 向前移动 1 个位置，并在其前面插入 5。

现在结果数组是：

5 10 8 20 30 2 9 7

步骤 #2 – 现在将元素 arr[2]（即 8）与元素 arr[1]（即 10）进行比较。由于 8 比其前面的元素 10 小，因此将其移位一位从它的位置向前一步，然后与5比较。由于8大于5，所以将其插入到它的后面。

那么结果数组是：

5 8 10 20 30 2 9 7

第 3 步 – 现在将元素 20 与 10 进行比较，因为它大于 10，因此它保持在原来的位置。

5 8 10 20 30 2 9 7

步骤 #4 – 将元素 30 与 20 进行比较，由于它大于 20，因此不会进行任何更改，数组保持原样。现在数组将是

5 8 10 20 30 2 9 7

步骤 #5 – 元素 2 与 30 进行比较，因为它小于 30，所以向前移动一位，然后与 20,10,8,5 逐一进行比较，所有元素都移动到前面 1 个位置，并且 2 个元素插入到 5 个元素之前。

结果数组是：

2 5 8 10 20 30 9 7

步骤 #6 – 将元素 9 与 30 进行比较，因为它小于 30；与20、10一一比较，元素向前移动1位，9插入到10之前、8之后。

结果数组是：

2 5 8 9 10 20 30 7

步骤 #7 – 元素 7 与 30 比较，由于它小于 30，因此与 30, 20, 10, 9, 8 比较，所有元素都移动 1 个位置一一向前，7插在8之前。

生成的数组将变为：

2 5 7 8 9 10 20 30

这样，数组的所有元素都使用插入排序进行排序，开始与前面的元素进行比较。

在 Java 中实现插入排序的示例

Java中的插入排序是一种简单的排序算法，适用于所有小数据集。

代码：

public class InsertionSort {
public static void insertionSort(int arr[]) { for (int j = 1; j < arr.length; j++) { int key = arr[j]; int i = j-1;
while ( (i > -1) && ( arr[i] > key ) ) { arr[i+1] = arr[i]; i--; }
arr[i+1] = key;
}
}
static void printArray(int arr[]) { int len = arr.length;
//simple for loop to print the elements of sorted array for (int i= 0; i<len; i++)
System.out.print(arr[i] + " " );
System.out.println();
}
public static void main(String args[]){ int[] arr1 = {21,18,15,23,52,12,61};
//calling the sort function which performs insertion sort insertionSort(arr1);
//calling the printArray function which performs printing of array printArray(arr1);
}
}

输出：

12 15 18 21 23 52 61

说明：

• 在上面的插入排序程序中，insertionSort()函数用于对原始数组元素进行排序。排序从第二个元素开始，因为第一个元素认为本身已排序。所以‘j’的循环是从数组的索引1开始的。 “i”是跟踪“j”之前索引的变量，以便比较值。”
• key' 是保存要排列在排序位置的当前元素的值的变量。如果当前值小于最左边的值，则执行while()循环，进行元素的移位，最后将当前元素插入到右侧位置。 printArray() 函数用于最终打印排序后的数组。

1.最佳案例

在插入排序中，最好的情况是数组的所有元素都已排序。因此，当任何元素与其最左边的元素进行比较时，它总是更大，因此不会处理元素的移位和插入。在这种情况下，最好的情况复杂度是线性的，即 O(n)。

2.最坏的情况

在上面的插入排序代码中，最坏的情况是数组处于逆序状态，因此每次将元素与最左边的元素进行比较时，它总是较小，然后与所有前面的元素进行比较放置、移动和插入完成。在这种情况下，插入排序的复杂度是 O(n^2)。

3.平均情况

即使在平均情况下，插入排序也具有 O(n^2) 复杂度，其中某些元素不需要移位，而某些元素会从其位置移位并在正确位置执行插入。

4.最佳使用

插入排序最适合当数组的大小不是很大，或者只需要对少量元素进行排序，几乎所有元素都已排序，只需要进行一些更改时。插入排序是小尺寸数组最快的算法之一，甚至比快速排序还要快。事实上，快速排序在对数组的小部分进行排序时使用插入排序。

结论

上面的解释清楚地展示了Java中插入排序的工作原理和实现。在其他编程语言中，执行插入排序的逻辑也保持不变，只是语法发生了变化。在实现任何排序算法之前，对需要排序的场景进行一些分析非常重要，因为并不是每种排序算法都适合所有场景。

以上是Java中的插入排序的详细内容。更多信息请关注PHP中文网其他相关文章！