The conventional concept of

Degree of order

Degree of order is the number of pairs of elements in an array that have an ordered relationship

Full degree of order

The order degree of a completely ordered array is full order degree, that is, the full order degree of an array of n length is Cn², that is, n*(n-1)/2;

The reverse of

Degree of full order – degree of order = degree of inversion

Bubble sort

public class SortMain { public static void main(String[] args) { int[] arr = {4, 5, 6, 3, 2, 1}; Int count = 0; // int count = 0; count = bubbleSort(arr); System.out.println(Arrays.toString(arr)); System.out.println(" Sorting Execution :" + count); } public static int bubbleSort(int[] arr) { int count = 0; for (int i = 0; i < arr.length; I++) {// When no more data is exchanged in a bubble, it is fully ordered and can exit the loop at any time Boolean flag = false; for (int j = 1; j < arr.length - i; J++) {/ / j compare with the if I (arr] [j - 1 > arr [j]) {count++; swap(arr, j); flag = true; } } if (! flag) { break; } } return count; } private static void swap(int[] arr, int j) { int temp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = temp; }}

Bubble Sort features:

  • Sort in place, space O(1)
  • Stable sort. Adjacent and equal elements are not swapped to ensure that the relative order of the two elements after sorting is the same as before sorting
  • O(n) in the best case, O(n ^ 2) in the worst case, which is N *(n-1)/2
  • The number of interchanges is equal to the degree of inversion

Insertion sort

public static int insertSort(int[] arr) { int count = 0; // for (int I = 1; i < arr.length; i++) { int temp = arr[i]; int j = i - 1; for (; j >= 0; j--) { if (temp < arr[j]) { count++; arr[j + 1] = arr[j]; } else { break; } } arr[j + 1] = temp; } return count; }

Insertion Sort features:

  • Sort in place, space O(1)
  • Stable sorting algorithm
  • Time complexity O(n ^ 2)

Selection sort

Three kinds of sorting comparison

  • Selection sort is not stable sort and is weaker than bubble and insertion sort
  • Bubble sort requires three assignment operations for swapping; insert sort requires only one
  • Insertion sort is slightly more efficient than bubble sort