Exchange sort method

Bubble sort ( Adjacency comparison method )

Bubbling

Exchange through adjacent records , The process of gradually changing the sequence to be sorted into an ordered sequence .

Algorithmic thought

The first 1 Trip to ： From 1 A record begins , Scan the sequence of records to be sorted , If two adjacent records are in reverse order , Then switch places ( Eliminate a reverse order ), Last n A record is the record with the largest keyword .
The first 2 Trip to ： Same as above , To the front n-1 Bubble sort of elements , Last n-1 A record is the record with the largest secondary key .
And so on , Until the first n-1 After the trip is completed ; Or if no reverse order is found during a certain bubble sorting process, it can be ended .

Algorithm analysis

The best situation ： Orderly . Comparison times n-1 Time , Number of moves 0 Time , The time complexity is O(n).
The worst ： The reverse . Comparison times n(n-1)/2 Time , Number of moves 3n(n-1)/2 Time , The time complexity is O(n2).
notes ： Swap a move 3 Time .
Spatial complexity ：O(1).
stability ： Stable .

Quick sort

Key points of algorithm improvement

Bubbling ： Exchanging adjacent elements can only eliminate one reverse order .
Quick typesetting ： Exchange nonadjacent elements , Multiple reverse orders can be eliminated .

The basic idea

A quick line ： Divide the sequence to be arranged into two sub tables , The keywords of the left table are smaller than those of the right table .
repeat , Until all sub tables are single records .
Pivot element ： Boundary records of the left and right sub tables .
Benchmark records ： The pivot element should be placed in the middle of the left and right child tables （ Reference position ）, So the datum record is the same as the pivot element .

A quick line














Selection of pivot elements ： The first record 、 The last record 、 Intermediate records 、 Record of intermediate values 、 Random recording .

Algorithm analysis

The best situation ： The length of the left and right sub tables after each division is the same , The time complexity is O(nlog2n), Call it the best average performance .
The worst ： It's in order , The total number of comparisons n(n-1)/2, The time complexity is O(n2).
On average ：Tavg(n)=klog2n, The time complexity is O(nlog2n).
Spatial complexity ：O(log2n).
stability ： unstable .
Welcome to join me for wechat exchange and discussion （ Please note csdn Add ）