This is the 15th article in a series on Data Structures and Algorithms: Simple Methods.

  1. | sequence table data structure
  2. | linked list data structure
  3. | stack data structure
  4. | queue data structure
  5. | double linked list data structure and circular linked list
  6. | binary tree data structure of the concepts and principles
  7. | binary tree data structure to create and traverse the implementation
  8. Binary tree data structure | cues
  9. | binary heap data structure
  10. | priority queue data structure
  11. | sequential search and binary search algorithm
  12. Data structure (animation) | binary search trees
  13. Sorting algorithm (animation) | violence sorting and bubble sort
  14. Sorting algorithm (animation) | simple selection sort

We’ve introduced three kinds of sorting, violent sorting, bubble sorting, and simple selection sorting, all based on exchange.

Another way to look at sorting is to view an array to be sorted as having two parts: the ordered region and the out-of-order region.

Before sorting begins, the entire array is out of order and the ordered array is empty:

After the sorting begins, the ordered region gradually expands and the out-of-order region gradually shrinks:

After sorting, the entire array is ordered and the out-of-order region is empty:

Core idea: the array is regarded as the unordered region and the ordered region two regions, from the unordered region to select an element, according to the size of the ordered region inserted into the appropriate location. When the unordered region is empty, the ordered region completes the ordering.

The dynamic process is as follows:

The code implementation is as follows:

/* * Insert sort * array: array * length: array length */
void straight_insertion_sort(int *array.int length)
{
    int i, j;
    // The outer loop determines the value to be inserted
    for (i = 1; i < length; i++) {
        if (array[i] < array[i - 1]) {
            int tmp = array[i]; // The value to be inserted
            // The inner loop makes room in the ordered region for values to be inserted
            for (j = i - 1; j >= 0 && array[j] > tmp; j--) {
                array[j + 1] = array[j];
            }
            array[j + 1] = tmp; / / insert}}}Copy the code

Note the key code for inserting elements into an ordered region array[j + 1] = TMP; The j + 1.

So that’s the basic principle of direct insert sort.

Complete code please visit lot | Gitee acquisition.

Please correct me if there are any mistakes.

If you think it’s good, you can like it and follow it. More data structures and algorithms will follow.