NlogN经典排序算法的实现-希尔排序，快速排序，归并排序.zip

# calsort NlogN经典排序算法的实现——希尔排序，快速排序，归并排序 # 迭代 ## 1.冒泡排序 对于长为n的一维数组，对i位这个位置，与`i+1~n`做 n-1-i 次冒泡比较，每一个完整的j循环计较使一个较大的数（泡泡）被交换（浮动）到较靠后的位置 ## 2.插入排序与哈希排序 （以升序为标准） > O（N^2）插入排序：从0位开始构建有序前列，后项新元素`在前列遍历，冒泡`，找到插入位置。 > > O(NlogN )插入的二分优化：将新元素插入有序前列中，可以`二分搜索`搜寻target位置。 > O(NlogN) 哈希基于伸长量对`[i]`与`[i+h]`隔项冒泡进行使数组部分有序。缩小增量重复操作提高精度，至增量为1时，已相当有序 哈希:  # 分治 > 分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法。二分递归模型 ## 1.快速排序 O(nlogn)——O（n^2） ### 思路 ```c++ /*基于分治，递归 挖坑填数：在一个区间选取基数，将其余数按事件顺序分到基数左右侧，对左右区间重复此操作。 itl，itr双下标，while（itl<itr）{移右小数填左，移左大数填右，迭代下标} then itl==itr ，此时填基数，成功分治出比基数大和小的两个区间 以左区间首位为新基数重复 思考子区间的起终点 */ ``` > 核心论点是子区间的始终点 > > 左区间是 ·0 to mid· 而是 ·i to mid· ，右区间不是 ·mid to n-1· 而是·mid to j· > 当做左快排的子右快排，和右快排的子左快排时，i，j与 0，n-1 出现差异 * 迭代填坑前，用`哨兵ij`保存此区间起点终点，用以传递给子递归的`迭代itlr` int i = itl; int j = itr; > i j迭代表如图 > > 样本数据`int a[] = {5,3,1,7,9,2,4,6,8};`  ### 源码 ~~~c++ #include<iostream> #include<windows.h> using namespace std; void quicksort(int* arr, int itl, int itr,int n) { if (itl >= itr) return; // cout << itl << " " << itr << " " << endl; int pop = arr[itl]; int moving = 2;//1左2右 //此处需要保存区间初始下标 int i = itl; int j = itr; while (itl < itr) { if (moving == 2) { if (arr[itr] < pop) { arr[itl++] = arr[itr]; moving = 1; continue; } else itr--; } if (moving == 1) { if (arr[itl] > pop) { arr[itr--] = arr[itl]; moving = 2; continue; } else itl++; } } if (itl == itr) { arr[itl] = pop; } //左区间是 ·0 to mid· 而是 ·i to mid· ，右区间不是 ·mid to n-1· 而是·mid to j· //做左快排的子右快排，和右快排的子左快排时，ij与0n 出现差异 quicksort(arr, i, itl-1,n); quicksort(arr, itr + 1, j, n); return; } //递归入口 void quicksort(int* arr, int n) { if (n < 2) return; int itl = 0, itr = n - 1; quicksort(arr, itl, itr, n); return; } int main() { int n; cin >> n; int* a = new int[n]; for (int i = 0; i < n; i++) { a[i] = n - i-1; } /*int a[] = {5,3,1,7,9,2,4,6,8};*/ quicksort(a,n); for (int i = 0; i < n; i++) { cout << a[i]<<" "; } } ~~~ > 可以感觉到二叉树结构 如果我们把数组的切分看做是一个树，那么上图就是它的最优情况的图示，共切分了logn次，所以，最优情况下快 速排序的时间复杂度为O(nlogn); 最坏情况：每一次切分选择的基准数字是当前序列中最大数或者最小数，这使得每次切分都会有一个子组，那么总 共就得切分n次，所以，最坏情况下，快速排序的时间复杂度为O(n^2); <img src="https://s2.loli.net/2022/08/03/rq6g4Oc927kv3JC.png" alt="image-20220803221809752" style="zoom: 25%;" /> <img src="https://s2.loli.net/2022/08/03/LqId7mvjfFH2gQZ.png" al="image-20220803221858920" style="zoom:25%;" /> ## 2.归并排序 > 快排：粗治细分，递归往复。归并：先分后治 > 时间复杂度`O（NlogN）`，空间复杂度`O(N)` ### 思路 ~~~c++ /*把数组二分拆解为二叉树结构 自顶向下方法 depart递归分划 所谓拆解，值的是二叉树式记录索引下标 我们可以用 left mid right 来表示两个一段序列，它可以按l-m-r拆为两个子树，当l==mid ,mid+1==r时，得到一对最短有序区间，当l==r时，递归越界return掉。 merge递归治理 再将兄弟最小子树升序归并，得到有序子树， 兄弟有序子树间再归并，辗转升序插入兄弟有序子树 需要等长辅助数组，取其部分长区间用以插排a的两个短有序区间*/ ~~~  ### 原码 ```c++ void msort(int *a,int n); void depart(int *a,int *b,int left , int right); void merge(int* a,int *b, int left, int mid, int right); int main() { int n; cin >> n; int* a = new int[n]; for (int i = 0; i < n; i++) { a[i] = n - i - 1; } msort(a, n); for (int i = 0; i < n; i++) { cout << a[i] << " "; } delete[] a; return 0; } void msort(int* a, int n) { if (n < 3) return; int* b = new int[n]; for (int i = 0; i < n; i++) b[i] = -1; depart(a, b,0, n - 1); delete[] b; } //这样写的递归结构就不是很清晰 void depart(int* a, int* b, int left, int right) { if (left >= right) return; int mid = (left + right) / 2; depart(a, b, left, mid); depart(a, b, mid + 1, right); merge(a, b, left, mid, right); } void merge(int* a, int* b, int left, int mid, int right) { int index = left; int itl = left; int itr = mid+1; while (itl <= mid && itr <= right) { //mute算法有bug，跳过阅读再回望 if (a[itl] < a[itr]) { //if (itl <= mid) b[index++] = a[itl++]; // else // b[index++] = a[itr++]; } else { //if (itr < right) b[index++] = a[itr++]; // else // b[index++] = a[itl++]; } } //以上方法会有剩余元素：只要一方迭代器走到底以上循环就应退出。哪个半区有剩余不可能同时成立。 //所以，采取分离方法，迭代填入 while (itl <= mid) b[index++] = a[itl++]; while (itr <= right) b[index++] = a[itr++]; for (int i = left; i <= right; i++) { a[i] = b[i]; } return; } ``` ### 探讨一，递归结构设计 ~~~c++ void depart(int* a, int* b, int left, int right) { if (left >= right) return; int mid = (left + right) / 2; depart(a, b, left, mid); depart(a, b, mid + 1, right); merge(a, b, left, mid, right); } ~~~ ~~~c++ void depart(int* a, int* b, int left, int right) { if (left < rihht) { int mid = (left + right) / 2; depart(a, b, left, mid); depart(a, b, mid + 1, right); merge(a, b, left, mid, right); } else return; } ~~~ 谁的逻辑更好呢？我偏向2nd ### 探讨二，归并双短有序列表方法 ~~~c++ //以下为bug算法，it下标溢出情况下干扰 if (a[itl] < a[itr]) 判断 else语句没法耦合在while算法中 while (index <= right) { if (a[itl] < a[itr]) { //插完边的树后，该it指针已经越界，会影响上文if判断，所以，对于已经插完一遍树的情况，我们选择退出当前算法，用下文while补项。 if (itl <= mid) b[index++] = a[itl++]; else b[index++] = a[itr++]; } else { if (itr < right) b[index++] = a[itr++]; else b[index++] = a[itl++]; } } ~~~ ~~~c++ //对策：解耦，先做双列插排直至一方遍历，再补项 while (itl <= mid && itr <= right) { if (a[itl] < a[itr]) b[index++] = a[itl++]; else b[index++] = a[itr++]; } while (itl <= mid) b[index++] = a[itl++]; while (itr <= right) b[index++] = a[itr++]; ~~~ ### 探讨三.a数组更新时机 > `merge`算法下我们使`left`到`right`区