Recently learn data structure, want to sort the algorithm summary comb, also pass the time.
1. Bubble sort
Bubble sort is a simple sorting algorithm. It repeatedly walks through the sequence to be sorted, comparing two elements at a time and swapping them if they are in the wrong order. The task of visiting an array is repeated until no more exchanges are needed, that is, the array has been sorted. 1 Compare adjacent elements. If the first one is larger than the second, swap them both; 2 Do the same for each pair of adjacent elements, starting with the first pair and ending with the last pair, so that the last element should be the largest; Repeat this step for all elements except the last one; Repeat steps 1 to 3 until the sorting is complete.Copy the code
void BubbleSort(int arr[], int size)
{
int i, j, tmp;
for (i = 0; i < size - 1; i++) {
for (j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j+1]) {
tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp; }}}}Copy the code2. Select sort
Selection-sort is a simple and intuitive sorting algorithm. It works by first finding the smallest (largest) element in the unsorted sequence and storing it at the beginning of the sorted sequence, then continuing to find the smallest (largest) element from the remaining unsorted elements and placing it at the end of the sorted sequence. And so on until all the elements are sorted. Direct selection sort of N records can get ordered results after n-1 direct selection sort. The specific algorithm is described as follows: initial state: the disordered region is R[1..n], and the ordered region is empty; Th order (I =1,2,3... N-1), the current ordered region and disordered region are R[1..i-1] and R(I.. N). This sort selects the record R[k] with the smallest keyword from the current unordered region and swaps it with the first record R in the unordered region, so that R[1.. I] and R[I +1..n) become the new ordered region with 1 more records and the new unordered region with 1 less records, respectively; at the end of n-1 turn, the array is ordered.Copy the code
void SelectionSort(int arr[], int size)// Select sort
{
int i, j, k, tmp;
for (i = 0; i < size - 1; i++) {
k = i;
for (j = i + 1; j < size; j++) {
if(arr[j] < arr[k]) { k = j; } } tmp = arr[k]; arr[k] = arr[i]; arr[i] = tmp; }}Copy the code3. Insert sort
In general, insert sorts are implemented on arrays using in-place. The algorithm is described as follows: Starting from the first element, the element can be considered to have been sorted; Fetch the next element and scan back to front in the sorted element sequence; If the element (sorted) is larger than the new element, move the element to the next position; Repeat step 3 until you find a place where the sorted element is less than or equal to the new element; After inserting a new element into that position; Repeat steps 2 to 5.Copy the code
void InsertionSort(int *arr, int size)// Insert sort
{
int i, j, tmp;
for (i = 1; i < size; i++) {
if (arr[i] < arr[i- 1]) {
tmp = arr[i];
for (j = i - 1; j >= 0 && arr[j] > tmp; j--) {
arr[j+1] = arr[j];
}
arr[j+1] = tmp; }}}Copy the codeBecause the name of the array is the address, I can also just take the address in the function which is *arr
4. Hill sort
1959 Shell invention, the first breakthrough O(N ^2) sorting algorithm, is an improved version of simple insertion sort. It differs from insertion sort in that it compares distant elements first. Hill sort is also called reduced increment sort. 4.1 Algorithm Description Firstly, the whole sequence of records to be sorted is divided into several sub-sequences for direct insertion sorting. The specific algorithm description is as follows: select an incremental sequence T1, T2... , where Ti >tj, tk=1; Sort the sequence k times according to the number of incremental sequences k; 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.Copy the code
void ShellSort(int *arr, int size) // Hill sort
{
int i, j, tmp, increment;
for (increment = size/ 2; increment > 0; increment /= 2) {
for (i = increment; i < size; i++) {
tmp = arr[i];
for (j = i - increment; j >= 0&& tmp < arr[j]; j -= increment) { arr[j + increment] = arr[j]; } arr[j + increment] = tmp; }}}Copy the code5. 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. 5.1 Algorithm description The input sequence of length N is divided into two sub-sequences of length N /2. Merge sort is used for these two subsequences respectively. Combine two sorted subsequences into a final sorted sequence.Copy the code
#define MAXSIZE 100
void Merge(int *SR, int *TR, int i, int middle, int rightend)
{
int j, k, l;
for (k = i, j = middle + 1; i <= middle && j <= rightend; k++) {
if (SR[i] < SR[j]) {
TR[k] = SR[i++];
} else{ TR[k] = SR[j++]; }}if (i <= middle) {
for (l = 0; l <= middle - i; l++) { TR[k + l] = SR[i + l]; }}if (j <= rightend) {
for (l = 0; l <= rightend - j; l++) { TR[k + l] = SR[j + l]; }}}void MergeSort(int *SR, int *TR1, int s, int t)
{
int middle;
int TR2[MAXSIZE + 1];
if (s == t) {
TR1[s] = SR[s];
} else {
middle = (s + t) / 2;
MergeSort(SR, TR2, s, middle);
MergeSort(SR, TR2, middle + 1, t); Merge(TR2, TR1, s, middle, t); }}Copy the code6. Quicksort
The basic idea of quicksort is that the records to be sorted are separated into two independent parts through a sort. If the keywords of one part of the records are smaller than those of the other part, the two parts of the records can be sorted separately to achieve the order of the whole sequence. 6.1 Algorithm Description Quicksort Divides a list into two sub-lists using the divide-and-conquer method. The algorithm is described as follows: Pick an element from the sequence, called "pivot"; Reorder the array so that all elements smaller than the base value are placed in front of the base value and all elements larger than the base value are placed behind the base value (the same number can go to either side). After the partition exits, the benchmark is in the middle of the array. This is called a partition operation; Recursively sorts subarrays of elements less than a reference value and subarrays of elements greater than a reference value.Copy the code
void QuickSort(int *arr, int maxlen, int begin, int end)
{
int i, j;
if (begin < end) {
i = begin + 1;
j = end;
while (i < j) {
if(arr[i] > arr[begin]) {
swap(&arr[i], &arr[j]);
j--;
} else{ i++; }}if(arr[i] >= arr[begin]) { i--; } swap(&arr[begin], &arr[i]); QuickSort(arr, maxlen, begin, i); QuickSort(arr, maxlen, j, end); }}void swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
Copy the code7. The heap sort
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. 7.1 Algorithm Description Initial keyword sequences (R1,R2... .rn) is constructed into the big top heap, which is the initial unordered region; 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]; 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.Copy the code
void Heapify(int *arr, int m, int size)
{
int i, tmp;
tmp = arr[m];
for (i = 2 * m; i <= size; i *= 2) {
if (i + 1 <= size && arr[i] < arr[i+1]) {
i++;
}
if (arr[i] < tmp) {
break;
}
arr[m] = arr[i];
m = i;
}
arr[m] = tmp;
}
void BulidHeap(int *arr, int size)
{
int i;
for (i = n / 2; i > 0; i--) { Heapify(arr, i, size); }}void swap(int *arr, int i, int j)
{
int tmp;
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
void HeapSort(int *arr, int size)
{
int i;
BulidHeap(arr, size);
for (i = size; i > 1; i--) {
swap(arr, 1, i);
Heapify(arr, 1, i - 1); }}Copy the code8. Counting sort
Counting sort is not a comparison-based sorting algorithm. Its core is to convert the input data values into keys and store them in an extra array space. As a sort of linear time complexity, counting sort requires that the input data must be integers with a definite range. 8.1 Algorithm Description Find the largest and smallest elements in the array to be sorted; 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; Add up all the counts (starting with the first element in C, adding each term to the previous one); Reverse populating the target array: place each element I in the C(I) item of the new array, subtracting C(I) by 1 for each element.Copy the code
void CountingSort(int *A, int *B, int n, int k)
{
int *C = (int *)malloc(sizeof(int) * (k + 1));
int i;
for (i = 0; i <= k; i++) {
C[i] = 0;
}
for (i = 0; i < n; i++) {
C[A[i]]++;
}
for (i = 1; i <= k; i++) {
C[i] = C[i] + C[i - 1];
}
for (i = n - 1; i >= 0; i--) {
B[C[A[i]] - 1] = A[i]; C[A[i]]--; }}Copy the code9. Bucket sorting
Bucket sort is an updated version of counting sort. It makes use of the mapping relation of functions, and the key of efficiency lies in the determination of the mapping function. Bucket sort works by dividing the data into a finite number of buckets, assuming that the input data is evenly distributed, and sorting each Bucket separately (it is possible to use a different sorting algorithm or recursive Bucket sorting). 9.1 Algorithm Description Set a quantitative array as an empty bucket. Iterate over the input data and put the data one by one into the corresponding bucket; Sort each bucket that is not empty; Splicing together sorted data from never-empty buckets.Copy the codevoid bucketSort(int *arr, int size, int max)
{
int i,j;
int buckets[max];
memset(buckets, 0, max * sizeof(int));
for (i = 0; i < size; i++) {
buckets[arr[i]]++;
}
for (i = 0, j = 0; i < max; i++) {
while((buckets[i]--) >0) arr[j++] = i; }}Copy the code10. Radix sort
Radix sort is sorted by low order and then collected; 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. 10.1 Algorithm Description Get the largest number in the array, and get the number of bits; Arr is the original array, and each bit is taken from the lowest level to form the RADIX array. The radix is sorted by counting (taking advantage of the fact that counting sorting is suitable for small range numbers);Copy the code
int get_index(int num, int dec, int order)
{
int i, j, n;
int index;
int div;
for (i = dec; i > order; i--) {
n = 1;
for (j = 0; j < dec - 1; j++)
n *= 10;
div = num / n;
num -= div * n;
dec--;
}
n = 1;
for (i = 0; i < order - 1; i++)
n *= 10;
index = num / n;
return index;
}
void RadixSort(int *arr, int len, int dec, int order)
{
int i, j;
int index;
int tmp[len];
int num[10];
memset(num, 0.10 * sizeof(int));
memset(tmp, 0, len * sizeof(int));
if (dec < order) {
return;
}
for (i = 0; i < len; i++) {
index = get_index(arr[i], dec, order);
num[index]++;
}
for (i = 1; i < 10; i++) {
num[i] += num[i- 1];
}
for (i = len - 1; i >= 0; i--) {
index = get_index(arr[i], dec, order);
j = --num[index];
tmp[j] = arr[i];
}
for (i = 0; i < len; i++) {
arr[i] = tmp[i];
}
RadixSort(arr, len, dec, order+1);
}
Copy the code