Insert the sort directly
1 sorting idea:
The record Ri to be sorted is inserted into the already sorted records R1, R2,..., R(N-1).
For a random sequence, starting from the second element, inserting the element into the corresponding position in the element before it in turn. The elements before it have been sorted.
First order: Insert the second element into the ordered list in the preceding order (at this time there is only one element in the previous one, of course it is ordered). After that, the first two elements of this sequence are ordered.
Second sort: Insert the third element into the ordered list of the previous length 2 so that the first two elements are ordered.
And so on until the Nth element is inserted into the ordered list of previous length (N-1).
2 Algorithm implementation:
// Directly insert sort void straight_insert_sort(int num[], int len){ int i,j,key; for(j=1;j<len;j++){ key=num[j]; i=j-1; while(i>=0&&num[i]>key){ num[i+1]=num[i]; i--; } num[i+1]=key; }}3 Performance analysis:
3.1 Space complexity: As mentioned above, an auxiliary unit key is used, and the space complexity is O(1)
3.2 Time complexity:
3.2.1 Best case: The records to be sorted are already ordered, then sort them in one trip, the keywords are compared once, and the records are moved twice. The whole process
The number of comparisons is
The number of records moves is
Time complexity O(n)
3.2.2 Worst case: The records to be sorted are already in reverse order, then the keyword comparison times are i (from i-1 to 0), and the record moves (i+2) times. The whole process
The number of comparisons is
The number of records moves is
Time complexity O(n^2)
3.2.3 Average time complexity: O(n^2)
3.3 Stability: Stable
Fold half insert sort
1 sorting idea:
Based on direct sorting, the records to be sorted Ri are inserted into the already sorted records R1, R2,..., R(N-1). Since the records R1, R2,..., R(N-1) have been sorted, "half-finding" can be used when looking for the insertion position.
2 Algorithm implementation:
// Fold half insert sort void binary_insert_sort(int num[], int len){ int i,j,key,low,high,mid; for(i=1;i<len;i++){ key=num[i]; low=0; high=i-1; mid=(low+high)/2; // Find the insertion point, the final insertion point is low while(low<=high){ if(key<num[mid]) high=mid-1; else low=mid+1; mid=(low+high)/2; } // Move record for(j=i;j>low;j--){ num[j]=num[j-1]; } // Insert record num[low]=key; }}3 Performance analysis:
3.1 Space complexity: As mentioned above, an auxiliary unit key is used, and the space complexity is O(1)
3.2 Time complexity: Although half-finish search reduces the number of records and comparisons, it does not reduce the number of movements, so the time complexity is the same as the direct search algorithm.
3.2.1 Best case: Time complexity O(n)
3.2.2 Worst case: Time complexity O(n^2)
3.2.3 Average time complexity: O(n^2)
3.3 Stability: Stable