04数据结构

冒泡排序 : 两两比较

逻辑 : 给数组中的元素做两两比较,从首个元素开始,小的排前,大的排后,依次两两比较,比完整组后,元素做比较的次数减一,再循环此过程直到比

#include <stdio.h> void printArray(int* arr,int length) { //判断数组中是否有元素 if (length == 0) { printf("arr:[]\n"); return; }//有元素-开始打印 printf("["); for (int i = 0; i < length; i++) { printf("%d",arr[i]); if (i == length - 1) { printf("]\n"); } else { printf(", "); } } } void bubbleSort(int* arr,int length) { //第一次冒泡排序,次数是长度减一 for (size_t j = 0; j < length - 1; j++) { //每此循环减一次长度,每次循环大数都往后挪 for (size_t i = 0; i < length - 1 -j ; i++) { if (arr[i] > arr[i+1]) { int temp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = temp; } } } } int main() { int arr[] = {1,2,3,4,5,6,7,8,9}; printArray(arr,9); bubbleSort(arr,9); printArray(arr,9); return 0; }

快速排序 : 每次做基准数归位

基准数 : 通常定义序列的第一个元素作为基准数,数组中第二个元素[start]开始往后找比基准数大的数找到停止,最后数组中一个元素[end]开始往前找比基准数小的数,找到停止,特殊情况start和end没相遇时,看end最后停的位置,找到位置后交换基准数完成归位操作

完成基准数归位操作后,对序列做分割,基准数前的为前序列,后的为后序列,并对每个前后序列再次做基准数归位,前序列的索引范围结束索引减一, 后序列的索引范围起始索引加一

快速排序具有二分性,每此归为基准数都将序列一分为二,随着每次一分为二索引的数据规模呈指数级减小

#include <stdio.h> void printArray(int *arr, int length) { if (length == 0) { printf("arr : []\n"); } printf("["); for (int i = 0; i < length; i++) { printf("%d", arr[i]); if (i == length - 1) { printf("]\n"); return; } else { printf(", "); } } } void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } void quickSort(int *arr, int start, int end) { // 出口 if (start >= end) { return; } // 写规律 int low = start; int high = end + 1; while (1) { while (low < end) { low++; if (arr[low] > arr[start]) { break; } } while (high > start) { high--; if (arr[high] < arr[start]) { break; } // 走到这里说明arr[low]>[high],arr[high]<arr[low],需要分别交换指向的元素 // 大前提 : low和high都停下,且low比high小,说明没找到基准数的位置 } if (low < high) { swap(&arr[low], &arr[high]); } else { // 说明low和high没越过 break; } } // 从循环出来说明基准书的位置找到了 // 交换基准数和相遇位置 // 基准数归为操作 swap(&arr[start], &arr[high]); // 升序要和high交换位置[high找小数],降序要和low[low找大] // 递归代码 quickSort(arr, start, high - 1); quickSort(arr, high + 1, end); } int main() { int arr[] = {123, 456, 879, 521, 654, 4, 154, 5, 8541}; int length = sizeof(arr) / sizeof(arr[0]); quickSort(arr, 0, length - 1); printArray(arr, length); printf("%d\n", length); return 0; }