C复习13(排序算法)

#技术笔记1.冒泡排序这个排序要能自己直接敲出来,由于每一轮有交换,导致数据就像冒泡泡一样,冒到数组的末尾,所以叫做冒泡排序。冒泡排序稳定时间复杂度O(n^2),空间复杂度O(1) (这里就给出一种代码从小到大的排序顺序冒了后面都是按从小到大的顺序排)void bubble_sort(int *arr, int len) { for (int i 0; i len; i) { bool swap_flag false; // 优化的地方 //如果已经排好序了,flag就为false直接结束了 for (int j 0; j len - i - 1; j) //优化的地方 { if (arr[j] arr[j 1]) { SWAP(arr, j, j 1); //用了个交换宏 swap_flag true; } } if (swap_flag false) { break; } arr_print(arr, len); } }2.选择排序就是划分一个已排序区和未排序区刚开始都是未排序的然后选一个最小的放入已排序区以此类推。选择排序不稳定平均时间复杂度O(n^2),空间复杂度O(1)。插入排序就是从左往右每次把当前的元素往前面已排好序的地方插入到合适的位置。插入排序稳定平均时间复杂度O(n^2),空间复杂度O(1)。希尔排序插入排序的升级版先让数组大致有序(按间隔切分子序列)再最后一次插入排序完成排序结果。希尔排序不稳定平均时间复杂度取决于增量序列,空间复杂度O(1)。3.快速排序前面C复习Day10那篇文章用的一个qsort函数(在stdlib.h中)就是快速排序函数具体代码参考源码。快速排序简而言之选一个基准分左右再递归求解基准选择好坏就关系时间复杂度了选不好容易让快排达到选择排序的效果。快速排序稳定平均时间复杂度O(nlogn),空间复杂度O(logn)。(代码如下)void parition(int arr[], int left, int right) { if (left right) { return; } //一般可以选第一个元素当枢轴位置,这里随机一个 int pivot_index (rand() % (right - left 1)) left; int pivot_value arr[pivot_index]; SWAP(arr, right, pivot_index); //跟最右边一个交换一下,然后准备从左边开始交换 int cur_l left; int cur_r right; while (cur_l cur_r) { while (cur_l cur_r arr[cur_l] pivot_value) { //说明此次不需要交换,直接继续找要交换的元素 cur_l; } if (cur_l cur_r) { arr[cur_r] arr[cur_l]; } while (cur_l cur_r arr[cur_r] pivot_value) { cur_r--; } if (cur_l cur_r) { arr[cur_l] arr[cur_r]; } } // 上述操作完成, 确定一个枢轴一定在正确的排序位置 arr[cur_l] pivot_value; parition(arr, left, cur_l - 1); //递归处理剩下的 parition(arr, cur_l 1, right); } void quick_sort(int arr[], int len) { srand(time(NULL)); //设计一个随机种子值 parition(arr, 0, len - 1); }4.归并排序归并排序就是先拆分成一个一个的元素再两两合并起来把数组一分为二一分为二一分为二直到分成一个一个再递归的把左右的一个个元素排序再将两个有序数组合并。归并排序稳定平均时间复杂度O(nlogn),空间复杂度O(n)。5.堆排序堆排序就是把数组当成完全二叉树反复从堆顶取数据进行排序建一个大根堆每次堆顶和最后一个元素交换堆大小减1再对新堆顶进行下沉判断下沉后继续判断直到恢复大根堆形态再重复此过程。堆排序不稳定平均时间复杂度O(nlogn),空间复杂度O(1)。