One , Introduction to sorting

1. Sorting classification

According to the different principles in the sorting process, it can be classified as :

► Insert sort ： Direct insert sort   Shell Sort

► Exchange sort ： Bubble sorting   Quick sort

► Select sort ： Simple selection sorting   Heap sort

► Merge sort

► Cardinality sort

2. Comparison of sorting algorithms

Sorting method

Best time

average time

Worst time

Secondary storage

stability

remarks

Select sort

O(n^2)

O(n^2)

O(n^2)

O(1)

instable

Insert sort

O(n)

O(n^2)

O(n^2)

O(1)

stable

Bubble sorting

O(n)

O(n^2)

O(n^2)

O(1)

stable

Shell Sort

O(n^1.3)

O(nlogn)

O(n^2)

O(1)

instable

Quick sort

O(nlogn)

O(nlogn)

O(n^2)

O(logn)

instable

Heap sort

O(nlogn)

O(nlogn)

O(nlogn)

O(1)

instable

Merge sort

O(nlogn)

O(nlogn)

O(nlogn)

O(n)

stable

Cardinality sort

O(kn)

O(kn)

O(kn)

O(n)

stable

On average ： Heap sort , Merge sort , Quick sort is better than Hill sort .

At best ： Bubble sort and direct insert sort are better .

At worst ： Heap sort and merge sort are better than fast sort .

Although direct insertion and bubble sorting are slow , But when the initial sequence is globally or locally ordered , The efficiency of these two algorithms is relatively high . When the initial sequence is globally or locally ordered , The efficiency of fast sorting algorithm will decrease . When the sorting sequence is small and does not require stability , The efficiency of direct sorting is better ; When stability is required , Bubble sorting method is more efficient .

Two , Direct insert sort

method ： For a given set of records , Initially, it is assumed that the first record is an ordered sequence , The rest of the records are unordered ; Then start with the second record , Inserts the currently processed records into the previous ordered sequence according to the size of the records , Until the last record is inserted into an ordered sequence .

#include <stdio.h> void InsertSort(int array[], int len) { int i, j, temp;
for(i = 1; i < len; i++) { temp = array[i]; for(j = i - 1; j >= 0; j--) {
if(temp < array[j]) { array[j + 1] = array[j]; } else { break; } } array[j + 1]
= temp; } } int main() { int i = 0; int a[] = {8, 2, 5, 3, 6, 7, 1, 9, 0}; int
length = sizeof(a) / sizeof(a[0]); InsertSort(a, length); for(i = 0; i <
length; i++) { printf("%d ", a[i]); } return 0; }
Three , Shell Sort

Hill sorting is also known as “ Reduce incremental sort ”, The basic principle is ： First, the elements to be sorted are divided into multiple subsequences , Make the number of elements in each sub order relatively small , Insert and sort the sub orders directly , Waiting for the whole sequence to be sorted “ After basic order ”, Once more, all elements are inserted and sorted directly .

The specific steps are as follows ：

(1) Select a step sequence t1, t2, ... tk, satisfy ti > tj(i <ｊ),tk = 1.

(2) Number of sequences by step k, To sort the sequence k Rank order .

(3) Sort each time , According to the corresponding step size ti, Divide the sequence to be sorted into ti Subsequence , Each subsequence is inserted and sorted directly .

#include <stdio.h> void ShellSort(int array[], int len) { int i, j, temp, h;
for(h = len / 2; h > 0; h = h / 2) { for(i = h; i < len; i++) { temp =
array[i]; for(j = i - h; j >= 0; j -= h) { if(temp < array[j]) { array[j + h] =
array[j]; } else { break; } } array[j + h] = temp; } } } int main() { int i =
0; int a[] = {8, 2, 5, 3, 6, 7, 1, 9, 0}; int length = sizeof(a) /
sizeof(a[0]); ShellSort(a, length); for(i = 0; i < length; i++) { printf("%d ",
a[i]); } return 0; }
Four , Bubble sorting
#include <stdio.h> void BubbleSort(int array[], int len) { int i, j; int temp;
for (i = 0; i < len -1; ++i) { for (j = len - 1; j > i; --j) { if (array[j] <
array[j - 1]) { temp = array[j]; array[j] = array[j - 1]; array[j - 1] = temp;
} } } } int main() { int i = 0; int a[] = {29, 18, 87, 56, 3, 27}; int length =
sizeof(a) / sizeof(a[0]); BubbleSort(a, length); for (i = 0; i < length; i++) {
printf("%d ", a[i]); } printf("\n"); return 0; }
Five , Quick sort （ Efficient ）

use “ divide and rule ” Thought of , Divide the big into the small , The smaller ones are being split into smaller ones .

principle ： For a given set of records , After one pass sorting , Divide the original sequence into two parts , All records in the former part are smaller than those in the latter part , Then, the records of the two parts are sorted in turn , Recurse the process , Until all records in the sequence are in order .

#include <stdio.h> int a[30], n; void QuickSort(int left, int right) { int i,
j, tmp, tmp1; i = left; j = right; if(left >= right) { return; } while(i < j) {
while(a[j] >= a[left] && i < j) //left As reference { j--; } while(a[i] <= a[left] && i
< j) { i++; } if(i < j) { tmp = a[i]; a[i] = a[j]; a[j] = tmp; } } tmp1 = a[i];
a[i] = a[left]; a[left] = tmp1; QuickSort(left, i - 1); QuickSort(i + 1,
right); } int main() { int i; printf("Please input n:\n"); scanf("%d", &n);
printf("Please input number:\n"); for(i = 1; i <= n; i++) { scanf("%d", &a[i]);
} QuickSort(1, n); for(i = 1; i <= n; i++) { printf("%d ", a[i]); } return 0; }
Six , Simple selection sorting

