Summary of the sorting

1, sorting,

Sorting is the process of rearranging a group of objects in a specified order, often for retrieval purposes.

2. Stability

The sequence of n records is {R1, R2… Rn}, and its corresponding key-value sequence is {k1, k2… Kn}, assuming ki= kJ, if Ri is before Rj in the sequence before ordering, that is, I <j, Ri is still before Rj after ordering, the sorting method used is said to be stable; Otherwise, the sorting method used is said to be unstable.

(The sorting method is stable if there are multiple records with the same key value in the sequence to be sorted, but the relative order of the records remains unchanged.)

Note: Stability is a property of the sorting method itself and has nothing to do with the data. In other words, a sorting method that is stable is stable for all data sequences, and conversely, a sorting method that is unstable on a set of data is unstable.

3, classification,

Internal Sorting: a process in which records to be sorted are stored in computer memory;

External Sorting: a Sorting process in which the number of records to be sorted is so large that the memory cannot store all the records and requires External storage to access them.

Direct insertion sort

1, concept,

Straight Insertion Sorting is a simple Sorting method. The basic idea is to insert each record into a sorted list one by one in order to create a new list. Direct insertion sort is similar to the process of sorting books in a library.

2, the algorithm

Insert sort algorithm is described as follows: ★★★ 201910 考试真题

// insert sort into R
void StraightlnsertSort(List R,int n)
{
    int i,j;
    for (i=2; i<=n; i++)//n is the length of the table and is inserted from the second record
    { 
        R[0]=R[i]; // The ith record is copied as sentry
        j=i- 1;
        while (R[0].key<R[j].key)  // Compare with the sentry until the key value is not greater than the sentry key value
        { 
            R[j+1]=R[j]; // Assign the JTH record to the j+1 record
            j--; 
        }
        R[j+1]=R[0]; // Insert the ith record into the sequence}}Copy the code

Record R[0] has two functions. First, it saves the value of R[I] before entering the search cycle, so that the contents of R[I] will not be lost due to the later movement of the record. In the while loop, R[0] automatically controls the end of the while loop once the array subscript variable J is out of bounds (i.e. J <1), thus avoiding the need to detect whether J is out of bounds every time in the while loop.

The application of this technique reduces the time to test the loop condition by about half.

3. Insert the sorting process directly

4. Time complexity and stability

The algorithm of direct insertion sort is simple, easy to understand, and easy to implement. The time complexity is O(n2). When the number of records to be sorted is large, direct insertion sort is generally not used. In terms of space, it requires only one auxiliary space for records, that is, space complexity is O(1).

The direct insert sort method is stable.