论效率来说还是堆排和希尔是比较快的~~

&＃x1f384;快速排序

 &＃x1f38b;快排递归版本

我们先演示一趟单趟的~~&＃x1f447;&＃x1f447;&＃x1f447;&＃x1f447;&＃x1f447;&＃x1f447;&＃x1f447;

✨Noitice &＃xff1a;如果keyi给的是左边的值&＃xff0c;就需要先从右边开始查找~~~~

                      如果keyi给的是右边的值&＃xff0c;就需要从左边的值开始进行查找~

                       这里还需要注意一些小bug&＃xff0c;就是越界的情况~~~~

int Partion(int* a, int left, int right)
{int keyi &＃61; left;while (left &＃61; a[keyi]){right--;}//从左边开始,找比keyi大的数&＃xff0c;while (left}

     完成这个快速排序是需要我们对它进行分区间的&＃xff0c;也就是分治问题&＃xff0c; 将它分为以keyi隔开的区间&＃xff0c;逐个进行排序&＃xff0c;这里就使用到了递归来进行~~&＃x1f447;&＃x1f447;&＃x1f447;&＃x1f447;&＃x1f447;&＃x1f447;&＃x1f447;&＃x1f447;&＃x1f447;&＃x1f447;

 我们来看一下代码实现~~其实也还好&＃x1f447;&＃x1f447;&＃x1f447;&＃x1f447;&＃x1f447;&＃x1f447;

int Partion(int* a, int left, int right)
{int keyi &＃61; left;while (left &＃61; a[keyi]){right--;}//从左边开始,找比keyi大的数&＃xff0c;while (left}void Quicksort(int* a, int left, int right)
{//左边&＃61;&＃61;右边就说明递归完了&＃xff0c;就返回~~if (left >&＃61; right){return;}int keyi &＃61; Partion(a, left, right);Quicksort(a, left, keyi - 1);Quicksort(a, keyi &＃43; 1, right);
}

 Summary&＃xff1a;递归版本省事比较简单&＃xff0c;但是有时候递归太多就容易栈溢出&＃xff0c;

&＃x1f38b;挖坑法

      挖坑法就是在原来的基础上进行了改进~先设置一个坑位&＃xff0c;先让右边的走&＃xff0c;找到小的就停止&＃xff0c;然后把值给到坑位。让right变成新的坑位&＃xff0c;再让左边走&＃xff0c;和右边类似&＃xff0c;注意最后跳出循环&＃xff0c;需要让最后的坑位等于key值然后返回坑位~

int Partionpit(int* a, int left, int right)
{int key &＃61; a[left];//设置的坑位int pit &＃61; left;while (left &＃61; key){right--;}a[pit] &＃61; a[right];pit &＃61; right;while (left }

&＃x1f38b;双指针法

int Partoinpointer(int* a, int left, int right)
{ //两个指针int key &＃61; left;int slow &＃61; left, fast &＃61; left &＃43;1;while (fast }void Quicksort(int* a, int left, int right)
{if (left >&＃61; right){return;}int keyi &＃61; Partoinpointer(a, left, right);Quicksort(a, left, keyi - 1);Quicksort(a, keyi &＃43; 1, right);
}

选key的两种情况~~ 

 &＃x1f38b; 快排非递归版本

    快排的递归版本我们可以想到&＃xff0c; 但是递归的缺点就是递归的太深&＃xff0c;容易栈溢出&＃xff0c;如果是一组比较有序的数组&＃xff0c;递归版本就会进行的很深~~快排非递归版本是使用到栈的思想来进行&＃x1f447;&＃x1f447;&＃x1f447;&＃x1f447;&＃x1f447;

void QuickSortNonR(int* a, int left, int right)
{stack st;st.push(left);st.push(right);while (!st.empty()){//开始取栈内元素int end &＃61; st.top();st.pop();int begin &＃61; st.top();st.pop();int keyi &＃61; Partionpit(a, begin, end);//处理过之后区间被分为[begin,key-1],keyi,[keyi&＃43;1,end];//被分为两个区间的选择先入右边&＃xff0c;这样就会先处理左边~//判断是区间是否还有&＃xff0c;有的话就继续入&＃xff0c;或者相等就入了~~if (keyi &＃43; 1 }

&＃x1f38b;快排性能对比

 在相对效率都较高的情况&＃xff0c;快排还是非常稳定的~~

&＃x1f384;归并排序

    归并排序&＃xff08;Merge sort&＃xff09;是建立在归并操作上的一种有效的排序算法。该算法是采用分治法&＃xff08;Divide and Conquer&＃xff09;的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用&＃xff0c;归并排序的实现由两种方法&＃xff1a;

• 自上而下的递归&＃xff08;所有递归的方法都可以用迭代重写&＃xff09;&＃xff1b;

⭐ 算法思想&＃xff1a;

1. 申请空间&＃xff0c;使其大小为两个已经排序序列之和&＃xff0c;该空间用来存放合并后的序列&＃xff1b;

2. 设定两个指针&＃xff0c;最初位置分别为两个已经排序序列的起始位置&＃xff1b;

3. 比较两个指针所指向的元素&＃xff0c;选择相对小的元素放入到合并空间&＃xff0c;并移动指针到下一位置&＃xff1b;

4. 重复步骤 3 直到某一指针达到序列尾&＃xff1b;

5. 将另一序列剩下的所有元素直接复制到合并序列尾。

动图演示&＃xff1a;

     归并排序就是将区间细分&＃xff0c;分治来达成目的~~

&＃x1f447;&＃x1f447;&＃x1f447;&＃x1f447;&＃x1f447;&＃x1f447;&＃x1f447;&＃x1f447;&＃x1f447;&＃x1f447;

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;