java插入排序_Java程序要插入排序

朱雀 2023-02-25 03:55 102阅读 0赞

java插入排序

Java程序插入示例的排序。 显示了示例仿真以及时间复杂度。

##  ##

**插入排序**是一种简单的排序算法，可以一次构建一个最终的排序数组（或列表）。 它比[冒泡排序][Link 1]有效得多，并且在大型列表上的效率比[快速排序][Link 2] ，堆排序或合并排序等效率更高。

我们可以使用迭代和递归方法来实现插入排序。 我们将在本文中使用迭代方法。 与递归相比，它很容易理解。

插入排序会重复扫描项目列表，每次以无序顺序将项目插入其正确位置。

**[Java程序进行冒泡排序][Java]**

## 2.插入排序算法： ##

根据数组准备算法，数组索引从0开始。

从索引i –> 1迭代到长度-1  
  
分配键= A \[i\]; j = i – 1; 循环j> = 0和A \[j\]>键 A \[j + 1\] = A \[j\]; j = j – 1; 结束循环 A \[j + 1\] =键； 结束迭代。

该算法基于纸牌组工作。 挑选一张卡放在手中，然后再挑选另一张卡。 然后将第二个数字与第一个数字进行比较。 如果大于第一张，则将第二张卡放在右侧。 如果少于，则在左侧放置第二张卡。 请通过下面的示例仿真来更好地理解。

## 3.示例仿真： ##

![aHR0cHM6Ly93d3cuamF2YWNvZGVnZWVrcy5jb20vd3AtY29udGVudC91cGxvYWRzLzIwMjAvMDYvSW5zZXJ0aW9uLXNvcnQtZXhhbXBsZS0zMDBweC0xLmdpZg][]

插入排序的图形示例。

## 4. Java程序对插入排序 ##

package com.adeepdrive.data.structures.sorting;  public class InsertionSortProgram { 
      public static void main(String[] args) { 
       // input array 
       int [] inputArray = { 6 , 5 , 3 , 1 , 8 , 7 , 2 , 4 }; 
       int length = inputArray.length; 
       int j = 0 ; 
       System.out.print( "Before Sorting: " ); 
       printArray(inputArray); 
       System.out.print( "\nValues for each Iteration" ); 
       for ( int i = 1 ; i < length; i++) { 
        j = i - 1 ; 
        int key = inputArray[i]; 
        while (j >= 0 && inputArray[j] > key) { 
         inputArray[j + 1 ] = inputArray[j]; 
         j = j - 1 ; 
        } 
        inputArray[j + 1 ] = key; 
        System.out.println(); 
        printArray(inputArray); 
       } 
       System.out.print( "\nAfter sorting: " ); 
       printArray(inputArray); 
      } 
      private static void printArray( int [] inputArray) { 
       for ( int value : inputArray) { 
        System.out.print(value + " " ); 
       } 
      }  }

**输出：**

排序前：6 5 3 1 8 7 2 4  
  
每个迭代的值 5 6 3 1 8 7 2 4 3 5 6 1 8 7 2 4 1 3 5 6 8 7 2 4 1 3 5 6 8 7 2 4 1 3 5 6 7 8 2 4 1 2 3 5 6 7 8 4 1 2 3 4 5 6 7 8 排序后：1 2 3 4 5 6 7 8

我们将当前的迭代索引值存储在键中，因为如果我们在条件上交换值。 在交换活动中，我们可能会损失该指数的原始价值。 为了避免数据丢失，我们将其存储在临时变量中。

在代码中，我们从索引1开始，忽略索引0，因为索引o已经排序。

i = 1，键= 5  
  
将键= 5与左侧值进行比较。 即5.条件6> 5 –> true。 交换他们。 5 6 3 1 8 7 2 4

现在我= 2，钥匙= 3  
  
将键与其左侧值进行比较并交换它们 6> 3 –> true –>交换–> 5 3 6 1 8 7 2 4 5> 3 –> true –>交换–> 3 5 6 1 8 7 2 4

现在我= 3，密钥= 1  
  
比较key（1）及其左侧值并对它们进行排序。 6> 1 –> true –>交换–> 3 5 1 6 8 7 2 4 5> 1 –> true –>交换–> 3 1 5 6 8 7 2 4 3> 1 –> true –>交换–> 1 3 5 6 8 7 2 4

现在我= 4，关键= 8  
  
比较key（8）及其左侧值并对它们进行排序。 6> 8 –> false –>无交换。 这意味着所有左侧值均已排序。

现在我= 5，关键= 7  
  
比较key（7）及其左侧值并对它们进行排序。 8> 7 –> true –>交换–> 1 3 5 6 7 8 2 4 6> 7 –> false –>无交换。 所有左侧值均已排序。

现在我= 6，关键2  
  
比较key（2）及其左侧的值并对它们进行排序。 8> 2 –> true –>交换–> 1 3 5 6 7 2 8 4 7> 2 –> true –>交换–> 1 3 5 6 2 7 8 4 6> 2 –> true –>交换–> 1 3 5 2 6 7 8 4 5> 2 –> true –>交换–> 1 3 2 5 6 7 8 4 3> 2 –> true –>交换–> 1 2 3 5 6 7 8 4 1> 2 –> false –>无交换。 这意味着所有左侧值均已排序。

现在我= 7，key4  
  
比较key（4）和它的左侧值并对它们排序。 8> 4 –> true –>交换–> 1 2 3 5 6 7 4 8 7> 4 –> true –>交换–> 1 2 3 5 6 4 7 8 6> 4 –> true –>交换–> 1 2 3 5 4 6 7 8 5> 4 –> true –>交换–> 1 2 3 4 5 6 7 8 3> 4 –>否–>无交换。 这意味着所有左侧值均已排序。

到达数组末尾并停止处理。

##  ##

**最坏情况下的时间复杂度：O（n \* n）**  
  
当所有值未排序时。 例如9 8 7 6 5 4 3 2 1

**最佳情况下时间复杂度：O（n）**  
  
什么时候  全部已输入已排序例如1 2 3 4 5 6 7 8 9 辅助空间：O（1）

## 6.插入排序优势： ##

插入排序的主要优点是  
  
1）其简单性。 2）处理少量清单时，它也表现出良好的性能。 3）插入排序是一种就地排序算法，因此空间需求最小。

## 7.插入排序的缺点： ##

插入排序的缺点是

1）它的性能不及其他更好的排序算法。  
  
2）对于每个要排序的n个元素都需要n个平方的步骤，因此插入排序不能很好地处理庞大的列表。 3）因此，插入排序仅在对几个项目的列表进行排序时才特别有用。

> 翻译自: [https://www.javacodegeeks.com/2020/06/java-program-to-insertion-sort.html][https_www.javacodegeeks.com_2020_06_java-program-to-insertion-sort.html]

java插入排序

[Link 1]: http://www.adeepdrive.com/2017/10/bubble-sort-in-java.html
[Link 2]: https://en.wikipedia.org/wiki/Quicksort
[Java]: https://www.javaprogramto.com/2017/10/bubble-sort-in-java.html
[aHR0cHM6Ly93d3cuamF2YWNvZGVnZWVrcy5jb20vd3AtY29udGVudC91cGxvYWRzLzIwMjAvMDYvSW5zZXJ0aW9uLXNvcnQtZXhhbXBsZS0zMDBweC0xLmdpZg]: /images/20230209/133a472161a349fdbb79bdcf7b6da74b.png
[https_www.javacodegeeks.com_2020_06_java-program-to-insertion-sort.html]: https://www.javacodegeeks.com/2020/06/java-program-to-insertion-sort.html