Учебники

60) Алгоритм сортировки вставок

Вставка сортировки – это простой алгоритм сортировки, подходящий для небольших наборов данных. Во время каждой итерации алгоритм

  • Удаляет элемент из массива
  • Сравнивает его с наибольшим значением в массиве
  • Перемещает элемент в правильное местоположение.

Вот как процесс работает графически

JAVA-программа для сортировки массива с использованием алгоритма сортировки вставками.

  1. package com.guru99;
  2. public class InsertionSortExample {
  3. public static void main(String a[])
  4. {
  5. int[] myArray = {860,8,200,9};
  6. System.out.println("Before Insertion Sort");
  7. printArray(myArray);
  8. insertionSort(myArray);//sorting array using insertion sort
  9. System.out.println("After Insertion Sort");
  10. printArray(myArray);
  11. }
  12. public static void insertionSort(int arr[])
  13. {
  14. int n = arr.length;
  15. for (int i = 1; i < n; i++)
  16. { System.out.println("Sort Pass Number "+(i));
  17. int key = arr[i];
  18. int j = i-1;
  19. while ( (j > -1) && ( arr [j] > key ) )
  20. {
  21. System.out.println("Comparing "+ key + " and " + arr [j]);
  22. arr [j+1] = arr [j];
  23. j--;
  24. }
  25. arr[j+1] = key;
  26. System.out.println("Swapping Elements: New Array After Swap");
  27. printArray(arr);
  28. }
  29. }
  30. static void printArray(int[] array){
  31. for(int i=0; i < array.length; i++)
  32. {
  33. System.out.print(array[i] + " ");
  34. }
  35. System.out.println();
  36. }
  37. }

Вывод кода:

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