Java 中的简单插入排序

Question

我写了一个简单的插入排序程序，但输出不正确。

class InsertionSort{
    public static void main(String h[]){
    int[] a = {5,4,3,2,1};
    int i,j,temp;
        for(i=1;i<a.length;i++){
            j = i-1; 
            while(i>0 && a[j] > a[i]){
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
        for(int x=0; x<a.length;x++){
            System.out.println(a[x]);   
        }
    }
}

Answer 1

在外循环的顶部，数组排序在元素 i 下面。您不想将 i 移回数组中。在内部循环中，j 将开始于 i 的新元素向下移动到已排序的数组中，方法是反复向下切换下一个元素。

for (i = 1; i < a.length; i++){
    for (j = i; j > 0 && a[j-1] > a[j]; j--){
        temp = a[j];
        a[j] = a[j-1];
        a[j-1] = temp;
    }
}

Answer 2

/*this program sort in ascending order by insertion sort */  
class InsertionSort{
public static void main(String h[]){
int[] a = {100,12,31, 5, 4, 3, 2, 1 };
int i, j, temp;
    for (i = 1; i < a.length; i++)
    {
        j = i - 1;
        while (j >= 0 && a[j] > a[i] )
        {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i=j;
            j--;

        }
    }
for(int x=0; x<a.length;x++){
    System.out.println(a[x]);   
  }
}
}
/*this program sort in descending order by insertion sort */  
class InsertionSort{
public static void main(String h[]){
int[] a = {100,12,31, 5, 4, 3, 2, 1 };
int i, j, temp;
    for (i = 1; i < a.length; i++)
    {
        j = i - 1;
        while (j >= 0 && a[j] < a[i] )
        {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i=j;
            j--;

        }
    }
for(int x=0; x<a.length;x++){
    System.out.println(a[x]);   
  }
}
}

Answer 3

虽然这里不需要循环，

                if ((a[j] < a[i]))
                {
                    temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }

Answer 4

public static int[] doInsertionSort(int[] input) {
    int reverse;
    for (int i = 1; i < input.length; i++) {
        for (int j = i; j > 0; j--) {

            System.out.println("compare " + input[j - 1] + " to " + input[j]);

            if (input[j] < input[j - 1]) {
                reverse = input[j];
                System.out.println("Reverse: "+ reverse);

                input[j] = input[j - 1];
                input[j - 1] = reverse;

                new printNumbers(input);
            }
        }
    }
    return input;
}

 printNumbers(int[] input) {

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

        System.out.print(input[i] + ", ");
    }
    System.out.println("\n");
}

Answer 5

public static void insertionsort(){
            Scanner sc = new Scanner(System.in);

                    int[] input = { 4, 2, 9, 6, 23, 12, 34, 0, 1 };
                    arr(input);
        }
        private static void printNumbers(int[] input) {
            for (int i = 0; i < input.length; i++) {
            System.out.print(input[i] + ", ");
        }
        System.out.println("\n");
        }

        public static void arr (int array[]){    
                int n = array.length;
        for (int j = 1; j < n; j++) {
            int key = array[j];
            int i = j-1;
            while ( (i > -1) && ( array [i] > key ) ) {
                array [i+1] = array [i];
                i--;
            }
            array[i+1] = key;
            printNumbers(array);

    }
}

Answer 6

插入排序

public class InsertionSort {

    public static void main(String args[]){
        int[] arry1 = {55,12,43,27,54,34,77,3,15,19};
        int[] arry2 = insertionSort(arry1);
        System.out.println("Insertion Sort Demo:");
        for(int i:arry2){
            System.out.print(i);
            System.out.print(" ");
        }
    }

    public static int[] insertionSort(int[] arr){

        int temp;
        for (int i = 1; i < arr.length; i++) {
            for(int j = i ; j > 0 ; j--){
                if(arr[j] < arr[j-1]){
                    temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
            }
        }
        return arr;
    }

}

程序输出：

插入排序演示：

3 12 15 19 27 34 43 54 55 77

Answer 7

这已经过测试并且有效

public static int[] insertionSort(int[] array) {
    int temp, j;

    for(int i = 1; i < array.length; i++) {
        temp = array[i];

        for (j = i - 1; j >= 0; j--) {
            if (array[j] > temp) {
                array[j+1] = array[j];
            } else {
                break;
            }
        }
        array[j + 1] = temp;
    }

    return array;
}

Answer 8

Scanner s = new Scanner(System.in);
        System.out.println("Enter the nos");
        num = s.nextInt();

