I. Basic ideas

In the set of numbers to be sorted， Assuming that the previous(n-1)[n>=2] The numbers are already in order.， Now to put the firstn The number is inserted into the preceding ordered number， makes thisn The numbers are also in order。 And so on and so forth.， Until they're all in order.。 Example: array a[] = {57, 68, 59, 52}. The comparison is done by comparing each number with the number before it. The first 57, with no count in front of it, does not need to be compared. Second number68， In contrast to the previous57 comparisons， owing to68 > 57， So no need to change positions。 The third number59， First with the previous68 comparisons， owing to59 < 68， So it needs to be compared to the number further ahead57 comparisons， owing to59 > 57。 So whatever57 Is there a number in front of the， There's no need to compare.。 classifier for objects with a handle59 insert into57 harmony68 It's fine between。 The fourth number52， There are three numbers in front of it：57，59，68。 initial contact with68 compare，52 < 68， Needs to be done again with59 compare，52 < 59， Needs to be done again with57 compare，52 < 57。 At this point there's no more counting ahead。 So put52 insert into57 ahead。 The final results are 52, 57, 59, 68.

1.png

II. Code implementation

#include<stdio.h>


void insertSort(int a[], int n)
{
    int i, j, temp;
    for (i = 1; i < n; i++)
    {
        temp = a[i];
        j = i;

        //  will be greater thantemp is shifted back one unit overall to the value of
        while(j > 0 && a[j-1] > temp)
        {
            a[j] = a[j-1];
            j--;
        }
        a[j]=temp;
    }
}


int main()
{
    int arr[] = {57, 68, 59, 52};
    int len = sizeof(arr) / sizeof(int);
    insertSort(arr, len);
    int i = 0;
    for(; i < len; i++)
    {
        printf("%d ", arr[i]);
    }

    return 0;
}

Results of the run.

52, 57, 59, 68

Program analysis. In the for loop, the （1） i = 1, temp = a[1] = 68, j = 1, a[0] = 57, a[0] > temp untenable， No adjustment required

（2）i = 2，temp = a[2] = 59， ① j = 2，a[1] = 68 > temp， execute a loopa[2] = a[1] = 68，j self-decreasing。 ② j = 1, a[0] = 57 > temp untenable， End of the cycle。 (iii) Final execution a[1] = temp = 59, at which point arr = {57, 59, 68, 52}

（3）i = 3，temp = a[3] = 52 ① j = 3, a[2] = 68 > temp， execute a loopa[3] = a[2] = 68，j self-decreasing ② j = 2，a[1] = 59 > temp， execute a loopa[2] = a[1] = 59，j self-decreasing ③ j = 1，a[0] = 57 > temo， execute a loopa[1] = a[0] = 57，j Self-decreasing becomes0， End of the cycle ④ Final execution a[0] = temp = 52, at which point a = {52, 57, 59, 68}

III. Time complexity analysis

(i) Best case scenario The best case is a sequential arrangement of data, such as {1, 2, 3, 4, 5}. The number of comparisons is 4 and the number of moves is 0. If there are n sequentially ordered elements, the number of comparisons is n - 1 and the number of moves is 0. So the complexity is O(n).

(ii) Worst case scenario The worst case is that the data is arranged in reverse order, e.g. {5, 4, 3, 2, 1}. The number of comparisons is 1 + 2 + 3 + 4 = 10 and the number of moves 2 + 3 + 4 + 5 = 14. If there are n inverted orderings, the number of comparisons is 1 + 2 + ...... + (n - 1) = n (n - 1) / 2 and the number of moves is 2 + 3 + ... + n = (n - 1) (n + 2) / 2. The total number of times is n (n - 1) / 2 + (n - 1)(n + 2) / 2 = (n - 1) (n + 1). So the complexity is O(n2).

(iii) Average situation The average case, the number of comparisons, shifts is the average of the best case and the worst case, the [(n - 1) + (n - 1)(n + 1)] / 2 = (n - 1) (n + 2) / 2. The complexity is O(n2).

IV. Stability

Taking {5, 2, 2, 1} as an example, the first 2 is inserted in front of 5. The second 2 will only be inserted between the first 2 and 5 according to the algorithm of direct insertion sort, not before the first 2. So the direct insertion sort is a stable sorting algorithm.

Recommended>>
1、reactnativeswipercomponentsweepacrossyourrotationimage
2、Basic Kafka concepts and installation guide standalone cluster sync
3、Negative number calculationC
4、600 English words that programmers must master
5、HTMLampampCSS07Floating and positioning layout

已发送

发送中