Exchange sort—Bubble Sort (Bubble Sort)

Exchange sorting mainly compares the key codes of the records to be sorted in pairs. If the key codes of the records to be sorted occur, if they are contrary to the sorting requirements, then exchange them. Let’s first look at the bubbling process of sorting columns: Let 1

i=1; //Set up pairwise comparison starting from the first record

If i≥j, one-trip bubbling ends.

Compare r[i].key and r[i+1].key, if r[i].key ≤ r[i+1].key, do not exchange, turn to ⑤

when r[i].key> ;r[i+1].key, r[0]=r[i]; r[i]=r[i+1]; r[i+1]=r[0]; change r[i] Exchange

i=i+1 with r[i+1]; adjust the pairwise comparison of the next two records and switch to the ②

bubble sorting method: for a table of n records, the first bubble is A record r[n] with the largest key code, the second bubble is performed on the table of n-1 records, and then a record r[n-1] with the largest key code is obtained. Repeat this until n records are pressed by the key code. Ordered table.

【Algorithm 10.6】


j=n; //Start from the table with n records

If j

i=1; //One trip of bubbling, setting starts from the first record Perform pairwise comparison,

If i ≥ j, one bubbling trip ends, j=j-1; the number of records in the bubble table is -1, go to ②

to compare r[i].key and r[i+1 ].key, if r[i].key≤r[i+1].key, no exchange, turn to ⑤

When r[i].key>r[i+1].key, r[i] r[i+1]; Exchange r[i] and r[i+1]

i=i+1; Adjust the next two records to compare them in pairs, go to ④

【Efficiency Analysis】

Space efficiency: Only one auxiliary unit is used.

Time efficiency: A total of n-1 bubbling operations are required. One bubbling operation for a table with j records requires j-1 key code comparisons.

Number of moves:

Best case: the columns to be sorted are already in order, no need to move

Worst case: three moves are required after each comparison,

For more exchange sorting-bubble sorting (Bubble Sort) related articles, please pay attention to the PHP Chinese website!