YouTip

### Bubble Sort Bubble Sort is a simple sorting algorithm. It repeatedly steps through the list to be sorted, compares two adjacent elements, and swaps them if they are in the wrong order (e.g., from largest to smallest, or from A to Z). The pass through the list is repeated until the list is sorted. Process demonstration: !(#) ## Example #includevoid bubble_sort(int arr[], int len); int main(){int arr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70}; int len = sizeof(arr) / sizeof(arr); bubble_sort(arr, len); for(int i = 0; i<len; i++){printf("%d ", arr); }return 0; }void bubble_sort(int arr[], int len){for(int i = 0; i<len - 1; i++){for(int j = 0; jarr[j + 1]){int temp = arr; arr = arr[j + 1]; arr[j + 1] = temp; }}}} ### Selection Sort Selection sort is a simple and intuitive sorting algorithm. It works as follows: First, find the smallest (or largest) element in the unsorted sequence and place it at the beginning of the sorted sequence. Then, find the smallest (or largest) element from the remaining unsorted elements and place it at the end of the sorted sequence. Repeat this process until all elements are sorted. Process demonstration: !(#) !(#) ## Example #includevoid selection_sort(int a[], int len); int main(){int arr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70}; int len = sizeof(arr) / sizeof(arr); selection_sort(arr, len); for(int i = 0; i<len; i++){printf("%d ", arr); }return 0; }void selection_sort(int a[], int len){for(int i = 0; i<len - 1; i++){int min = i; for(int j = i + 1; j<len; j++){if(a<a){min = j; }}if(min != i){int temp = a; a = a; a = temp; }}} ### Insertion Sort Insertion Sort is a simple and intuitive sorting algorithm. Its principle is to build a sorted sequence. For unsorted data, it scans backwards from the end of the sorted sequence to find the appropriate position and inserts it. In implementation, Insertion Sort typically uses in-place sorting (i.e., requiring only O(1) extra space). Therefore, during the backwards scan, it repeatedly shifts sorted elements backward to make space for the new element. Process demonstration: !(#) ## Example #includevoid insertion_sort(int arr[], int len); int main(){int arr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70}; int len = sizeof(arr) / sizeof(arr); insertion_sort(arr, len); for(int i = 0; i<len; i++){printf("%d ", arr); }return 0; }void insertion_sort(int arr[], int len){for(int i = 1; i0&&arr>temp){arr = arr; j--; }arr = temp; }} ### Shell Sort Shell Sort, also known as the diminishing increment sort algorithm, is a more efficient improvement of Insertion Sort. Shell Sort is an unstable sorting algorithm. Shell Sort is based on the following two properties of Insertion Sort to propose improvements: * Insertion Sort is efficient when operating on nearly sorted data, achieving linear sorting efficiency. * However, Insertion Sort is generally inefficient because it can only move data by one position at a time. Process demonstration: !(#) ## Example #includevoid shell_sort(int arr[], int len); int main(){int arr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70}; int len = sizeof(arr) / sizeof(arr); shell_sort(arr, len); for(int i = 0; i0; gap /= 2){for(int i = gap; i= gap&&arr>temp){arr = arr; j -= gap; }arr = temp; }}} ### Merge Sort Divide the data into two segments, and move the smallest element from each segment into the end of a new data segment. This can be done from top to bottom or from bottom to top. Process demonstration: !(#) !(#) ## Iterative Method #include#includeint min(int x, int y); void merge_sort(int arr[], int len); int main(){int arr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70}; int len = sizeof(arr) / sizeof(arr); merge_sort(arr, len); for(int i = 0; i<len; i++){printf("%d ", arr); }return 0; }int min(int x, int y){return x<y ? x : y; }void merge_sort(int arr[], int len){int* a = arr; int* b = (int*)malloc(len * sizeof(int)); if(b == NULL){fprintf(stderr, "Memory allocation failedn"); exit(EXIT_FAILURE); }for(int seg = 1; seg<len; seg += seg){for(int start = 0; start<len; start += seg + seg){int low = start; int mid = min(start + seg, len); int high = min(start + seg + seg, len); int k = low; int start1 = low, end1 = mid; int start2 = mid, end2 = high; while(start1<end1&&start2<end2){b[k++] = a<a ? a[start1++] : a[start2++]; }while(start1<end1){b[k++] = a[start1++]; }while(start2<end2){b[k++] = a[start2++]; }}int* temp = a; a = b; b = temp; }if(a != arr){for(int i = 0; i<len; i++){b = a; }b = a; }free(b); } ## Recursive Method #include#include#includevoid merge_sort_recursive(int arr[], int reg[], int start, int end); void merge_sort(int arr[], const int len); int main(){int arr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70}; int len = sizeof(arr) / sizeof(arr); merge_sort(arr, len); for(int i = 0; i= end)return; int mid = start + (end - start) / 2; int start1 = start, end1 = mid; int start2 = mid + 1, end2 = end; merge_sort_recursive(arr, reg, start1, end1); merge_sort_recursive(arr, reg, start2, end2); int k = start; while(start1<= end1&&start2<= end2){reg[k++] = arr<arr ? arr[start1++] : arr[start2++]; }while(start1<= end1){reg[k++] = arr[start1++]; }while(start2<= end2){reg[k++] = arr[start2++]; }memcpy(arr + start, reg + start, (end - start + 1) * sizeof(int)); }void merge_sort(int arr[], const int len){int* reg = (int*)malloc(len * sizeof(int)); if(reg == NULL){fprintf(stderr, "Memory allocation failedn"); exit(EXIT_FAILURE); }merge_sort_recursive(arr, reg, 0, len - 1); free(reg); } ### Quick Sort Randomly select an element from the interval as a pivot, place elements smaller than the pivot before it, and elements larger than the pivot after it. Then, recursively sort the sub-intervals of smaller and larger elements. Process demonstration: !(#) ## Iterative Method #includetypedef struct _Range{int start, end; }Range; Range new_Range(int s, int e){Range r; r.start = s; r.end = e; return r; }void swap(int *x, int *y){int t = *x; *x = *y; *y = t; }void quick_sort(int arr[], const int len){if(len0){Range range = r; if(range.start>= range.end)continue; int mid = arr[(range.start + range.end) / 2]; int left = range.start, right = range.end; do{while(arrmid) --right; if(left<= right){swap(&arr, &arr); left++; right--; }}while(left<= right); if(range.startleft)r[p++] = new_Range(left, range.end); }}int main(){int arr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70}; int len = sizeof(arr) / sizeof(arr); quick_sort(arr, len); for(int i = 0; i<len; i++){printf("%d ", arr); }return 0; } ## Recursive Method #includevoid swap(int *x, int *y){int t = *x; *x = *y; *y = t; }void quick_sort_recursive(int arr[], int start, int end){if(start>= end)return; int mid = arr; int left = start, right = end - 1; while(left<right){while(left<right&&arr<mid)left++; while(left= mid)right--; swap(&arr, &arr); }if(arr>= arr)swap(&arr, &arr); else left++; quick_sort_recursive(arr, start, left - 1); quick_sort_recursive(arr, left + 1, end); }void quick_sort(int arr[], int len){quick_sort_recursive(arr, 0, len - 1); }int main(){int arr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70}; int len = sizeof(arr) / sizeof(arr); quick_sort(arr, len); for(int i = 0; i<len; i++){printf("%d ", arr); }return 0; }