For a given set of records , Minimum record after first round comparison , The record is then exchanged with the location of the first record ; Next, the second round of sorting is carried out for other records excluding the first record , Get the minimum record and exchange position with the second record ; Repeat the process , Until there is only one record for comparison .

#include <stdio.h> void SelectSort(int *num, int n) { int i, j; int tmp = 0,
min = 0; for(i = 0; i < n - 1; i++) { min = i; for(j = i + 1; j < n; j++) {
if(num[j] < num[min]) { min = j; } } if(min != i) { tmp = num[i]; num[i] =
num[min]; num[min] = tmp; } } } int main() { int i, len; int num[] = {4, 8, 2,
4, 0, 9, 1, 3, 5}; len = sizeof(num) / sizeof(num[0]); SelectSort(num, len);
for(i = 0; i < len; i++) { printf("%d ", num[i]); } return 0; }
Seven , Heap sort

*    Construct the sequence into a complete binary tree ;
*    Transform this ordinary binary tree into a pile , To get the minimum ;
*    Output min ;
*    Delete root , Continue to transform the remaining trees into piles , Then you can get the minor value ;
*    Output minor value ;
*    Repeated transformation , Output minor value , Next small value , Until all nodes output , And you get a sort .

#include <stdio.h>// It is suitable for large amount of data ( Building wastes time ) void AdjustMinHeap(int *array, int pos,
int len) { int tmp, child; for(tmp = array[pos]; 2 * pos + 1 <= len; pos =
child) { child = 2 * pos + 1; if(child < len && array[child] > array[child +
1]) { child++; } if(array[child] < tmp) { array[pos] = array[child]; } else {
break; } } array[pos] = tmp; } void Swap(int *a, int *b) { int temp; temp = *a;
*a = *b; *b = temp; } void HeapSort(int *array, int len) { int i; for(i = len/2
- 1; i >= 0; i--) { AdjustMinHeap(array, i, len - 1); } for(i = len - 1; i >=
0; i--) { Swap(&array[0], &array[i]); AdjustMinHeap(array, 0, i - 1); } } int
main() { int i; int array[] = {0, 13, 14, 1, 18, 27}; int length =
sizeof(array) / sizeof(array[0]); HeapSort(array, length); for(i = 0; i <
length; i++) { printf("%d ", array[i]); } return 0; }
Eight , Merge sort

Using recursion and divide and conquer technology to divide data series into smaller and smaller half sub tables , Sort the half sub table again , Finally, we use recursive steps to merge the ordered half tables into larger and larger ordered sequences .

principle ： For a given set of records , First, the two adjacent lengths are 1 Merge the subsequences of , obtain n/2 Length is 2 perhaps 1 Ordered subsequence of , In merging the two , Repeat this process , Until we get an ordered sequence .

#include <stdio.h> #include <stdlib.h> void Merge(int array[], int start, int
middle, int end) { int i, j, k, n1, n2; n1 = middle - start + 1; n2 = end -
middle; int *L = (int *)malloc(n1 * sizeof(int)); int *R = (int *)malloc(n2 *
sizeof(int)); for (i = 0, k = start; i < n1; i++, k++) { L[i] = array[k]; } for
(i = 0, k = middle + 1; i < n2; i++, k++) { R[i] = array[k]; } for (k = start,
i = 0, j = 0; i < n1 && j < n2; k++) { if (L[i] < R[j]) { array[k] = L[i]; i++;
} else { array[k] = R[j]; j++; } } if (i < n1) { for (j = i; j < n1; j++, k++)
{ array[k] = L[j]; } } if (j < n2) { for (i = j; i < n2; i++, k++) { array[k] =
R[i]; } } } void MergeSort(int array[], int start, int end) { int middle; int
i; if (start < end) { middle = (start + end) / 2; MergeSort(array, start,
middle); MergeSort(array, middle + 1, end); Merge(array, start, middle, end); }
} int main() { int i = 0; int a[] = {49, 38, 65, 97, 76, 13, 27}; int length =
sizeof(a) / sizeof(a[0]); MergeSort(a, 0, length -1); for (i = 0 ; i < length;
i++) { printf("%d ", a[i]); } printf("\n"); return 0; }
Nine , Cardinality sort

step ：

(1) distribution , Start with a bit , According to bit value (0-9) Put them separately 0~9 In barrel No （ such as 53, Bits are 3, Put in 3 In barrel No ）

(2) collect , Then place the 0~9 The data in bucket No. 1 is put into the array in order

#include <stdio.h> int Getmax(int *a, int n) { int i, max; max = a[0]; for(i =
0; i < n; i++) { if(max < a[i]) { max = a[i]; } } return max; } int
countsort(int *a,int n, int exp) { int output[n]; int buckets[10] = {0}; int i;
for(i = 0; i < n; i++) { buckets[(a[i] / exp) % 10]++; } for(i = 1; i < n; i++)
{ buckets[i] += buckets[i - 1]; } for(i = n - 1; i >= 0; i--) {
output[buckets[(a[i] / exp) % 10] - 1] = a[i]; buckets[(a[i] / exp) % 10]--; }
for(i = 0; i < n; i++) { a[i] = output[i]; } return 1; } int Radixsort(int *a,
int n) { int exp; int max = Getmax(a, n); for(exp = 1; (max / exp) > 0; exp *=
10 ) { countsort(a,n,exp); } return 1; } int main() { int i; int a[] = {278,
109, 63, 930, 589, 184, 505, 269, 8, 83}; int len = sizeof(a) / sizeof(a[0]);
Radixsort(a, len); for(i = 0; i < len; i++) { printf("%d ", a[i]); } return 0; }

Technology
Daily Recommendation