Summarize eight sorting algorithms of memory sort

When n is large, the sorting method with time complexity O(nlog2n) should be adopted: quicksort, heap sort or merge sort order.

Quicksort: is currently based on the comparison of internal sorting is considered to be the best method, when the keywords to be sorted are randomly distributed, the average time of quicksort is the shortest;

1. Insertion Sort — Straight Insertion Sort

Basic idea:

Inserts a record into an ordered table, resulting in a new ordered table with an increment of 1. That is, the first record of the sequence is regarded as an ordered subsequence, and then the second record is inserted one by one until the whole sequence is ordered.

Important: Set up sentries for temporary storage and array boundaries.

Example of direct insert sort:

If an equal element is encountered, the inserted element places the desired element after the equal element. Therefore, the order of equal elements does not change, and the order that comes out of the original unordered sequence is the order that comes out of the sorted sequence, so insertion sort is stable.

Implementation of the algorithm:

void print(int a[], int n ,int i){ cout<<i <<":"; for(int j= 0; j<8; j++){ cout<<a[j] <<" "; } cout<<endl; } void InsertSort(int a[], int n) { for(int i= 1; i<n; I ++){if(a[I] < a[i-1]){// If (a[I] < a[i-1]){// If (a[I] < a[i-1]){ <, insert int j= I -1; int x = a[i]; A [I] = a[i-1]; / / has to move an element while (x < a [j]) {/ / search position in orderly table insert a [j + 1) = a, [j]. j--; } a[j] = x; } print(a,n, I); / / print on each sort results}} int main () {int a [8] =,1,5,7,2,4,9,6 {3}; InsertSort(a,8); Print (a, 8, 8); }Copy the code

Efficiency:

Time complexity: O (n^2).

Other insertion sorts are binary insertion sort and 2-way insertion sort.

Insert Sort — Hill Sort (Shell’s Sort)

Hill sorting was proposed by D.L.Shell in 1959, which is a great improvement over direct sorting. Hill sort is also called reduced increment sort

Basic idea:

Firstly, the whole sequence of records to be sorted is divided into several sub-sequences for direct insertion sort respectively. When the records in the whole sequence are “basically ordered”, the whole records are directly inserted and sorted successively.

Operation method:

1. Select a delta sequence T1, T2… , where Ti >tj, tk=1;

2. Sort the sequence k times according to the number of incremental sequences k;

3. In each sort, the sequence to be sorted is divided into several sub-sequences of length M according to the corresponding increment TI, and each sub-table is sorted by direct insertion. Only when the increment factor is 1, the whole sequence is treated as a table, and the length of the table is the length of the whole sequence.

Example of hill sort:

Algorithm implementation:

We simply deal with delta sequences: delta sequences D = {n/2,n/4, n/8….. 1} n is the number of numbers to sort

That is, the first set of records to be sorted is divided into several groups of subsequences according to a certain increment D (n/2, where n is the number of numbers to be sorted), and the subscript difference of records in each group is D. Direct insert sort is done for all elements in each group, and then it is grouped by a smaller increment (D /2), and direct insert sort is done again in each group. Keep decreasing increments until you get to 1, and finally use direct insert sort to complete the sort.

void print(int a[], int n ,int i){ cout<<i <<":"; for(int j= 0; j<8; j++){ cout<<a[j] <<" "; } cout<<endl; } /** * @param int dk to reduce the increment, dk=1 * */ void ShellInsertSort(int a[], int n, int dk) { for(int i= dk; i<n; ++ I){if(a[I] < a[i-dk]){// If (a[I] < a[i-dk]){ <, insert int j = i-dk; int x = a[i]; A [I] = a[i-dk]; While (x < a[j]){a[j+dk] = a[j]; j -= dk; } a[j] = x; } print(a, n, I); Void shellSort(int a[], int n){int dk = n/2; void shellSort(int a[], int n){void shellSort(int a[], int n){int dk = n/2; while( dk >= 1 ){ ShellInsertSort(a, n, dk); dk = dk/2; }} int main(){int a[8] = {3,1,5,7,2,4,9,6}; / / ShellInsertSort (a, 8, 1); // Insert sort shellSort(a,8); Print (a,8,8); }Copy the code

The analysis of hill sort prescription is very difficult. The comparison times of key codes and record movement times depend on the selection of incremental factor sequence D, and the comparison times of key codes and record movement times can be accurately estimated under specific circumstances. No one has given a method to select the best sequence of incremental factors. The sequence of incremental factors can be taken in various ways, including odd number and prime number, but it should be noted that there is no common factor except 1 in the incremental factor, and the last incremental factor must be 1. Hill sorting method is an unstable sorting method.

3. Select Sort — Simple Selection Sort

Basic idea:

In the set of numbers to be sorted, the smallest (or largest) number is selected and swapped with the number in the first position; Then swap the smallest (or largest) number with the second position of the remaining number, and so on, until the n-1st element (the second-to-last element) is compared with the NTH element (the last element).

Example of simple selection sort:

Operation method:

In the first run, the record with the smallest key code is found out from n records and exchanged with the first record.

In the second run, the record with the smallest key code is selected from n-1 records starting from the second record and exchanged with the second record.

And so on…..

At the i-th run, the record with the smallest key code is selected from the n-i+1 records starting from the i-th record and exchanged with the i-th record.

Until the entire sequence is ordered by key.

Algorithm implementation:

Void print (int a [], int n, int I) {cout < < "the first" < < I + 1 < < "trip:"; for(int j= 0; j<8; j++){ cout<<a[j] <<" "; } cout<<endl; } /** * @return int array key */ int SelectMinKey(int a[], int n, int I) {int k = I; for(int j=i+1 ; j< n; ++j) { if(a[k] > a[j]) k = j; } return k; } /** * selectSort ** / void selectSort(int a[], int n){int key, TMP; for(int i = 0; i< n; ++i) { key = SelectMinKey(a, n,i); // Select the smallest element if(key! = i){ tmp = a[i]; a[i] = a[key]; a[key] = tmp; } print(a, n, I); }} int main(){int a[8] = {3,1,5,7,2,4,9,6}; Cout <<" initial value: "; for(int j= 0; j<8; j++){ cout<<a[j] <<" "; } cout<<endl<<endl; selectSort(a, 8); Print (a, 8, 8); }Copy the code

Simple selection sort improvement – binary selection sort

Simple selection sort, each loop can only determine the sorted position of one element. We could consider an improvement to determine the position of two elements (the maximum and minimum records of the current trip) per loop, thereby reducing the number of loops required for sorting. The improved sorting of N data takes [n/2] cycles at most. The concrete implementation is as follows:

void SelectSort(int r[],int n) { int i ,j , min ,max, tmp; for (i=1 ; i <= n/2; I ++) {// do not more than n/2 times select sort min = I; max = i ; For (j= I +1; j<= n-i; j++) { if (r[j] > r[max]) { max = j ; continue ; } if (r[j]< r[min]) { min = j ; }} // The switching operation can be discussed separately to improve efficiency. r[i-1] = r[min]; r[min] = tmp; tmp = r[n-i]; r[n-i] = r[max]; r[max] = tmp; }}Copy the code

4. Select Sort — Heap Sort

Heap sort is a tree selection sort, which is an effective improvement over direct selection sort.

Basic idea:

A heap is defined as follows: a sequence of n elements (k1,k2… Kn), if and only if

Is called a heap. From the definition of the heap, the top element (that is, the first element) must be the smallest item (the small top heap). If a heap is stored in a one-dimensional array, the heap corresponds to a complete binary tree, and all non-leaf nodes have values no greater than (or less than) their children, and the root node (the top element of the heap) has a minimum (or maximum) value. Such as:

(a) big top heap sequence :(96, 83,27,38,11,09)

(b) small top heap sequence :(12,36,24,85,47,30,53,91)

Initially, the sequence of n numbers to be sorted is regarded as a sequential storage binary tree (one-dimensional array storage binary tree), adjust their storage order to make it a heap, output the top element of the heap, get the smallest (or largest) element of n elements, then the number of root nodes of the heap is the smallest (or maximum). The first (n-1) elements are then readjusted into the heap, and the top element is output, yielding the second smallest (or second largest) element of n elements. And so on, until you have a heap of only two nodes, and you swap them, and you end up with an ordered sequence of n nodes. This process is called heap sort.

Therefore, two problems need to be solved to realize heap sort: 1. How to build n numbers to be sorted into heap; 2. 2. How to adjust the remaining n-1 elements to make a new heap after the top element is output?

We’ll start with the second problem: the adjustment process for the remaining N-1 elements to rebuild the heap after the top elements are output. Ways to adjust the small top heap:

1) A heap with m elements is left with m-1 elements after the top element is output. The bottom element is sent to the top of the heap (the last element is swapped with the top) and the heap is destroyed simply because the root does not satisfy the heap’s properties.

2) Swap the root node with the smaller elements in the left and right subtrees.

3) If it is switched with the left subtree: if the left subtree heap is destroyed, that is, the root of the left subtree does not meet the properties of the heap, then the method (2) is repeated.

4) If it is swapped with the right subtree, if the right subtree heap is destroyed, that is, the root of the right subtree does not meet the nature of the heap. Then repeat method (2).

5) Continue the above swap operations for subtrees that do not meet the heap properties until leaf nodes and the heap is built.

This adjustment from root to leaf is called filtering. As shown in figure:

Let’s talk about the initial process of building a heap of n elements. Method of building heap: The process of building heap on the initial sequence is a process of repeated screening.

1) complete binary tree of n nodes, then the last node is noThe subtree of zero.

2) Filter from noStarts with a subtree at the root of the node, which becomes the heap.

3) After that, the subtrees with each node as the root are screened to become the heap until the root node.

As shown in the figure, the initial heap building process: unordered sequence: (49,38,65,97,76,13,27,49)

Implementation of the algorithm:

According to the algorithm description, heap sort requires two processes, one is to build the heap, and the other is to exchange the position of the top and the last element of the heap. So heapsort consists of two functions. One is the infiltration function that builds the heap, and the other is the function that calls the infiltration function repeatedly to achieve sorting.

void print(int a[], int n){ for(int j= 0; j<n; j++){ cout<<a[j] <<" "; } cout<<endl; } /** * it is known that H[s... m] satisfies the definition of a heap except for H[s] * adjust H[s] to make it a large top heap. * * @param H is the heap array to be adjusted * @param s is the position of the array element to be adjusted * */ void HeapAdjust(int H[],int s, int length) { int tmp = H[s]; int child = 2*s+1; // The position of the left child node. While (child <length) {if(child+1 <length && H[child]<H[child+1]) {// If the right child is larger than the left child (find the child node larger than the current node to be adjusted) ++child; } the if (H [s] < H [child]) {/ / if a larger child nodes is greater than the parent H [s] = H [child]; // Then move the larger child up and replace its parent s = child; Child = 2*s+1; child = 2*s+1; } else {// If the node to be adjusted is larger than its left and right children, no adjustment is needed and exit break; } H[s] = tmp; } print(H,length); Void BuildingHeap(int H[], int H[], int H[], int H[], int H[], int H[], Int I = (length-1) / 2 for (int I = (length-1) / 2; int I = (length-1) / 2; i >= 0; --i) HeapAdjust(H,i,length); } /** * HeapSort */ void HeapSort(int H[],int length) {// Heap(H, length); For (int I = length-1; i > 0; Int temp = H[I]; int temp = H[I]; H[i] = H[0]; H[0] = temp; HeapAdjust(H,0, I) HeapAdjust(H,0, I) after each swap between the top element and the last element in the heap; }} int main () {int H [10] =,1,5,7,2,4,9,6,10,8 {3}; Cout <<" initial value: "; print(H,10); HeapSort(H,10); //selectSort(a, 8); Cout <<" result: "; print(H,10); }Copy the code

Analysis:

Let the tree depth be k,. From root to leaf screening, elements are compared at most 2(K-1) times and records are exchanged at most K times. Therefore, after the heap is built, the number of filters in the sorting process does not exceed the following formula:

The number of heap comparisons does not exceed 4N times, so the worst case of heap sort is O(nlogn).

5. Swap Sort — Bubble Sort

Basic idea:

In a set of numbers to be sorted, the two adjacent numbers are compared and adjusted from top to bottom for all the numbers that are not yet sorted, so that the larger number sinks and the smaller one rises. That is, whenever two adjacent numbers are compared and find that their sort is the opposite of the sort required, they are swapped.

Example of bubble sort:

Implementation of the algorithm:

void bubbleSort(int a[], int n){ for(int i =0 ; i< n-1; ++i) { for(int j = 0; j < n-i-1; ++j) { if(a[j] > a[j+1]) { int tmp = a[j] ; a[j] = a[j+1] ; a[j+1] = tmp; }}}}Copy the code

Improvement of bubble sort algorithm

A common improvement to bubble sort is to add a symbolic variable exchange, which indicates whether data is exchanged during a particular sort. If there is no exchange during a particular sort, the data is sorted as required and can be immediately ended to avoid unnecessary comparisons. This paper also provides the following two improved algorithms:

1. Set a symbolic variable pos that records the last swap position in each sort run. Since all the records after the POS position have been swapped in place, it is only necessary to scan the POS position in the next sorting.

The improved algorithm is as follows:

void Bubble_1 ( int r[], int n) { int i= n -1; While (I > 0) {int pos= 0; For (int j= 0; j< i; j++) if (r[j]> r[j+1]) { pos= j; Int TMP = r[j]; r[j]=r[j+1]; r[j+1]=tmp; } i= pos; // Get ready for the next sort}}Copy the code

2. In traditional bubble sort, only one maximum value or minimum value can be found in each sort operation. We consider that we can get two final values (the largest value and the smallest value) at one time by bubbling forward and backward twice in each sort operation, thus reducing the number of sort trips almost by half.

The improved algorithm is implemented as follows:

void Bubble_2 ( int r[], int n){ int low = 0; int high= n -1; // Set the initial value of the variable int TMP,j; while (low < high) { for (j= low; j< high; + + j) / / is bubbling, find so much the if (r > r [j] [j + 1]) {TMP = r [j]; r[j]=r[j+1]; r[j+1]=tmp; } --high; For (j=high; j>low; If (r[j]<r[j-1]) {TMP = r[j]; r[j]=r[j-1]; r[j-1]=tmp; } ++low; // Change the low value by one bit}}Copy the code

6. Swap Sort — Quick Sort

Basic idea:

1) Select a base element, usually the first or last element,

2) Through a sorting, the records to be sorted are divided into two independent parts, and the element values of some records are smaller than the base element values. The other records element values greater than the reference value.

3) The base element is in the correct position after it is sorted

4) Then continue sorting the two parts of the records in the same way until the whole sequence is in order.

Example of quicksort:

(a) A sorting process:

(b) The whole process of sorting

Implementation of the algorithm:

Recursive implementation:

void print(int a[], int n){ for(int j= 0; j<n; j++){ cout<<a[j] <<" "; } cout<<endl; } void swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; } int partition(int a[], int low, int high) { int privotKey = a[low]; While (low < high && a[high] >= privotKey) --high; // Search forward from high, up to low+1. Swap (&a[low], &a[high]) smaller than the base element to the low swap(&a[low], &a[high]); while(low < high && a[low] <= privotKey ) ++low; swap(&a[low], &a[high]); } print(a,10); return low; } void quickSort(int a[], int low, int high){ if(low < high){ int privotLoc = partition(a, low, high); QuickSort (a, low, privotloc-1); QuickSort (a, privotLoc + 1, high); / / order of the Gao Zibiao recursive recursive}} int main () {int a [10] =,1,5,7,2,4,9,6,10,8 {3}; Cout <<" initial value: "; print(a,10); QuickSort (a, 0, 9); Cout <<" result: "; print(a,10); }Copy the code

Analysis:

Quicksort is generally considered to have the best average performance among sorting methods of the same order of magnitude (O(nlog2n)). However, if the initial sequence is ordered by key code or basically ordered, fast sort deforms into bubble sort. In order to improve it, the “three-point method” is usually used to select the reference record, that is, the two endpoints and midpoints of the sorting interval are adjusted to the pivot record. Quicksort is an unstable sorting method.

Quicksort improvements

In this improved algorithm, only the sub-sequence whose length is greater than K is recursively called quicksort, so that the original sequence is basically ordered, and then the whole basic ordered sequence is sorted by insertion sort algorithm. Practice shows that the time complexity of the improved algorithm is reduced, and the performance of the improved algorithm is the best when k is about 8. The algorithm idea is as follows:

void print(int a[], int n){ for(int j= 0; j<n; j++){ cout<<a[j] <<" "; } cout<<endl; } void swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; } int partition(int a[], int low, int high) { int privotKey = a[low]; While (low < high && a[high] >= privotKey) --high; // Search forward from high, up to low+1. Swap (&a[low], &a[high]) smaller than the base element to the low swap(&a[low], &a[high]); while(low < high && a[low] <= privotKey ) ++low; swap(&a[low], &a[high]); } print(a,10); return low; } void qsort_improve(int r[],int low,int high, int k){if(high-low > k){ Int pivot = partition(r, low, high); Qsort_improve (r, low, pivot - 1,k); qsort_improve(r, pivot + 1, high,k); } } void quickSort(int r[], int n, int k){ qsort_improve(r,0,n,k); For (int I =1; for(int I =1; i<=n; i ++){ int tmp = r[i]; int j=i-1; while(tmp < r[j]){ r[j+1]=r[j]; j=j-1; } r[j+1] = tmp; }} int main () {int a [10] =,1,5,7,2,4,9,6,10,8 {3}; Cout <<" initial value: "; print(a,10); QuickSort (a, 9, 4); Cout <<" result: "; print(a,10); }Copy the code

7. Merge Sort

Basic idea:

Merge sort is the merging of two (or more) ordered tables into a new ordered table, that is, the sequence to be sorted into several subsequences, each subsequence is ordered. Then the ordered subsequence is combined into a whole ordered sequence.

Merge sort example:

Merging method:

Let r[I… n] consist of two ordered subtables R [I… m] and R [m+1… n], with length of n-i +1 and n-m respectively.

1. J = m + 1; K = I; i=i; // set the start index of the two child tables and the start index of the auxiliary array

2. If I >m or j>n, go to ⑷ // one of the subtables has been merged, and the comparison is finished

3. If r[I]

4. If j<=n, put r[j… n] into RF [k… n] // The last table is not empty

5. The merger is complete.

   
   

void print(int a[], int n ,int i){ cout<<i <<":"; for(int j= 0; j<8; j++){ cout<<a[j] <<" "; } cout<<endl; } /** * @param int dk to reduce the increment, dk=1 * */ void ShellInsertSort(int a[], int n, int dk) { for(int i= dk; i<n; ++ I){if(a[I] < a[i-dk]){// If (a[I] < a[i-dk]){ <, insert int j = i-dk; int x = a[i]; A [I] = a[i-dk]; While (x < a[j]){a[j+dk] = a[j]; j -= dk; } a[j] = x; } print(a, n, I); Void shellSort(int a[], int n){int dk = n/2; void shellSort(int a[], int n){void shellSort(int a[], int n){int dk = n/2; while( dk >= 1 ){ ShellInsertSort(a, n, dk); dk = dk/2; }} int main(){int a[8] = {3,1,5,7,2,4,9,6}; / / ShellInsertSort (a, 8, 1); // Insert sort shellSort(a,8); Print (a,8,8); }Copy the code

An iterative algorithm for merging

A list of 1 elements is always ordered. Therefore, for n elements to be sorted, each element can be regarded as an ordered subtable. The subtables are combined in pairs to generate N /2 subtables. The length of the resulting subtables is 2 except for the last subtable, which may be 1. Pairwise merging is performed until a table of n elements ordered by key codes is generated.

void print(int a[], int n ,int i){ cout<<i <<":"; for(int j= 0; j<8; j++){ cout<<a[j] <<" "; } cout<<endl; } /** * @param int dk to reduce the increment, dk=1 * */ void ShellInsertSort(int a[], int n, int dk) { for(int i= dk; i<n; ++ I){if(a[I] < a[i-dk]){// If (a[I] < a[i-dk]){ <, insert int j = i-dk; int x = a[i]; A [I] = a[i-dk]; While (x < a[j]){a[j+dk] = a[j]; j -= dk; } a[j] = x; } print(a, n, I); Void shellSort(int a[], int n){int dk = n/2; void shellSort(int a[], int n){void shellSort(int a[], int n){int dk = n/2; while( dk >= 1 ){ ShellInsertSort(a, n, dk); dk = dk/2; }} int main(){int a[8] = {3,1,5,7,2,4,9,6}; / / ShellInsertSort (a, 8, 1); // Insert sort shellSort(a,8); Print (a,8,8); }Copy the code

Recursive algorithm for two – way merging

void print(int a[], int n ,int i){ cout<<i <<":"; for(int j= 0; j<8; j++){ cout<<a[j] <<" "; } cout<<endl; } /** * @param int dk to reduce the increment, dk=1 * */ void ShellInsertSort(int a[], int n, int dk) { for(int i= dk; i<n; ++ I){if(a[I] < a[i-dk]){// If (a[I] < a[i-dk]){ <, insert int j = i-dk; int x = a[i]; A [I] = a[i-dk]; While (x < a[j]){a[j+dk] = a[j]; j -= dk; } a[j] = x; } print(a, n, I); Void shellSort(int a[], int n){int dk = n/2; void shellSort(int a[], int n){void shellSort(int a[], int n){int dk = n/2; while( dk >= 1 ){ ShellInsertSort(a, n, dk); dk = dk/2; }} int main(){int a[8] = {3,1,5,7,2,4,9,6}; / / ShellInsertSort (a, 8, 1); // Insert sort shellSort(a,8); Print (a,8,8); }Copy the code

8. Radix Sort

Before we talk about radix sort, let’s talk about bucket sort:

Basic idea: is to divide the array into a limited number of buckets. Each bucket is sorted individually (it is possible to use another sorting algorithm or continue sorting with bucket sort recursively). Bucket sort is a kind of induction result of pigeon nest sort. Bucket sorting uses linear time (θ (n)) when the values in the array to be sorted are evenly distributed. But bucket sort is not comparison sort, and it is not affected by the O(n log n) lower bound. In simple terms, the data is grouped into buckets, and then the data in each bucket is sorted.

For example, sort n integers A[1..n] in the range of size [1..1000]

First, you can set the bucket to be in the range of size 10. Specifically, set B[1] to be an integer that stores [1..10], and set B[2] to store (10.. 20] the whole number… Set B[I] stores integers ((i-1)*10, I *10], I = 1,2,.. 100. There are 100 buckets.

Then, A[1..n] is scanned from top to bottom, placing each A[I] into the corresponding bucket B[j]. And then sort the numbers in each of those 100 buckets, and you can bubble, select, or even sort quickly, and generally you can do anything.

Finally, print the numbers in each bucket in turn, and print the numbers in each bucket from the smallest to the largest, so that you have a sorted sequence of all the numbers.

Let’s say I have n numbers, I have m buckets, and if the numbers are evenly distributed, I have n over m numbers in each bucket on average. if

Quicksort the numbers in each bucket, then the complexity of the whole algorithm is

  O(n   +   m   *   n/m*log(n/m))   =   O(n   +   nlogn   –   nlogm)  

As can be seen from the above equation, when m approaches n, the bucket sorting complexity approaches O(n).

Of course, the above complexity calculation is based on the assumption that the n input numbers are evenly distributed. It’s a strong assumption, but it doesn’t work that well in practice. If all the numbers fall into the same bucket, it degenerated into general sorting.

Most of the sorting algorithms are O(n2), and some of them are O(nlogn). Bucket sorting can achieve O (n) time complexity. But the downside of bucket sorting is:

1) First of all, the space complexity is relatively high, which requires large extra overhead. Sorting has the space overhead of two arrays, one to hold the sorted array and one to hold the bucket, so if the sorted array is 0 to m-1, then you need m buckets, and the bucket array has to have at least m Spaces.

2) Secondly, the elements to be sorted must be in a certain range, etc.

Bucket sort is a sort of allocation sort. The assignment sort is specific in that there is no need to compare key codes, but the premise is to know some specific conditions of the sequence to be sorted.

The basic idea of distributive sort: to put it bluntly, it is to sort buckets many times.

The radix sort process does not need to compare keywords, but rather implements sorting through the allocate and collect processes. Their time complexity can reach linear order O(n).

Example:

The 52 cards in playing cards can be divided into two fields according to the color and face value, and the size relationship is:

Color: plum < square < heart < black heart

Face value: 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A

That is, two cards, if the color is different, no matter how the face value, the color of the card is lower than the color of the high, only in the case of the same color, the size of the relationship is determined by the size of the face value. This is multi-key sort.

To get the sorting results, we discuss two sorting methods. Method 1: sort the color first, divide it into 4 groups, namely plum group, square group, heart group, black heart group. Then sort each group separately by face value. Finally, join the four groups together. Method 2: First give 13 numbering groups according to 13 denominations (2, 3… , No. A), put the cards into the corresponding numbering group according to their face value and divide them into 13 piles. Then give 4 numbered groups according to the color (plum, square, red heart, black heart), take out the cards in group 2 and put them into the corresponding color group respectively, and then take out the cards in group 3 and put them into the corresponding color group respectively… , in this way, the 4 color groups are ordered by face value, and then, the 4 color groups can be connected in turn.

Let the unordered sequence of n elements contain D keys {k1, k2… Kd}, is called sequence pair key codes {k1, k2… Kd} order means that for any two records r[I] and R [j](1≤ I ≤j≤n) satisfy the following order relation:

K1 is called the most dominant key code and KD is called the least minor key code.

Two multi-key sorting methods:

Multi-key sort the sequence from the least major key to the least major key or from the least major key to the most major key can be sorted in two ways:

MSD method (Most Significant Digit First) :

1) The sequence is divided into several sub-sequences by sorting and grouping according to K1. In the records of the same sequence, the key codes K1 are equal.

2) Then each group is sorted into subgroups according to K2. After that, the following key codes are sorted into subgroups until each subgroup is sorted according to the lowest key code KD.

3) Connect the groups to obtain an ordered sequence. Poker by color, face value sorting introduced in the method is MSD method.

The Least Significant Digit first method:

1) Sort from KD first, then sort KD-1, and repeat successively until the subsequence is divided into the smallest subsequence according to K1.

2) Finally connect each sub-sequence, you can get an orderly sequence, poker according to the color, face value sorting method introduced in the second is LSD method.

The basic idea of chain radix sort based on LSD method

The idea of “multi keyword sort” realizes “single keyword sort”. The single keyword of logarithmic or character type can be regarded as multiple keywords composed of multiple digits or characters. In this case, the method of “allocation-collection” can be used to sort. This process is called radix sort, in which the number of possible values of each digit or character is called radix. For example, playing cards have a base of 4 suits and a base of 13 faces. When arranging cards, you can first arrange according to the color, also can first arrange according to the face value. According to the color arrangement, first according to the red, black, square, flower order is divided into 4 piles (distribution), and then according to this order again stacked together (collection), and then according to the face value of the order is divided into 13 piles (distribution), and then according to this order stacked together (collection), so the second distribution and collection can be arranged in order cards.

Radix sort:

Sort by low order, then collect; And then sort it in order, and then collect it; And so on, all the way to the highest place. Sometimes some attributes are prioritized, first by low priority, then by high priority. The final order is that the higher-priority ones come first, and the lower-priority ones come first. Radix sort is based on sorting separately, collecting separately, so it’s stable.

Algorithm implementation:

void print(int a[], int n ,int i){ cout<<i <<":"; for(int j= 0; j<8; j++){ cout<<a[j] <<" "; } cout<<endl; } /** * @param int dk to reduce the increment, dk=1 * */ void ShellInsertSort(int a[], int n, int dk) { for(int i= dk; i<n; ++ I){if(a[I] < a[i-dk]){// If (a[I] < a[i-dk]){ <, insert int j = i-dk; int x = a[i]; A [I] = a[i-dk]; While (x < a[j]){a[j+dk] = a[j]; j -= dk; } a[j] = x; } print(a, n, I); Void shellSort(int a[], int n){int dk = n/2; void shellSort(int a[], int n){void shellSort(int a[], int n){int dk = n/2; while( dk >= 1 ){ ShellInsertSort(a, n, dk); dk = dk/2; }} int main(){int a[8] = {3,1,5,7,2,4,9,6}; / / ShellInsertSort (a, 8, 1); // Insert sort shellSort(a,8); Print (a,8,8); }Copy the code

conclusion

Summary of stability, time complexity and space complexity of various kinds of sorting:

We compare the case of the time complexity function:

The growth of time complexity function O(n)

So the sorting record for n is larger. The general selection is O(nlog2n) time complexity sorting method.

Time complexity:

(1) Square order (O(n2)) sorting all kinds of simple sorting: direct insertion, direct selection and bubble sorting; (2) Linear logarithmic order (O(nlog2n)) sort quick sort, heap sort and merge sort; (3) order O(n1+§),§ is a constant between 0 and 1.

Hill sort (4) linear order (O(n)) sort radix sort, in addition to the bucket, box sort.

Description:

When the original table is ordered or basically ordered, direct insertion sort and bubble sort can greatly reduce the number of comparison and moving records, and the time complexity can be reduced to O (n).

On the contrary, when the original table is basically ordered, it is degraded to bubble sort, and the time complexity is increased to O (n2).

Whether the original table is ordered or not has little effect on the time complexity of simple selection sort, heap sort, merge sort and radix sort.

Stability:

Stability of sorting algorithm: if there are multiple records with the same keyword in the sequence to be sorted, the relative order of these records remains unchanged, the algorithm is stable; If the relative order of records changes after sorting, the algorithm is said to be unstable. Stability benefits: If the sorting algorithm is stable, sort from one key, then from another key, and the results of the first key sort can be used by the second key sort. Radix sort is like this, sort first by the lowest order, then by the highest order, the same elements in the same order will not change. In addition, if the sorting algorithm is stable, redundant comparisons can be avoided.

Stable sorting algorithms: bubble sort, insertion sort, merge sort and radix sort

Not stable sorting algorithms: selection sort, quicksort, Hill sort, heap sort

Selection sorting algorithm criteria:

Each sorting algorithm has its advantages and disadvantages. Therefore, in practice, it is necessary to choose appropriately according to different situations, or even combine a variety of methods.

The basis for selecting a sorting algorithm

There are many factors that affect sorting and the algorithm with low average time complexity is not necessarily optimal. Conversely, sometimes an algorithm with a high average time complexity may be more suitable for some special cases. At the same time, the readability of algorithm should be considered to facilitate the maintenance of software. Generally speaking, the following four factors need to be considered:

1. The size of n, the number of records to be sorted;

2. The size of the data volume of the record itself, that is, the size of other information except the keywords in the record;

3. The structure and distribution of keywords;

4. Requirements for sorting stability.

Let the number of elements to be sorted be n.

1) When n is large, the sorting method with time complexity O(nlog2n) should be adopted: quicksort, heap sort or merge sort.

Quicksort: is currently based on the comparison of internal sorting is considered to be the best method, when the keywords to be sorted are randomly distributed, the average time of quicksort is the shortest; Heap sort: if the memory space allows and requires stability,

Merge sort: it has a certain amount of data movement, so we might combine it with insert sort to get a certain length of sequence first and then merge it, which would be more efficient.

2) When n is large, the memory space allows, and requires stability = “merge sort

3) When n is small, direct insertion or direct selection sort can be used.

Direct insert sort: When elements are ordered, direct insert sort greatly reduces the number of comparisons and moves.

Direct selection sort: the elements are ordered. If stability is not required, select direct selection sort

5) The traditional bubble sort is generally not used or not directly used.

6) Radix sort it is a stable sorting algorithm, but there are certain limitations: 1, the keyword can be decomposed. 3, if it is a number, it is best to be unsigned, otherwise it will increase the corresponding mapping complexity, can first separate the positive and negative sorting.