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 <j),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
©2019-2020 Toolsou All rights reserved,
Map judge key Corresponding value Does the value exist -containsKey() Unity3D Input Key system Map---Java judge Map Contains a keyelementui select obtain valueajax get Request Chinese parameter garbled solution inherit jpa Repository Write custom method query Go language Array initialization and basic operations ToastUtils Use of 【JAVA】【 Huawei campus recruitment written examination - Software 】2020-09-09JQ get request Splicing url parameter ( query criteria )