This is the 28th day of my participation in the August Text Challenge.More challenges in August

Exchange sort

Basic idea:

According to the comparison results of two element keywords in the sequence, the position of the two records in the sequence is swapped, so as to ensure the overall order

Bubble sort

(1) Compare the values of elements in pairs from back to front (or from front to back). If it is in reverse order, swap them until the sequence comparison is complete, called a bubble, and the result will be the smallest element sorted

② In the next bubble, the smallest element determined in the previous bubble will not participate in the comparison, and other elements will continue to perform the exchange according to ①, and the second smallest element will be sorted

③ Sort all elements in order at most N-1 times

Note:

  • Bubble sort can end prematurely when no swap occurs in a run
  • Bubble sort is a stable sorting algorithm
void  BubbleSort(ElemType  A[],int  n){
for(i=0; i<n- 1 ; i++){
flag=false; // Record whether this sequence is swapped
for(j=n- 1; j>i ; j--)
if(A[j- 1].key>A[j].key){    // If it is in reverse order
swap(A[j- 1],A[j]);    / / exchange flag = true;
}
if(flag==false) // The table is in order if no swap occurs
return; }}Copy the code

Efficiency analysis:

  • Space efficiency: use only constant replication units, space complexity is O(1)
  • Optimal time complexity: the table itself is ordered, only n-1 times comparison, no exchange, time complexity is O(n).
  • Worst time complexity: in reverse order, n-1 rows are compared, and n- I rows are compared +3(n- I) swaps are performed on the ith row

  • Average time complexity: also 𝑂(𝑛2).
  • Note: The ordered subsequence produced by bubble sort must be globally ordered (as opposed to insertion sort), such that each sort has at least one element in its final position

Second, quicksort

Assuming that the sorting table length is N, the basic idea is:

① Take any element of the table to be sorted as the benchmark, and divide the table into two independent sub-tables L[1,… k-1] and L[K +1,… n] through one sorting, so that all elements in L[1,… k-1] are less than pivot. All elements in L[k+1… n] are greater than or equal to pivot

② Place pivot at its final position L[k], which is a sort

③ In the next sort, repeat the above process recursively for the two sub-tables until each part has only one element or is empty, that is, all elements are placed in their final position