1, insertion sort

Insert sort is to insert elements into an already ordered sequence so that the entire sequence is still ordered after insertion.

1.1. Implementation of insertion sort

Execute the process

  1. During execution, the insertion sort is divided into two parts: the header is the sorted sequence and the tail is the sorted sequence
  2. Scan each element from scratch: As soon as an element is scanned, insert it into the appropriate position in the header so that the header data remains in order

Code implementation

for (int begain = 1; begain < array.length; Begain ++) {// Save the position of the scan element int cur = begain; While (cur > 0 && CMP (cur, cur-1) < 0) {// Swap two elements swap(cur, cur-1); cur --; }}Copy the code

1.2, Insertion sort – optimization

Idea: Change the swap to the shuffle

  1. Back up the elements to be inserted
  2. The ordered data in the header is larger than the element to be inserted and moves one position toward the tail
  3. Place the element to be inserted into the final appropriate position

Code implementation

for (int begain = 1; begain < array.length; Begain ++) {// record the traversal position int cur = begain; T v = array[cur]; While (cur > 0 && CMP (v,array[cur-1]) < 0) {// Move the element backwards array[cur] = array[cur-1]; cur --; } // Insert the element array[cur] = v; }Copy the code

2. Binary search

  1. If it’s an unordered array, you need to traverse from position 0. Average time complexity: O(n)
  2. For ordered arrays, binary search can be used, worst time complexity: O(logn)

Train of thought

  1. Suppose we search for an element V in [begain,end], mid == (begain + end) / 2
  2. If v < m, go to [begain, mid] binary search
  3. If v > m, go binary search in the range [mid + 1, end]
  4. If v == m, return mid

Search for instance

Search 10:

  1. Mid = (0 + 7) / 2 = 3
  2. And then we figure out that mid on the right is equal to 3 plus 7 over 2 is equal to 5. 12 is bigger than 10. Continue binary search
  3. And finally hit it at 4

Begain == end == 1

Code implementation

Public static int search (int [] array, int v) {/ / if array does not exist, then return the if (array = = null | | array. The length = = 0) return 1; Int begain = 0; Int end = array.length; While (begain < end) {int mid = (begain + end) >> 1; If (v < array[mid]) {end = mid} else if (v > array[mid]) {begain begain = mid + 1; } else {return mid; } } reutrn -1; }Copy the code

3, Insertion sort – binary search optimization

  • In the process of inserting element V, the appropriate insertion position can be searched for bisection first, and then the element V can be inserted
  • The insertion position returned by binary search is required: the position of the first element greater than v

Such as:

If v is 5, return index 2

If v is 1, return index 0

If v is 15, return index 7

If v is 8, return index 5

Train of thought

  • Suppose we search for an element v in [begain, end], mid == (begain + end) / 2
  • If v < m, go binary search in [Begian,mid]
  • If v >= m, go binary search in the range [mid + 1,end]

implementation

// Insert method implementation,seource: current index position traversed. Private void insert(int source, int dest) {T v = array[source]; For (int I = source; i > dest; i-- ) { array[i] = array[i - 1]; } array[dest] = v; Private int search(int index) {int begain = 0; int end = index; while (begain < end) { int mid = (begian + end) >> 1; if (cmp(index, mid) < 0) { end = mid; } else { begain = mid + 1; } } return begain; } for (int I = 1; i < array.length; i++) { insert(i, search(i)); }Copy the code