【 Graph data structure 】 Comprehensive summary of sorting (II)

Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

One, foreword

• Review: the previous summary of the insertion class and swap class sorting for a more detailed summary, requirements for direct insert, split insert sort, bubble sort requirements proficient
• Learning objectives: Master simple selection sorting algorithm, understand the characteristics, space-time complexity and algorithm flow of tree selection sorting, heap selection sorting, merge sorting and radix sorting.

Second, select class sorting

Definition: Each time from the unordered sequence to be sorted, select a maximum or minimum number, put in front, the data element is empty when the sorting ends

1. Simple selection sort

Dynamic demonstration:

Algorithm explanation:

• Starting with the first number, find subscripts lower than that number and swap elements
• Starting with the second number, find subscripts lower than that number and swap elements
• Repeat the above operation n-1 times in total, and the sorting is complete

Code:

void SelectSort(RecordType r[], int length)
/* Do a simple selection sort on the record array r, length is the length of the array */
{
	int i,j,k,n=length;	
        RecordType x;    
	for ( i=1 ; i<= n- 1; ++i)  
	{
		k=i;
		for (j=i+1 ; j<= n ; ++j) 
			if (r[j].key < r[k].key ) k=j;
		if( k! =i) { x= r[i]; r[i]= r[k]; r[k]=x; }}}Copy the code

Features:

• Unstable sort
• Time complexity O(n*n), space complexity O(1)

2. Tree selection sort

Static demo:

Algorithm explanation:

• The bottom row 21, 25, 49, 25, 16, 08, 63 is given the number to sort from smallest to largest
• The two adjacent ones pick the smallest one to move up one level, and only one of them fills the number with an infinite value
• The penultimate layer is paired again until you reach the very top
• At this point, 08 at the top is the smallest number, print 08, and take all 08 to infinity
• Pick a minimum again, and so on

Features:

• The algorithm is not required
• Stable sorting, add extra storage space
• Time complexity O(Nlogn), space complexity O(n-1)

3. Heap selection sort

Dynamic demonstration:

Algorithm explanation:

• Those with the largest root values are called the big top heap, and those with the smallest root values are called the small top heap
• Starting at the last level, if the value of the child node is greater than that of the parent node, then the position is switched
• Push up until the root reaches its maximum value

Create the initial heap:

void crt_heap(RecordType r[], int length )
/* Create a heap for r, length is the length of the array */
{
	int i,n;
        n= length;
	for ( i=n/2; i >= 1; --i) /* Filter heap from [n/2] */ 
		sift(r,i,n);
}
Copy the code

Adjust the heap:

void  sift(RecordType  r[],  int k, int m)
/* If r[k..m] is a complete binary tree rooted in r[k], and the left and right subtrees rooted in R [2K] and R [2K +1] are large root heaps, adjust r[k..m] to satisfy the heap properties */
{	RecordType t;	int i,j;	int x;	int finished;
	t= r[k];          /* hold "root" record r[k] */ 	
     x=r[k].key;	i=k;	j=2*i;
	finished=FALSE;
	while( j<=m && ! finished ) {if (j<m  && r[j].key< r[j+1].key )  j=j+1;   /* If there is a right subtree and the root keyword of the right subtree is large, "filter" along the right branch */
		     if ( x>= r[j].key)	finished=TRUE;            /* Filter completed */ 
		     else 
		     {   r[i] = r[j];  i=j;  j=2*i;	}    /* Continue filtering */ 
		}
		r[i] =t;          /* r[k] fills in the appropriate position */ 
} 
Copy the code

Heap sort:

void  HeapSort(RecordType  r[],int length)
/* Heap sort on r[1..n]. After executing this algorithm, the records in r are sorted in order by key */ 
{
	int i,n;	RecordType b;
	crt_heap(r, length);	n= length;
	for (  i=n ; i>= 2; --i) 
	{
		b=r[1];     /* Swap the top record with the last record in the heap */ 
		r[1]= r[i];
		r[i]=b; 
		sift(r,1,i- 1);  /* Adjust r[1.. I -1] to heap */}}/* HeapSort */ 
Copy the code

Features:

• Heap selection is an improvement of the tree and takes up less space
• Unstable sort, suitable for large n sort
• Time complexity O(n*logn), space complexity O(1)

Merge sort

Method one:

• Divide the overall number in two and break it down layer by layer
• Once subdivided, each piece is sorted until the whole is in order

Method 2:

• To sort a sequence by merging two contiguous blocks together, and to sort two contiguous ordered blocks again until they are finally ordered (preferred)

Code:

void MergeSort ( RecordType  r[], int n) /* Merge sort on r[1..n] */ 
{
	MSort ( r, 1, n, r);
}
void   MSort(RecordType  r1[],  int  low,  int  high,  RecordType  r3[])
/* R1 [low..high] is sorted and placed in R3 [low..high], r2[low..high] is secondary space */ 
{
	int mid;   RecordType  r2[20];
	if (low==high)   r3[low]=r1[low];
	else
	{
		mid=(low+high)/2;
        MSort(r1,low, mid, r2);
        MSort(r1,mid+1,high, r2); Merge (r2,low,mid,high, r3); }}/* MSort */ 
Copy the code

Features:

• A stable sort
• Time complexity O(nlogn), space complexity O(n)
• Additional space is relatively large, rarely used for internal sort, mainly external sort

4. Assign class sorting

1. Multi-keyword sorting

​

• High priority: Sorted by face value in each of four categories by suit size
• Low priority: Sorting the different suits of the same denomination into 13 categories according to the size of the denomination

2. Chain radix sort

​

Algorithm explanation:

• For the nine three-digit numbers above, the first step is to sort them from the smallest to the largest
• Then the results of the first step are sorted in order of ten digits
• Finally, with the help of the results of the second step, in order from the smallest to the largest hundreds
• And again, it’s the same thing for 4 bits and 5 bits

Features:

• Time complexity O(d*n), where D is the key word count and n is the number of records
• Stable sort
• Space complexity =2 queue Pointers + N pointer fields

Fifth, summarize and conclude