        System.out.println("Enter the "+num+" integers");
        int array []= new int[num];
        for(int count = 0;count<num; count++ )
        {
            array[count] = s.nextInt(); 
        }

        for(int i = 0;i<array.length;i++)
        {
            key = array[i];
            j = i-1;
            while(j>=0 && array[j]>key)
            {
                array [j+1] = array[j];
                j=j-1;
            }

            array[j+1] = key;
        }

        System.out.println("Sorted array");

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

        {
            System.out.println(array[i]);
        }

Answer 9

插入排序 (ES6)

（以防有人需要）

// Insertion Sort In-Place

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j > 0; j--) {
      if (arr[j] < arr[j - 1]) {
        [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
      } else {
        break;
      }
    }
  }
  return arr;
}

const arr = [5,1,9,2,0,6,4,3,8,7];

console.log(insertionSort(arr)); // [0,1,2,3,4,5,6,7,8,9]

Answer 10

插入排序是另一种排序数组的排序算法elements.This算法优于选择排序算法或冒泡排序algorithm.Worst案例时间复杂度，平均案例时间复杂度为(n^2)。最佳情况时间复杂度为 (n)。最坏情况 space 复杂度为 (n)，最佳情况 space 复杂度为常量 (1)。让我们看看如何实现插入排序算法。

import java.util.Scanner;

class insertion_sort{
  public static void main(String a[]){

    Scanner sc=new Scanner(System.in);
    System.out.print("Size of array :");
    int n=sc.nextInt();

    int[] num=new int[n];
    int i,j,tmp,tmp2;


    for(i=0;i<n;i++){
        num[i]=sc.nextInt();
    }

    for(i=1;i<n;i++){
        tmp=num[i];
        for(j=0;j<i;j++){
            if(num[i-j-1]>tmp){
                tmp2=num[i-j-1];
                num[i-j-1]=tmp;
                num[i-j]=tmp2;
            }
            else{
                break;
            }
        }
    }

    for(i=0;i<n;i++){
        System.out.print(num[i]+"  ");
    }
}

}

Answer 11

public int[] insertionSort(int[] list)
{
for (int i = 1; i < list.length; i++)
{
int key = list[i];
int j = i - 1;
while (j >= 0 && key < list[j])
{
int temp = list[j];
list[j] = list[j + 1];
list[j + 1] = temp;
j--;
}
}

return list;
}

Answer 12

非常简单的方法

public static void main(String[] args) {
    int[] array = {100, 12, 31, 5, 4, 3, 2, 1};

    for (int i = 1; i < array.length; i++) {
        for (int j = i; j > 0; j--) {
            if (array[j - 1] > array[j]) {
                int temp = array[j];
                array[j] = array[j - 1];
                array[j - 1] = temp;
            }
        }
    }
    System.out.println(Arrays.toString(array));
}

Answer 13

我们可以遵循使用游标的简单方法。请在下面找到。

public static void insertionSort(int[] elements) {
    for(int i=1;i<elements.length;i++) {            
        int cursor = i;
        for(int j=i;j>=0;j--) {
            if(elements[j]>elements[cursor]) {
                int temp = elements[j];
                elements[j] = elements[cursor];
                elements[cursor] = temp;                    
                cursor = j;                 
            }

        }
    }
}

请让我知道您的反馈，以便从我身边改进是最有帮助的

Answer 14

import java.security.SecureRandom;

import java.util.Arrays;


public class Sorting {
    
    
    public static void insertionSort(int[] data){
        
        for(int i=1;i<data.length;i++){
            
            int insert = data[i];
            int index = i;
            
            while(0<index && insert < data[index-1]){
                data[index]=data[index-1];
                index--;
            }
            data[index]=insert;
        }       
    }

    public static void main(String[] args) {
        SecureRandom generator = new SecureRandom();
        int[] data = generator.ints(30, 10, 20).toArray();
        

        insertionSort(data);
        System.out.println("Sorted array: "+Arrays.toString(data));

    }

}

Java 中的简单插入排序

Simple Insertion Sort in Java

java

sorting

insertion-sort

插入排序 (ES6)