所以我们就需要从下往上面调~~这样就可以把它搞成一个大堆~~大堆建立完之后,就开始我们的堆排👇👇👇👇
冒泡排序是非常稳定的排序方式,而且比较容易理解👇👇👇👇👇👇
选择排序思想较为简单,就是打擂台的方法,选出最大或者最小的数字,然后排列称为升序或者降序只不过这次的选择排序,一次选出了最大数和最小数,相当于是量变~~👇👇👇👇👇👇👇、
标记起始位置和最后的位置,让最大的和end交换,最小的和begin交换。这里面的一个小bug是如果最大值在第一位,那么最大值就会先被换走。就是上面这种情况,那么我们就需要稍微做一下处理~~~~👇👇👇👇👇


论效率来说还是堆排和希尔是比较快的~~
🎄快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中 的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止~~快速排序有一些比较难以理解~我们观察一下👇👇👇👇👇👇👇
🎋快排递归版本
我们先演示一趟单趟的~~👇👇👇👇👇👇👇

✨Noitice :如果keyi给的是左边的值,就需要先从右边开始查找~~~~
如果keyi给的是右边的值,就需要从左边的值开始进行查找~
这里还需要注意一些小bug,就是越界的情况~~~~
int Partion(int* a, int left, int right)
{int keyi = left;while (left = a[keyi]){right--;}//从左边开始,找比keyi大的数,while (left}
完成这个快速排序是需要我们对它进行分区间的,也就是分治问题, 将它分为以keyi隔开的区间,逐个进行排序,这里就使用到了递归来进行~~👇👇👇👇👇👇👇👇👇👇

我们来看一下代码实现~~其实也还好👇👇👇👇👇👇
int Partion(int* a, int left, int right)
{int keyi = left;while (left = a[keyi]){right--;}//从左边开始,找比keyi大的数,while (left}void Quicksort(int* a, int left, int right)
{//左边==右边就说明递归完了,就返回~~if (left >= right){return;}int keyi = Partion(a, left, right);Quicksort(a, left, keyi - 1);Quicksort(a, keyi + 1, right);
}
Summary:递归版本省事比较简单,但是有时候递归太多就容易栈溢出,
🎋挖坑法
挖坑法就是在原来的基础上进行了改进~先设置一个坑位,先让右边的走,找到小的就停止,然后把值给到坑位。让right变成新的坑位,再让左边走,和右边类似,注意最后跳出循环,需要让最后的坑位等于key值然后返回坑位~
int Partionpit(int* a, int left, int right)
{int key = a[left];//设置的坑位int pit = left;while (left = key){right--;}a[pit] = a[right];pit = right;while (left }
🎋双指针法
int Partoinpointer(int* a, int left, int right)
{ //两个指针int key = left;int slow = left, fast = left +1;while (fast }void Quicksort(int* a, int left, int right)
{if (left >= right){return;}int keyi = Partoinpointer(a, left, right);Quicksort(a, left, keyi - 1);Quicksort(a, keyi + 1, right);
}

选key的两种情况~~
🎋 快排非递归版本
快排的递归版本我们可以想到, 但是递归的缺点就是递归的太深,容易栈溢出,如果是一组比较有序的数组,递归版本就会进行的很深~~快排非递归版本是使用到栈的思想来进行👇👇👇👇👇
void QuickSortNonR(int* a, int left, int right)
{stack st;st.push(left);st.push(right);while (!st.empty()){//开始取栈内元素int end = st.top();st.pop();int begin = st.top();st.pop();int keyi = Partionpit(a, begin, end);//处理过之后区间被分为[begin,key-1],keyi,[keyi+1,end];//被分为两个区间的选择先入右边,这样就会先处理左边~//判断是区间是否还有,有的话就继续入,或者相等就入了~~if (keyi + 1 }

🎋快排性能对比


在相对效率都较高的情况,快排还是非常稳定的~~
🎄归并排序
归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:
- 自上而下的递归(所有递归的方法都可以用迭代重写);
⭐ 算法思想:
-
申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
-
设定两个指针,最初位置分别为两个已经排序序列的起始位置;
-
比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
-
重复步骤 3 直到某一指针达到序列尾;
-
将另一序列剩下的所有元素直接复制到合并序列尾。
动图演示:

归并排序就是将区间细分,分治来达成目的~~
👇👇👇👇👇👇👇👇👇👇

void _Mergesort(int*a,int left,int right,int*tmp)
{//递归到最后一个子区间就返回&#xff0c;在返回过程中完成归并~~if (left >&#61; right){return;}int mid &#61; (left &#43; right) / 2;_Mergesort(a, left, mid, tmp);_Mergesort(a, mid &#43; 1, right, tmp);int begin1 &#61; left, end1 &#61; mid, begin2 &#61; mid &#43; 1, end2 &#61; right;int i &#61; left;while (begin1 <&#61; end1 && begin2 <&#61; end2){if (a[begin1] }void Mergesort(int *a,int n)
{int* tmp &#61; new int[n];_Mergesort(a, 0, n - 1, tmp);delete[]tmp;tmp &#61; nullptr;
}
✨性能对比



最稳定的还是希尔和归并~~·
&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;