定制做网站技术,哈尔滨工程研究生招生信息网,建设部网站官网挂证通报,汕头建总目录 一、快速排序1.1 递归1.2 非递归 二、归并排序2.1 递归2.2 非递归 一、快速排序
1.1 递归
快速排序的递归采用二叉树的前序遍历的思路#xff0c;单趟排序先确定好一个元素的位置#xff0c;然后往后递归再确定其他子区域内的某个元素的位置#xff0c;直到只有一个元… 目录 一、快速排序1.1 递归1.2 非递归 二、归并排序2.1 递归2.2 非递归 一、快速排序
1.1 递归
快速排序的递归采用二叉树的前序遍历的思路单趟排序先确定好一个元素的位置然后往后递归再确定其他子区域内的某个元素的位置直到只有一个元素返回。
递归的图示 代码
void QuickSort(int* a, int begin, int end)
{//区间内小于等于1就返回if (begin end){return;}//单趟排序返回确定位置好的元素下标int ki partsort1(a, begin, end);//递归 - 区间[begin, ki-1][ki1, end]QuickSort(a, begin, ki - 1);QuickSort(a, ki 1, end);
}接下来分析单趟排序的实现。有3种方式Hoare法、挖坑法、前后指针法。
1️⃣Hoare法 整体思路
通过三数取中获取较靠中间元素的下标mid然后mid指向的元素与左端的元素进行交换防止极端情况定义一个变量 ki left 便于记录左端的值注意ki是下标先移动右边再移动左边right指向的元素大于等于ki指向的元素就减1往前走小于就停下left指向的元素小于等于ki指向的元素就1往后走大于就停下然后两者停下分别指向的元素进行交换然后先走右再走左继续移动left与right相遇跳出循环交换ki指向的元素和left指向的元素此时left指向的元素就是确定好位置的元素最后返回下标left
图示 代码
//Hoare法
int partsort1(int* a, int left, int right)
{//获取较中间的元素的下标int mid getmid(a, left, right);//三数取中Swap(a[left], a[mid]);//与左端交换防止极端情况int ki left;//注意ki得到的是下标while (left right){//先走右再走左while (left right a[right] a[ki])//是大于等于往前走小于就停下{ // 防止走的过程中越界right--;}while (left right a[left] a[ki])//是小于等于往前走大于就停下{ // 防止走的过程中越界left;}Swap(a[left], a[right]);//交换两个元素}Swap(a[ki], a[left]);//把ki指向的元素交换到它最终的位置return left;//返回确定位置的元素的下标
}问题1为什么要三数取中 因为三数取中可以防止出现极端情况该极端情况指ki指向的元素本来就应该放在左端比如
如果大部分是这种最坏情况导致快速排序的复杂度为O(N ^ 2)
三数取中可以取到较靠中间位置的元素的下标尽可能避免了以上情况就算有个别还是在最左端但是对整体的效率并没有多大影响。所以三数取中对快速排序的优化有很大的帮助。
代码
//三数取中
int getmid(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[right] a[left])return left;elsereturn right;}else{if (a[mid] a[right])return mid;else if (a[right] a[left])return left;elsereturn right;}
}问题2为什么ki取的是下标不是数组元素 这与最后确定元素位置的交换有关假设ki是数组元素交换的是left指向的元素和ki那么结果是left指向的元素变成了ki这个元素但是数组左端的元素依旧没变。 ki取的是下标才能真正交换数组左端和left指向的元素。 问题3为什么先走右边再走左边 举个栗子 2️⃣挖坑法
整体思路
三数取中与Hoare法的步骤一样ki取的是left指向的元素为后面的填坑作准备定义一个坑hole left 是下标先走右边停下后将此时right指向的元素覆盖坑位的元素然后产生新的坑位right变成坑再走左边停下后将此时left指向的元素覆盖坑位的元素然后产生新的坑位left变成坑循环全部走完后最终的hole就是ki要确定的位置覆盖坑位然后返回hole
图示 代码
//挖坑法
int partsort2(int* a, int left, int right)
{//获取较中间的元素的下标int mid getmid(a, left, right);//三数取中Swap(a[left], a[mid]);//与左端交换防止极端情况int ki a[left];//注意ki得到的是数组元素int hole left;//初始的坑的位置while (left right){//先走右再走左while (left right a[right] ki)//是大于等于往前走小于就停下{ // 防止走的过程中越界right--;}a[hole] a[right];//覆盖坑位的元素hole right;//产生新的坑位while (left right a[left] ki)//是小于等于往前走大于就停下{ // 防止走的过程中越界left;}a[hole] a[left];//覆盖坑位的元素hole left;//产生新的坑位}a[hole] ki;//确定元素的位置return hole; //返回确定位置的元素的下标
}3️⃣前后指针法
通过前面的两种方法可以发现确定好某个元素的位置后该元素的左右两个区间分别是小于这个元素和大于这个元素以数组是1,2,3,4,5,6,7,8,9,10为例也就是说要确定位置的元素是区分两个不同区间的标杆所以这里可以使用前后指针法用来区分两块区域。
整体思路
定义前后指针curleft1pre left如果cur指向的元素小于等于ki指向的元素pre先加1再交换pre和cur分别指向的元素然后curcur循环完交换pre和ki分别指向的元素pre的位置就是确定好的位置然后返回pre
图示 代码
//前后指针法
int partsort3(int* a, int left, int right)
{int mid getmid(a, left, right);//三数取中Swap(a[left], a[mid]);//与左端交换防止极端情况int ki left;//注意ki得到的是下标int cur left 1, pre left;//定义前后指针while (cur right)//范围限制{if (a[cur] a[ki])//如果小于先pre再交换分别指向的元素{Swap(a[pre], a[cur]);}cur;//cur都要往后走}Swap(a[ki], a[pre]);//把ki指向的元素交换到它最终的位置return pre;//返回确定位置的元素的下标
}1.2 非递归
快速排序的非递归是用栈模拟递归来实现的栈的特点是后进先出递归是先左边再右边的所以放入栈的数据应该先放右再放左这样取数据才是先左再右。
图示 代码
//快速排序 - 非递归
void QuickSortNoR(int* a, int begin, int end)
{stackint st;//定义一个栈st.push(end);//先放右st.push(begin);//再放左while (!st.empty())//不为空进入循环{int left st.top();//取左值st.pop();//删除栈顶元素int right st.top();//取右值st.pop();//删除栈元素int ki partsort3(a, left, right);//一趟排序确定某个元素的位置返回该位置if (ki 1 right)//整体先放右{st.push(right);//里面先放右st.push(ki 1);//里面再放左}if (left ki - 1)//整体再放左{st.push(ki - 1);//里面先放右st.push(left);//里面再放左}}
}快速排序特性总结
时间复杂度O(N * logN)空间复杂度O(logN)不稳定
二、归并排序
2.1 递归
归并排序的递归采用二叉树的后序遍历的思想先分解成小块区间然后再合并两个小块空间的同时将这两块子区间的元素进行排序。依次类推。这里还要额外开辟一块临时空间用来对两个子区间排序在临时空间排完序后然后把已经排序的元素的拷贝到原数组对应的位置最终将整个数组排完序。
图示
代码
//归并排序-递归
void MergeSort(int* a, int* tmp, int begin, int end)
{//区间内元素个数小于等于1返回if (begin end){return;}int mid (begin end) / 2;//取划分区域的下标MergeSort(a, tmp, begin, mid);//递归左边MergeSort(a, tmp, mid 1, end);//递归右边int begin1 begin, end1 mid;//合并的第一块小区间int begin2 mid 1, end2 end;//合并的第二块小区间int k begin;//注意k为begin当前区域的初始位置while (begin1 end1 begin2 end2){ // 谁小谁先放入tmpif (a[begin1] a[begin2]){tmp[k] a[begin1];}else{tmp[k] a[begin2];}}// 哪块小区间有剩余直接放入tmpwhile (begin1 end1){tmp[k] a[begin1];}while (begin2 end2){tmp[k] a[begin2];}//最后拷贝到原数组对应的位置完成排序memcpy(a begin, tmp begin, sizeof(int) * (end2 - begin 1));
}2.2 非递归
归并排序的非递归也是模拟递归的过程只是没有递只有归即只有合并的过程用for循环控制合并区间的大小和范围即可也要借助临时空间来排序最后拷贝给原数组。
图示 代码
//归并排序-非递归
void MergeSortNoR(int* a, int* tmp, int n)
{int gap 1;//初始合并的子区间大小while (gap n)//范围{for (int i 0; i n; i gap * 2){int begin1 i, end1 i gap - 1;//合并的第一块小区间int begin2 i gap, end2 i gap * 2 - 1;//合并的第二块小区间int k i;if (begin2 n)//只有第一块小区间没有第二块小区间{break;//不能合并跳出}if (end2 n)//第二块小区间个数较少但是不影响合并{end2 n - 1;//修改end2的值}while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[k] a[begin1];}else{tmp[k] a[begin2];}}while (begin1 end1){tmp[k] a[begin1];}while (begin2 end2){tmp[k] a[begin2];}memcpy(a i, tmp i, sizeof(int) * (end2 - i 1));//排序拷贝回原数组}gap * 2;//区间增大}
}注意 上面的代码有两个特殊处理用于非2的次方个元素的数组如果begin2大于等于n说明要合并的两个子区间仅仅只有第一块小区间没有第二块小区间这时就不需要合并了第一块小区间在之前已经合并为有序。如果end2大于等于n第二块小区间还是存在的只是元素个数少些这时就把end2的指向的位置该成第二块小区间内最后一个元素的位置即可。 归并排序特性总结
归并排序要额外开辟一块空间用来处理排序的问题时间复杂度O(N * logN)空间复杂度O(N)稳定
