©2020-2024 ioDraw All rights reserved
A hundred people see a hundred me , I am both an angel and a devil
There will always be all kinds of people on the way of life
They all have different opinions about us
Just like good people see hard-working people , He feels very disciplined Very hard
And some people who have nothing and want to lie flat , It feels like he's rolling Very work
What we need to do is not to change our goals because of the eyes of those lying flat
But quietly trying to become someone else's dream
1. Bubble sorting
2. Quick sort
3. Merge sort
1, Bubble sorting
Ascending sort ：
Ascending order ： Comparison of each trip , Will return the largest number in the comparison
Descending order ： Comparison of each trip , Will return the lowest decimal point in the number of comparisons
reflection ： If it's already orderly or close to orderly , And compare n-1 Do you want to go ?（ If so, compare it n-1 It's too much trouble !）
terms of settlement ：
We can use a variable record , If there is no exchange in the trip , Default to 0, If there's an exchange, it's for 1. Then judge whether the variable is 0, If for 0 Jump out of comparison loop , Otherwise, continue the loop comparison .
code ：
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> // exchange void Swap(int* p1,
int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } // Bubble sorting void BubbleSort(int*
a, int n) { for (int j = 0; j < n; j++) { int exchange = 0; for (int i = 1; i <
n - j; i++) { if (a[i - 1] > a[i]) { Swap(&a[i - 1], &a[i]); exchange =
1;// Avoid unnecessary sorting } } if (exchange == 0) { break; } } } void PrintArray(int* a, int
n) { for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } int
main() { int a[] = { 7, 3, 2, 6, 8, 1, 9}; int size = sizeof(a) / sizeof(int);
BubbleSort(a, size); PrintArray(a, size); return 0; }
Summary of bubble sorting characteristics ：
* Bubble sort is a sort that is very easy to understand
* Time complexity ：O(N^2)
* Spatial complexity ：O(1)
* stability ： stable
2, Quick sort
2.1 Excavation method
notes ： Generally, the first or last number is used as a keyword , Find the keyword to the left key Small value , Find keyword ratio to the right key Large value .
thinking ： First, assign the first number as a keyword to key, Then the position of the first number is a pit , from end Look to the left for a number smaller than the keyword , Find him and put him in the pit , Then its location becomes a new pit , Then from begin Find a number larger than the keyword to the right and put it into a new pit to continue to form a new pit , In this order until end and begin and pivot Point to the same position key Put it in this place , This sort will put a number back . Then order the numbers to the left of this number in the same way , The numbers on the right are ordered , The whole array is ordered .
reflection ： Why begin < end ?
Because when begin = end Time ,key The value will return , then key Previously less than key value ,key Has been greater than key value . So there is no need to cross search .
consider ： When is quicksort the worst ? When it's in order , The time complexity is O(N^2).
So how do we solve this problem ???
Using the method of taking the middle of three numbers .
The thought of the method of taking the middle of three numbers ： Compare the number of the first subscript and the number of the middle subscript with the number of the last subscript , Return median （ Not the largest nor the smallest ）.
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> // exchange void Swap(int* p1,
int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } // Triple median method int GetMidIndex(int*
a, int left, int right) { int mid = (left + right) >> 1; if (a[left] < a[mid])
{ if (a[mid] < a[right]) { return mid; } else if (a[left] > a[right]) { return
left; } else { return right; } } else // a[left] > a[mid] { if (a[mid] >
a[right]) { return mid; } else if (a[left] < a[right]) { return left; } else {
return right; } } } // Pit digging method for quick sorting void QuickSort(int* a,int left,int right) { if
(left >= right) { return; } int index = GetMidIndex(a, left, right);
Swap(&a[left], &a[index]); int begin = left; int end = right; int key =
a[begin]; int pivot = begin; while (begin < end) { while (begin < end && a[end]
>= key) { end--; } a[pivot] = a[end]; pivot = end; while (begin < end &&
a[begin] <= key) { begin++; } a[pivot] = a[begin]; pivot = begin; } a[pivot] =
key; QuickSort(a, left, pivot - 1); QuickSort(a, pivot + 1, right); } void
PrintArray(int* a, int n) { for (int i = 0; i < n; i++) { printf("%d ", a[i]);
} printf("\n"); } int main() { int a[] = { 7, 3, 2, 6, 8, 1, 9}; int size =
sizeof(a) / sizeof(int); QuickSort(a, 0, size - 1); PrintArray(a, size); return
0; }
2.2 Left and right pointer method
thinking ： Find the one smaller than the keyword to the left , Find one larger than keyword to the right , Exchange after finding
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> // exchange void Swap(int* p1,
int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } // Triple median method int GetMidIndex(int*
a, int left, int right) { int mid = (left + right) >> 1; if (a[left] < a[mid])
{ if (a[mid] < a[right]) { return mid; } else if (a[left] > a[right]) { return
left; } else { return right; } } else // a[left] > a[mid] { if (a[mid] >
a[right]) { return mid; } else if (a[left] < a[right]) { return left; } else {
return right; } } } // Left and right pointer method of quick sorting void QuickSort2(int* a, int lefti, int righti)
{ if (lefti >= righti) { return; } int index = GetMidIndex(a, lefti, righti);
Swap(&a[lefti], &a[index]); int left = lefti; int right = righti; int key =
left; while (left < right) { while (left < right && a[right] >= a[key]) {
--right; } while (left < right && a[left] <= a[key]) { ++left; } Swap(&a[left],
&a[right]); } Swap(&a[key], &a[left]); QuickSort2(a, lefti, left-1);
QuickSort2(a, left+1, righti); } void PrintArray(int* a, int n) { for (int i =
0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } int main() { int a[] =
{ 7, 3, 2, 6, 8, 1, 9}; int size = sizeof(a) / sizeof(int); QuickSort2(a, 0,
size - 1); PrintArray(a, size); return 0; }
2.3 Front and back pointer method
thinking ：front Find a comparison in front key Large value , When found after++, Then swap the two values （ Push the small one forward , Big push back ）
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> // exchange void Swap(int* p1,
int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } // Triple median method int GetMidIndex(int*
a, int left, int right) { int mid = (left + right) >> 1; if (a[left] < a[mid])
{ if (a[mid] < a[right]) { return mid; } else if (a[left] > a[right]) { return
left; } else { return right; } } else // a[left] > a[mid] { if (a[mid] >
a[right]) { return mid; } else if (a[left] < a[right]) { return left; } else {
return right; } } } // Before and after pointer method of quick sorting void QuickSort3(int* a, int lefti, int righti)
{ if (lefti >= righti) { return; } int index = GetMidIndex(a, lefti, righti);
Swap(&a[lefti], &a[index]); int after = lefti; int front = lefti + 1; int key =
lefti; while (front <= righti) { if (a[front] < a[key]) { after++;
Swap(&a[front], &a[after]); } front++; } Swap(&a[after], &a[key]);
QuickSort3(a, lefti, after - 1); QuickSort3(a, after + 1, righti); } void
PrintArray(int* a, int n) { for (int i = 0; i < n; i++) { printf("%d ", a[i]);
} printf("\n"); } int main() { int a[] = { 7, 3, 2, 6, 8, 1, 9}; int size =
sizeof(a) / sizeof(int); QuickSort3(a, 0, size - 1); PrintArray(a, size);
return 0; }
Summary of quick sort features ：
* The overall comprehensive performance and usage scenarios of quick sort are relatively good , That's why I dare to call it quick sort
* Time complexity ：O(N*logN)
* Spatial complexity ：O(logN)
* stability ： instable
3, Merge sort
basic thought ： Merge sort （MERGE-SORT） It is an effective sorting algorithm based on merging operation , The algorithm adopts divide and conquer method （Divide and
Conquer） A very typical application of . Merge ordered subsequences , Get a completely ordered sequence ; That is, first make each sub sequence orderly , Then make the subsequence segments orderly . If two ordered tables are combined into one ordered table , It is called two-way merging .
#include<stdlib.h> #include<stdio.h> // Merge sort void _MergeSort(int* a, int left,
int right, int* tmp) { if (left >= right) return; int mid = (left + right) >>
1; // hypothesis [left, mid] [mid+1, right] Orderly , Then we can merge _MergeSort(a, left, mid, tmp);
_MergeSort(a, mid + 1, right, tmp); // Merge int begin1 = left, end1 = mid; int
begin2 = mid + 1, end2 = right; int index = left; while (begin1 <= end1 &&
begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; }
else { tmp[index++] = a[begin2++]; } } while (begin1 <= end1) { tmp[index++] =
a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } // Copy back
for (int i = left; i <= right; ++i) { a[i] = tmp[i]; } } void MergeSort(int* a,
int n) { int* tmp = (int*)malloc(sizeof(int)*n); _MergeSort(a, 0, n - 1, tmp);
free(tmp); } void PrintArray(int* a, int n) { for (int i = 0; i < n; i++) {
printf("%d ", a[i]); } printf("\n"); } int main() { MergeSort(a, size - 1);
PrintArray(a, size); return 0; }
Summary of characteristics of merging and sorting ：
* The disadvantage of merging is the need O(N) Spatial complexity of , The thinking of merging and sorting is to solve the problem of external sorting in the disk topic .
* Time complexity ：O(N*logN)
* Spatial complexity ：O(N)
* stability ： stable
Complexity and stability analysis of sorting algorithm
Technology