)
#技术笔记
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)。
