Ten classic sorting algorithms (dynamic demo + code)

The sorting algorithm is an important part of the data structure, and it is necessary to learn systematically.

Time and space complexity comparison

1 Bubble sort

Algorithm idea:

1. Compare adjacent elements. If the first one is bigger than the second, swap them both.
2. Do the same for each pair of adjacent elements, starting from the first pair to the last pair at the end. When we do that, the last element is going to be the largest number.
3. Repeat this step for all elements except the last one.
4. Keep repeating the above steps for fewer and fewer elements at a time until there are no more pairs to compare.

Code:

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

2 Selection sort

Algorithm idea:

1. Locate the smallest (largest) element in the unsorted sequence and store it at the start of the sorted sequence
2. Continue to find the smallest (largest) element from the remaining unsorted elements and place it at the end of the sorted sequence
3. And so on until all the elements are sorted

Code:

function selectionSort(arr) { var len = arr.length; var minIndex, temp; for (var i = 0; i < len - 1; i++) { minIndex = i; for (var j = i + 1; j < len; J ++) {if (arr[j] < arr[minIndex]) {// find minIndex = j; }} temp = arr[I]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } return arr; }Copy the code

3 Insert sort

Algorithm idea:

1. Start with the first element, which can be considered sorted
2. Takes the next element and scans back to front in the sorted element sequence
3. If the element (sorted) is larger than the new element, move the element to the next position
4. Repeat step 3 until you find a place where the sorted element is less than or equal to the new element
5. After inserting the new element into the location
6. Repeat steps 2 to 5

Code:

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); }}int main(){int a[15] = {2,3,4,5,15,19,16,27,36,38,44,46,47,48,50}; InsertSort(a,15); Print (a, 15, 15); }Copy the code

4 Quick Sort

Algorithm idea:

1. Take the first number as the base
2. Swap numbers smaller than the base to the front and numbers larger than the base to the back
3. Repeat the second step for the left and right intervals until each interval has only one number

Code:

Void QuickSort(vector<int> &v, int low, int high) {if (low >= high) return; int first = low; Int last = high; Int key = v[first]; While (first < last && v[last] >= key) last--; if (first < last) v[first++] = v[last]; While (first < last && v[first] <= key) first++; if (first < last) v[last--] = v[first]; } // v[first] = key; // QuickSort(v, low, first-1); // QuickSort(v, first + 1, high); }Copy the code

Heapsort refers to a sort algorithm designed by using heap data structure. Heap is a nearly complete binary tree structure, and also satisfies the property of heap: that is, the key value or index of the child node is always smaller (or larger) than its parent node.

Algorithm idea:

1. The initial sequence of keywords to be sorted (R1,R2… .rn) is constructed into the big top heap, which is the initial unordered region;
2. By exchanging the top element R[1] with the last element R[n], a new unordered region (R1,R2… Rn-1) and a new ordered region (Rn), and R[1,2… n-1]<=R[n];
3. Since the new heap top R[1] after the swap may violate the heap properties, it is necessary to apply the current unordered region (R1,R2… Rn-1) adjusts to the new heap, and then swaps R[1] again with the last element of the unordered region to obtain the new unordered region (R1,R2… .Rn-2) and the new ordered region (Rn-1,Rn). This process is repeated until the number of elements in the ordered region is N-1, and the whole sorting process is complete.

Code:

#include <iostream>#include <algorithm>using namespace std; // heap sort :(maximum heap, ordered region). Unload the roots from the top of the heap before placing them in the ordered zone, and then restore the heap. Void max_heapify(int arr[], int start, int end) {int dad = start; int son = dad * 2 + 1; While (son <= end) {if (son + 1 <= end && arr[son] < arr[son + 1]) // Select the largest son++; If (arr[dad] > arr[son]) // If (arr[dad] > arr[son]) Swap (arr[dad], arr[son]); dad = son; son = dad * 2 + 1; }}}void heap_sort(int arr[], int len) {for (int I = len / 2-1; i >= 0; i--) max_heapify(arr, i, len - 1); For (int I = len-1; int I = len-1; int I = len-1; i > 0; i--) { swap(arr[0], arr[i]); max_heapify(arr, 0, i - 1); }}int main() { int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };  int len = (int) sizeof(arr) / sizeof(*arr); heap_sort(arr, len); for (int i = 0; i < len; i++) cout << arr[i] << ' '; cout << endl; return 0; }Copy the code

6 merge sort

Merge sort is an efficient sorting algorithm based on merge operation. This algorithm is a very typical application of Divide and Conquer. The ordered subsequences are combined to obtain a fully ordered sequence. That is, each subsequence is ordered first, and then the subsequence segments are ordered. If two ordered tables are joined into one ordered table, it is called 2-way merge.

Algorithm idea: 1. Divide the input sequence of length N into two sub-sequences of length N /2; 2. 2. Merge sort is used for these two subsequences respectively; 3. Merge the two sorted subsequences into a final sorted sequence.

Code:

void print(int a[], int n){ for(int j= 0; j<n; j++){ cout<<a[j] <<" "; } cout<<endl; Rf [I... n]void Merge(ElemType *r,ElemType *rf, int I, int m, int n){int j,k; for(j=m+1,k=i; i<=m && j <=n ; ++k){ if(r[j] < r[i]) rf[k] = r[j++]; else rf[k] = r[i++]; } while(i <= m) rf[k++] = r[i++]; while(j <= n) rf[k++] = r[j++]; print(rf,n+1); }void MergeSort(ElemType *r, ElemType *rf, int lenght){ int len = 1; ElemType *q = r ; ElemType *tmp ; while(len < lenght) { int s = len; len = 2 * s ; int i = 0; while(i+ len <lenght){ Merge(q, rf, i, i+ s-1, i+ len-1 ); // Join I = I + len; } if(i + s < lenght){ Merge(q, rf, i, i+ s -1, lenght -1); } TMP = q; q = rf; rf = tmp; / / exchange q, rf, to ensure that the, when the next train merge from q merge to rf}} int main () {int a [10] =,3,4,5,15,19,26,27,36,38,44,46,47,48,50 {2}; int b[10]; MergeSort(a, b, 15); print(b,15); Cout <<" result: "; print(a,10); }Copy the code

7 Hill sort

Hill sort, also known as the descending incremental sort algorithm, is a more efficient and improved version of insertion sort. But Hill sort is an unstable sort algorithm. Firstly, the whole record sequence to be sorted is divided into several sub-sequences for direct insertion sorting.

Algorithm idea:

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.

Code:

void shell_sort(T array[], int length) {    int h = 1;    while (h < length / 3) {        h = 3 * h + 1;    }    while (h >= 1) {        for (int i = h; i < length; i++) {            for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {                std::swap(array[j], array[j - h]);            }        }        h = h / 3;    }}
Copy the code

8 Counting sort

Counting sort counts the number of elements I that are less than or equal to the value of the element, so the element is placed in the index bit I of the target array (I ≥0).

• Counting sort is based on the assumption that all the numbers in the sequence to be sorted are integers and occur within the interval (0, k).
• If k (the maximum size of the array to be sorted) is too large, it will cause too much space complexity. It is generally the best algorithm for sorting numbers between 0 and 100, but it is not suitable for sorting names alphabetically.
• Counting sort is not comparison sort, which is faster than any comparison sort algorithm.

Algorithm idea:

1. Find the largest and smallest elements in the array to be sorted;
2. Count the number of occurrences of each element of value I in the array and store it in the i-th entry of array C;
3. Add up all the counts (starting with the first element in C, adding each term to the previous one);
4. Populate the target array: place each element I in the C[I] entry of the new array, and subtract 1 from C[I] for each element;

Code:

#include <iostream>#include <vector>#include <algorithm>using namespace std; Void CountSort(vector<int>& vecRaw, vector<int>& vecObj){if (vecraw.size () == 0) return; Int vecCountLength = (*max_element(begin(vecRaw), end(vecRaw))) + 1; vector<int> vecCount(vecCountLength, 0); For (int I = 0; i < vecRaw.size(); i++) vecCount[vecRaw[i]]++; Int I = 1; for (int I = 1; i < vecCountLength; i++) vecCount[i] += vecCount[i - 1]; Vecraw.size (); for (int I = vecraw.size (); i > 0; VecObj [--vecCount[i-1]] = vecRaw[i-1]; vecObj[--vecCount[i-1]] = vecRaw[i-1]; {} int main () the vector < int > vecRaw =,5,7,9,6,3,4,5,2,8,6,9,2,1 {0}; vector<int> vecObj(vecRaw.size(), 0); CountSort(vecRaw, vecObj); for (int i = 0; i < vecObj.size(); ++i) cout << vecObj[i] << " "; cout << endl; return 0; }Copy the code

9 bucket sort

Put the elements of I into bucket I, and finally pour out the bucket in turn.

Algorithm idea:

1. Set a quantitative array as an empty bucket.
2. Search the sequence and put the items one by one into the corresponding bucket.
3. Sort each bucket that is not empty.
4. Put items back into their original sequence in a bucket that is never empty.

Code:

function bucketSort(arr, bucketSize) { if (arr.length === 0) { return arr; } var i; var minValue = arr[0]; var maxValue = arr[0]; for (i = 1; i < arr.length; i++) { if (arr[i] < minValue) { minValue = arr[i]; Else if (arr[I] > maxValue) {maxValue = arr[I]; }} // bucket initialization var DEFAULT_BUCKET_SIZE = 5; / / sets the default bucket number 5 bucketSize = bucketSize | | DEFAULT_BUCKET_SIZE; var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1; var buckets = new Array(bucketCount); for (i = 0; i < buckets.length; i++) { buckets[i] = []; } for (I = 0; i < arr.length; i++) { buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]); } arr.length = 0; for (i = 0; i < buckets.length; i++) { insertionSort(buckets[i]); // Insert sort for (var j = 0; j < buckets[i].length; j++) { arr.push(buckets[i][j]); } } return arr; }Copy the code

A multi – keyword sorting algorithm can be implemented by bucket sorting.

Algorithm idea:

1. Get the largest number in the array and get the number of digits;
2. Arr is the original array, and each bit is taken from the lowest level to form the RADIX array.
3. Counting sorting for the Radix (taking advantage of counting sorting for a small range of numbers)

Code:

Int maxbit(int data[], int n) {int maxData = data[0]; //< maximum number /// first calculate the maximum number, then calculate its number, so that the original sequence of each number judge its number, slightly optimized point. for (int i = 1; i < n; ++i) { if (maxData < data[i]) maxData = data[i]; } int d = 1; int p = 10; while (maxData >= p) { //p *= 10; // Maybe overflow maxData /= 10; ++d; } return d; /* int d = 1; // save the maximum number of digits int p = 10; for(int i = 0; i < n; ++i) { while(data[i] >= p) { p *= 10; ++d; } } return d; */}void radixsort(int data[], int n); int *tmp = new int[n]; int *count = new int[10]; // count int I, j, k; int radix = 1; for(i = 1; i <= d; I++) {for(j = 0; j < 10; j++) count[j] = 0; For (j = 0; j < n; j++) { k = (data[j] / radix) % 10; // Count the number of records in each bucket count[k]++; } for(j = 1; j < 10; j++) count[j] = count[j - 1] + count[j]; For (j = n-1; j >= 0; {k = (data[j] / radix) % 10; tmp[count[k] - 1] = data[j]; count[k]--; } for(j = 0; j < n; Data [j] = TMP [j]; radix = radix * 10; } delete []tmp; delete []count; }Copy the code

The resources

1. https://www.cnblogs.com/onepixel/p/7674659.html (partial dynamic graph source)
2. Electronic Engineering Album