Thuật toán sắp xếp chèn vào Java với ví dụ về chương trình

Thuật toán sắp xếp chèn là gì?

Sắp xếp chèn là một thuật toán sắp xếp đơn giản phù hợp với các tập dữ liệu nhỏ. Trong mỗi lần lặp, thuật toán:

• Loại bỏ một phần tử khỏi một mảng.
• So sánh nó với giá trị lớn nhất trong mảng.
• Di chuyển phần tử đến đúng vị trí của nó.

Quy trình thuật toán sắp xếp chèn

Đây là cách quy trình thuật toán sắp xếp chèn hoạt động bằng đồ họa:

Java Ví dụ chương trình để sắp xếp một mảng bằng thuật toán sắp xếp chèn:

package com.guru99;
 
public class InsertionSortExample {
 
	
    public static void main(String a[])
    {    
        int[] myArray  = {860,8,200,9};  
        
        System.out.println("Before Insertion Sort");  
        
        printArray(myArray);
            
        insertionSort(myArray);//sorting array using insertion sort    
           
        System.out.println("After Insertion Sort");  
        
        printArray(myArray);   
    }    
 public static void insertionSort(int arr[]) 
	{  
        int n = arr.length;  
        
        for (int i = 1; i < n; i++)
        {   System.out.println("Sort Pass Number "+(i));
            int key = arr[i];  
            int j = i-1;  
            
            while ( (j > -1) && ( arr [j] > key ) ) 
            {  
            System.out.println("Comparing "+ key  + " and " + arr [j]); 
                arr [j+1] = arr [j];  
                j--;  
            }  
            arr[j+1] = key; 
            System.out.println("Swapping Elements: New Array After Swap");
            printArray(arr);
        }  
    }
 static void printArray(int[] array){
	    
	    for(int i=0; i < array.length; i++)
		{  
			System.out.print(array[i] + " ");  
		} 
	    System.out.println();
	    
	}
}

Đầu ra mã:

Before Insertion Sort
860 8 200 9 
Sort Pass Number 1
Comparing 8 and 860
Swapping Elements: New Array After Swap
8 860 200 9 
Sort Pass Number 2
Comparing 200 and 860
Swapping Elements: New Array After Swap
8 200 860 9 
Sort Pass Number 3
Comparing 9 and 860
Comparing 9 and 200
Swapping Elements: New Array After Swap
8 9 200 860 
After Insertion Sort
8 9 200 860