Java中的简单插入排序
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/28379397/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Simple Insertion Sort in Java
提问by Harsh Kanakhara
I had written a simple insertion sort program but the output is not coming correctly.
我写了一个简单的插入排序程序，但输出不正确。
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]);
}
}
}
采纳答案by Mohammad tanvirul islam
/*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]);
}
}
}
回答by philipxy
At the top of the outer loop the array is sorted below element i. You don't want to move iback down into the array. In the inner loop jmoves the new element that starts at idown into the sorted array by repeatedly switching with the next one down.
在外部循环的顶部，数组被排序在 element 之下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;
}
}
回答by Dushman
While loop is unnecessary here,
虽然这里不需要循环，
if ((a[j] < a[i]))
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
回答by user3507620
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");
}
回答by Charith mohotti
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);
}
}
回答by AKHY
Insertion Sort
插入排序
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;
}
}
Program Output:
程序输出：
Insertion Sort Demo:
插入排序演示：
3 12 15 19 27 34 43 54 55 77
3 12 15 19 27 34 43 54 55 77
回答by Nikhil Chatterjee
This is tested and works
这是经过测试并有效的
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;
}
回答by srikanth S
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]);
}
回答by Lior Elrom
Insertion Sort (ES6)
插入排序 (ES6)
(in case someone needs it)
（以防有人需要）
// 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]回答by GT_hash
Insertion sort is a another sorting algorithm for sorting array elements.This algorithm is better than selection sort algorithm or bubble sort algorithm.Worst case time complexity and average case time complexity is (n^2).Best case time complexity is (n) .Worst case space complexity is (n) and best case space complexity is constant(1).Let's see how to implement insertion sort algorithm.
插入排序是另一种对数组元素进行排序的排序算法。该算法优于选择排序算法或冒泡排序算法。最坏情况时间复杂度和平均情况时间复杂度为 (n^2)。最佳情况时间复杂度为 (n) 。最坏情况空间复杂度为（n），最好情况空间复杂度为常数（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]+" ");
}
}
}
}
