排序算法梗概（上）

一、排序基础概念稳定排序相等元素排序后相对位置不变如两个相同的 5原来谁在前排序后还在前。不稳定排序相等元素位置可能互换。时间复杂度最好 / 平均 / 最坏情况的比较与交换次数。空间复杂度是否需要额外数组原地排序 vs 非原地。二、十大经典排序速览前5个1. 冒泡排序Bubble Sort思想相邻元素两两比较大的往后 “冒”时间O (n²)空间O (1)稳定 ✅适用数据量极小、教学演示实例: #includestdio.hint main(){int n;scanf(%d,n);int arr[n];for(int i0;in;i){for(int j0;jn-1-i;j){if(arr[j]data[j1]){int temparr[j];arr[j]arr[i];arr[i]temp;}}}for(int i0;in;i){printf(%d ,arr[i]);}return 0;}2. 选择排序Selection Sort思想每次选最小 / 最大放到已排序区末尾时间O (n²)空间O (1)不稳定 ❌特点交换次数极少实例 #includestdio.hvoid selectsort(int *data,int len){int min;for(int i0;ilen;i){int mini;for(int ji;jlen;j){if(data[min]data[j]){minj;}}}if(i!min){int temparr[i];arr[i]arr[j];arr[j]temp;}}int main(){int data[]{47,35.60.95,77,15,28};int lensizeof(data)/sizeof(data[0]);insertsort(data,len);for(int i0;ilen;i){printf(%d ,data[i]);}return 0;}3. 插入排序Insertion Sort思想像打牌一样逐个插入前面有序区时间O (n²)空间O (1)稳定 ✅适用近乎有序的数据效率很高实例 #includestdio.hvoid insertsort(int* data,int len){int key;for(int i1;ilen;i){keydata[i];int ji-1;while(j0data[j]key){data[j1]data[j];j--;}data[j1]key;}}int main(){int data[]{47,35.60.95,77,15,28};int lensizeof(data)/sizeof(data[0]);insertsort(data,len);for(int i0;ilen;i){printf(%d ,data[i]);}return 0;}4. 希尔排序Shell Sort思想分组插入排序逐步缩小增量时间O (n log n) ~ O (n²)空间O (1)不稳定 ❌实例void shellsort(int *data,int len){int temp;int steplen/2;while(step1){for(int istep;ilen;i){if(dat[i]data[i-step]){tempdata[i];int ji-step;while(j0tempdata[i]){data[jstep]data[j];jj-step;}data[jstep]temp;}}stepstep/2;}}int main(){int data[]{47,35.60.95,77,15,28};int lensizeof(data)/sizeof(data[0]);insertsort(data,len);for(int i0;ilen;i){printf(%d ,data[i]);}return 0;}5. 归并排序Merge Sort思想分治 → 拆分 → 合并时间O (n log n)空间O (n)稳定 ✅适用外部排序、大数据量实例includestdio.hvoid merge(int *data,int left,int mid,int right){int temp[100];int ileft;int jmid1;int k0;while(imidjright){if(data[i]data[j]){temp[k]data[i];}else {temp[k]data[j];}}whlie(imid){temp[k]data[i];}while(jright){temp[k]data[j];}for(int t0;tk;t){data[left]temp[t];}void mergesort(int *data,int left,int right){if(leftright{int mid(leftright)/2;mergesort(data,left,right);mergesort(data,mid1,right);mergesort(data,left,mid,right);}}int main(){int data[]{47,35.60.95,77,15,28};int lensizeof(data)/sizeof(data[0]);insertsort(data,len);for(int i0;ilen;i){printf(%d ,data[i]);}return 0;}三、复杂度对比表表格排序最好平均最坏空间稳定冒泡O(n)O(n²)O(n²)O(1)是选择O(n²)O(n²)O(n²)O(1)否插入O(n)O(n²)O(n²)O(1)是希尔O(n)O(n log n)O(n²)O(1)否归并O(n log n)O(n log n)O(n log n)O(n)是