Insertion sort
Insertion sort is a simple, intuitive and stable sorting algorithm. Le byte
Insertion sort works much like people sort a poker hand. We start with our left hand empty and the cards on the table face down. Then, we take one card at a time from the table and insert it into the correct position in the left hand. To find the right position for a card, we compare it from right to left with every card we already have in hand, as shown below:
Requirements:
{4,3,2,10,12,1,5,6}
{1,2,3,4,5,6,10,12}
Sorting principle:
1. Divide all elements into two groups, sorted and unsorted;
2. Find the first element in the unsorted group and insert it into the sorted group.
3. Run backwards through the sorted elements and compare them with the elements to be inserted until one element is less than or equal to the element to be inserted
Insert elements in this position, other elements move back one bit;
2. Swap the values at the first index and the minimum index
Insert sort API design:
The name of the class
Insertion
A constructor
Insertion() : Creates Selection objects
Members of the method
1. Public static void sort(Comparable[] a)
2. Private static Boolean greater(Comparable V,Comparable W): Determine whether V is greater than W
Private static void exch(Comparable[] a,int I,int j)
Insert sort code implementation:
// Insert sort
public class Insertion { /*
Sort the elements in array A
* /
public static void sort(Comparable[] a) { for (int i = 1; i < a.length; i++) { for (int j = i; j > 0; J –) {// select * from j-1 where j-1 = 1; // select * from j-1 where j-1 = 1;
if (greater(a[j – 1], a[j])) { exch(a, j – 1, j);
} else { break;
}
}
}
}
/ *
Compares whether the v element is greater than the w element
* /
private static boolean greater(Comparable v, Comparable w) { return v.compareTo(w) > 0;
}
/ *
The array elements I and j swap places
* /
private static void exch(Comparable[] a, int i, int j) { Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
// Test the code
public class InsertionTest { public static void main(String[] args) { Integer[] a = {4, 3, 2, 10, 12, 1, 5, 6};
Insertion.sort(a);
System.out.println(Arrays.toString(a)); / /,2,3,4,5,6,10,12 {1}
}
}
Time complexity analysis of insertion sort
Insert sort uses a double-layer for loop, where the inner loop is the code that actually completes the sort. Therefore, we analyze the time complexity of insert sort, mainly analyzing the number of times the inner loop is executed.
The worst case is {12,10,6,5,4,3,2,1}.
The number of comparisons is :(n-1)+(n-2)+(n-3)+… +2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2;
The number of switches is :(n-1)+(n-2)+(n-3)+… +2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2;
(n2/2-n /2)+(n2/2-n /2)=N^ 2-n;
According to the big O derivation, the time complexity of the final insertion sort is O(N^2) if the highest order term in the function is reserved. This article turns to music bytes.