手撕各种排序（上）：https://developer.aliyun.com/article/1389400
🌙选择排序
基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。咱们看看图解：
这里我们看一个动态的图解：
上代码：
//选择排序测试 void SelectSort(int* a, int n) { //初始化第一个元素 和 最后一个元素 int begin = 0; int end = n - 1; while (begin < end) { //选出最大值和最小值 int mini = begin, maxi = begin; for (int i = begin + 1; i <= end; i++) { if (a[i] > a[maxi]) { maxi = i; } if (a[i] < a[mini]) { mini = i; } } //最小值和最初的元素交换 Swap(&a[begin], &a[mini]); //如果max被换走就需要重新赋值 if (maxi == begin) { maxi = mini; } //最大值和最末的元素交换 Swap(&a[end], &a[maxi]); ++begin; --end; } }
注意事项：
💦1.这里先找到最小值和最大值，然后交换到最前面和最后面，一次进行。
💦2. 如果最大值被交换后，需要从新赋值。
时间复杂度：O(N²)
空间复杂度：O(1)
稳定性：不稳定
复杂性：简单
🌙堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。咱们看看图解：
再看看动态的图解：
上代码：
//堆排序测试 //实现向下调整建大堆 void AdjustDown(int* a, int n, int parent) { //孩子和父亲的关系 int child = parent * 2 + 1; while (child < n) { //找出小的那个孩子 if (child + 1 < n && a[child + 1] < a[child]) { ++child; } //实现向下调整元素 if (a[child] < a[parent]) { //元素交换 Swap(&a[child], &a[parent]); // 继续往下调整 parent = child; child = parent * 2 + 1; } else { break; } } } //堆排序测试 void HeapSort(int* a, int n) { //向下调整建堆 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { //实现向下调整建大堆 AdjustDown(a, n, i); } int end = n - 1; while (end > 0) { //元素交换 Swap(&a[0], &a[end]); //实现向下调整建大堆 AdjustDown(a, end, 0); --end; } }
注意事项：
💦1.首先我们需要建大堆（以在二叉树讲解咯），交换，再建大堆
💦2. 每交换一个元素都需要再建一次大堆。
时间复杂度：O(NlogN)
空间复杂度：O(1)
稳定性：不稳定
复杂性：复杂
🌙快排
在快排这个板块中我将讲述四个方法，希小伙伴都能掌握。
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
💫Hoare方法
在动态图中，key称为基准值，默认把基准值定义在数组的首元素上，其次为了加快遍历的速度，需要用到两个变量分别去对应数组的首尾部分，L处在数列的首部，它需要从左往右寻找比Keyi位置的值大的，遇到后就停下来，没遇到就一直走；R处在数列的尾部，它需要从右往左去寻找比keyi位置的值小的，也是遇到后就停下来，没遇到就一直走。
当L与R都遇到停下来后开始互换位置，然后继续遍历，直到L==R时，双方都不会再走了，因为它们走到了同一个位置，这个位置被称为它俩的相遇点，之后便需要将keyi位置的值与相遇点的值互换位置，这样keyi位置的值就放到了中间，成为了数组的中心——基准值，它意味着将数组分为两个子序列，左序列全是小于Keyi的值，右序列全是大于Keyi的值，这样便可以利用递归，一层一层再对左右两个子序列进行相同的步骤——将一个大的无序序列转化为多个小的序列，从而进行排序，最终排列为完全有序的序列。
上代码：
//三数取中 （找出中间值） int GetMidi(int* a, int left, int right) { //中间值 int mid = (left + right) / 2; //三个数比较找出中间值 if (a[left] < a[mid]) { if (a[mid] < a[right]) { return mid; } else if (a[left] > a[right]) { return left; } else { return right; } } else { if (a[mid] > a[right]) { return mid; } else if (a[left] < a[right]) { return left; } else { return right; } } } // 右边找小，左边找大，交换，把左边的值跟a[keyi]交换 int PartSort1(int* a, int left, int right) { //找中间值（相对） int midi = GetMidi(a, left, right); //把最左边（相对）跟中间值（相对）换 Swap(&a[left], &a[midi]); //定位最左边（相对） int keyi = left; while (left < right) { //找小 while (left < right && a[right] >= a[keyi]) { --right; } //找大 while (left < right && a[left] <= a[keyi]) { ++left; } //左右交换 Swap(&a[left], &a[right]); } //此时左边走到中间了，开始交换 Swap(&a[keyi], &a[left]); //返回 return left; };
注意事项：
💦1.首先先找到中间值。
💦2.再和最左边元素互换
💦3.左边找比（中间值）大的数，右边找（中间值）小的数，然后左右值交换。
💦4.此时左边走到中间了，开始交换
💦5.上述进行循环，知道排序完成
💫挖坑法
大家就看一下下面图解：
//三数取中 （找出中间值） int GetMidi(int* a, int left, int right) { //中间值 int mid = (left + right) / 2; //三个数比较找出中间值 if (a[left] < a[mid]) { if (a[mid] < a[right]) { return mid; } else if (a[left] > a[right]) { return left; } else { return right; } } else { if (a[mid] > a[right]) { return mid; } else if (a[left] < a[right]) { return left; } else { return right; } } } //挖坑法 int PartSort2(int* a, int left, int right) { //找中间值（相对） int midi = GetMidi(a, left, right); //把最左边（相对）跟中间值（相对）换 Swap(&a[left], &a[midi]); //定位最左边（相对） int key = a[left]; //保存key值以后，左边形成第一个坑 int hole = left; while (left < right) { //右边先走，找小，填到左边的坑，右边形成新的坑位 while (left < right && a[right] >= key) { --right; } a[hole] = a[right]; hole = right; //左边再走，找大，填到右边的坑，左边形成新的坑位 while (left < right && a[left] <= key) { ++left; } a[hole] = a[left]; hole = left; } a[hole] = key; return hole; }
💫前后指针
通过创建两个指针，prev指针指向数组序列首元素位置，cur指向prev的下一个位置，cur通过遍历去寻找比key基准值小的，若找到了，还得看prev的下一个位置是否为cur所处的位置，若prev的下一个位置确实为cur所处位置，则将cur指向的值与prev指向的值进行互换，若prev的下一个位置不是cur所处位置，则cur继续往后遍历，直到cur遍历结束，最后要将key基准值与prev指向的值进行互换，最终确认基准值处于数组序列的中间位置。
//三数取中 （找出中间值） int GetMidi(int* a, int left, int right) { //中间值 int mid = (left + right) / 2; //三个数比较找出中间值 if (a[left] < a[mid]) { if (a[mid] < a[right]) { return mid; } else if (a[left] > a[right]) { return left; } else { return right; } } else { if (a[mid] > a[right]) { return mid; } else if (a[left] < a[right]) { return left; } else { return right; } } } //前后指针 int PartSort3(int* a, int left, int right) { //找中间值（相对） int midi = GetMidi(a, left, right); //把最左边（相对）跟中间值（相对）换 Swap(&a[left], &a[midi]); //定义指针开头 int prev = left; //定义指针开头后一个 int cur = prev + 1; int keyi = left; while (cur <= right) { if (a[cur] < a[keyi] && ++prev != cur) { Swap(&a[prev], &a[cur]); } ++cur; } //交换 Swap(&a[prev], &a[keyi]); return prev; }
💫快排非递归
1.初始化我们的栈。
2.入栈把我们的开始的left==0 right==n-1；
3.进入我们的循环体循环体进入的条件是判断栈中是否还有数值如果有数值的化什么其中的数值对应的范围还是没有序的就需要出栈（这个时候就需要进行出栈（注意栈的数值的左右范围的对应））进行我们的挖坑排序（对于挖坑我们应该把key返回出来通过key的数值进行我们再一次的入栈操作同时我们的范围）。
3.1[left key-1] 和[key+1 right] 这样的范围满足条件才能继续push 之后pop进行我们的排序；
4如果说我们的循环体结束了的话我们的数组就一定有序！
前面已经讲述了栈，这里就不再实现栈了
//快排非递归（采用栈的形式）（先进后出） void QuickSortNonR(int* a, int begin, int end) { //定义 ST st; //初始化 STInit(&st); //添加元素 STPush(&st, end); STPush(&st, begin); while (!STEmpty(&st)) { //剥离元素 让left取先入但是后出的元素（区间的左边） int left = STTop(&st); STPop(&st); //让right取栈顶元素（是我们后入的区间的右边） int right = STTop(&st); STPop(&st); // 右边找小，左边找大，交换，把左边的值跟a[keyi]交换 int keyi = PartSort1(a, left, right); //分割成段 // [lefy,keyi-1] keyi [keyi+1, right] if (keyi + 1 < right) { //添加元素 STPush(&st, right); STPush(&st, keyi + 1); } if (left < keyi - 1) { //添加元素 STPush(&st, keyi - 1); STPush(&st, left); } } //销毁 STDestroy(&st); }
