Java 中的插入排序

数组排序是 Java 初学者应该知道的最常见的操作之一。尽管数组并不总是排列数据的最方便方式，而且这主要适用于小数，但数组排序背后的概念在复杂的软件和数据科学中有大量应用。在这篇文章中，我们将仔细研究什么是插入排序。我们提供了一些示例和练习题来帮助您完全掌握这个概念。

什么是插入排序？

基本上，插入排序是开发人员用来组织小数字字符串的算法。它将所有值分成两个堆栈 - 一个已排序的堆栈和一个未排序的堆栈。一个一个地，“未排序”堆栈中的数字被挑选出来并按正确的顺序排列。让我们仔细看看插入排序的输入和输出：

• 输入：具有未排序数字元素的数组 A：A[0,1, n, n-2...]。
• 输出：包含相同数字但完全排序的数组。这个通常称为 B：B[0]B[1]...B[n-1]。

有几种使用插入排序的方法 - 以下是最流行的：

• 数值排序（升序）：[1, 2, 3, 4, 5]
• 数值排序（降序）：[5, 4, 3, 2, 1]
• 按字母排序：[a, b, c, d]

注意：如果你有一个空数组或一个单例，这些被认为是默认排序的。

理解插入排序理论

在探索插入排序背后的代码之前，让我们使用非技术语言分解算法。因为我们将展示升序排序的代码，所以在这篇文章中逐步解释算法是有意义的。 步骤 1.迭代 betweenarr[1]和arr[n]wheren是一个通常小于 10 的数值。 步骤 2.使用该方法将您选择的元素（称为key）与序列中的前一个数字进行比较sort()。 步骤 3.如果所有元素都小于它们的后继元素，重复比较直到找到更大的值。 第 4 步。交换一个较大的值超出较小的位置以创建有序序列。 步骤 5.重复这个过程，直到你得到一个排序好的字符串

排序原始数组

由于该算法是最直接的 Java 操作之一，因此即使是完全的初学者在实现它时也不会有太多困难。这是对数组进行排序的分步指南

1.声明一个用于排序的数组

首先，让我们创建一个值字符串，稍后我们将使用 Java 显示这些值。要使用插入排序，您需要创建一个数组。为此，使用int[]

int[] arrayA = {10, 14, 20, 30};

2.使用sort_arr实现算法

sort_arr 方法是实现插入排序最常用的方法之一。在实践中，它看起来像这样：

for(int i=0; i< sort_arr.length; ++i){
        int j = i;

3.创建循环和迭代器

通过在插入排序算法中使用循环，开发人员不必为每个元素重复逻辑。虽然创建循环看起来很复杂，但其实很简单 - 下面是一个示例：

for(int i=0; i< sort_arr.length; ++i){

现在您有了一个正常运行的循环，是时候创建一个迭代器，它将按照所需的顺序对所有元素进行排序。从现在开始，我们将迭代器称为“ j”。

        int j = i;

4. 创建一个“while 循环”

当谈到插入排序时，“while”循环对于新的排序数组是必不可少的。要将其设置为升序插入排序，开发人员需要满足两个条件：

• 分配给 j 的值必须大于 0
• 分配给的值j-1需要大于j索引

一旦 while 循环中的两个条件都为真，数组的键值将等于索引j。

5.数组排序

设置 while 循环后，将交换j和值，直到 while 循环中的一个或两个条件失败。j-1类似地，将对 for 循环中的每个值重复排序，直到 for 循环条件也失败为止。以下是插入排序过程在实践中的工作原理：

int key = sort_arr[j];
          sort_arr[j] = sort_arr[j-1];
          sort_arr[j-1] = key;
          j = j-1;

排序 ArrayList

尽管了解插入排序背后的数学原理很重要，但在实际软件开发中，您对 ArrayList 的排序要多于原始数组中的序列。下面是对 ArrayList 进行排序的分步指南：

1. Element为属于集合的项目 创建一个新类。

   
   public class Element {
       private int id;
   
       public Element(int id) {
           this.id = id;
       }
   

2. 在一个集合中，有一个compareTo()方法——我们将使用它来比较两个元素的 ID。

   
       public int compareTo(Element element) {
           int res = 0;
           if (this.id < element.getId()) {
               res = -1;
           }
           if (this.id > element.getId()) {
               res = 1;
           }
           return res;
       }
   }
   

3. 应用该算法并创建一些循环来对对象进行排序ArrayList而不是比较它们。

   
   public static void insertionSortArrayList(List<element> list) {
       for (int j = 1; j < list.size(); j++) {
           Element current = list.get(j);
           int i = j-1;
           while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) {
               list.set(i+1, list.get(i));
               i--;
           }
           list.set(i+1, current);
       }
   }
   

4. 您还可以向 中添加更多元素ArrayList，如下所示：

   
   List<element> list = new ArrayList<>();
   
   // Create elements w/ IDs 0-24
   for (int i = 0; i < 25; i++) {
       list.add(new Element(i));
   }
   
   // To use insertion sort, shuffle the values
   Collections.shuffle(list);
   

5. 现在是排序的时候了：

   
   // This helps print values before sorting
   list.forEach(e -> System.out.print(e.getId() + ", "));
   
   // Sort the list
   insertionSortArrayList(list);
   
   System.out.println();
   
   // Display a sorted array 
   list.forEach(e -> System.out.print(e.getId() + ", "));
   

6. 现在让我们比较输入和输出以确保我们没有出错。这是我们用作示例的字符串的比较。

   
   4, 2, 6, 7, 0, 5, 9, 1, 8, 3,
   0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
   

插入排序练习题

现在您已经掌握了这种排序算法，是时候考验您的理论和实践技能了。 理论测验 #1 给定一个数组 [1, 4, 6, 8] 并向其中添加一个新元素 n = 7。你需要进行多少次比较才能得到一个排序的数字序列？指示数组中索引 n 的最终值。 理论测验 #2 在求职面试中，团队负责人要求您证明排序插入是一种低效的方法。给定一个数字字符串 [0, 3, 6, 8, 9]，您的输入序列的顺序应该是什么才能最大化排序所需的运行时间？ 练习题 使用 Java 的插入排序对 [0, 1, 4, 5, 2, 3, 7, 9, 8] 数组进行升序排序。

结论

掌握插入排序的最大挑战是理解这个过程是如何工作的。一旦掌握了它，将模板转换为代码就是小菜一碟。只要你不断地练习和复习相关的练习题，你就会迅速提高你的插入排序速度。