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.

Bubble sort

1, concept,

Bubble Sort is a simple sorting algorithm in the field of computer science.

It repeatedly walks through the column of elements to be sorted, comparing two adjacent elements in turn, and swapping them if the order is wrong (from largest to smallest, Z to A). The task of visiting an element is repeated until no neighboring elements need to be swapped, that is, the element column has been sorted.

The algorithm gets its name from the fact that smaller elements slowly “float” to the top of the sequence (ascending or descending) through exchange, just as bubbles of carbon dioxide in a carbonated drink eventually rise to the top.

2, the algorithm

When the algorithm is implemented, define an integer variable called endsort, which is set to 0 before each sort, or 1 if records are swapped in a run of bubbling. At the end of a loop, we check endsort again and terminate the algorithm if endsort is 0.

201910 real exam

void BubbleSort (List R,int n) {
    int i,j,temp,endsort;
    for(i=1; i<=n- 1; i++) { endsort=0;
        for (j=1; j<=n-i; j++) {if (R[j].key>R[j+1].key) // Switch records in reverse order
            {
                temp=R[j];
                R[j]=R[j+1];
                R[j+1]=temp;
                endsort=1; }}if (endsort==0) break; }}Copy the code

3. Time complexity and stability

The average time complexity of the algorithm is O(n^2). If it is already ordered, the number of comparisons is n-1, and the time complexity is O(n).

Bubble sort is a stable sorting method.