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
Sorting algorithm | Average time complexity | Spatial complexity | The stability of | The characteristics of |
Simple selection sort | O(n*n) | O(1) | unstable | Suitable for basic order |
Tree selection sort | O(n*logn) | O(n) | stable | Taking up too much space |
Heap selection sort | O(n*logn) | O(1) | unstable | Suitable for sorting with large n values |
Merge sort | O(n*logn) | O(n) | stable | Subsequences require order |
Radix sort | O(d*n) | 2 queue Pointers +n pointer fields | stable | Suitable for a small number of keywords |