庆阳市住房和城乡建设局网站,重庆网站seo多少钱,免费小程序模板,网站建设开发用什么软件创作不易#xff0c;友友们给个三连吧#xff01;#xff01;
一、堆排序
堆排序已经在博主关于堆的实现过程中详细的讲过了#xff0c;大家可以直接去看#xff0c;很详细,这边不介绍了
DS#xff1a;二叉树的顺序结构及堆的实现-CSDN博客
直接上代码#xff1a; … 创作不易友友们给个三连吧
一、堆排序
堆排序已经在博主关于堆的实现过程中详细的讲过了大家可以直接去看很详细,这边不介绍了
DS二叉树的顺序结构及堆的实现-CSDN博客
直接上代码
void AdjustDown(int* a, int n, int parent)//升序要建大堆
{int child parent * 2 1;//假设左孩子比右孩子大while (child n){//如果假设错误就认错if (child 1 n a[child] a[child 1])child;//如果孩子大于父亲交换if (a[child] a[parent]){Swap(a[child], a[parent]);//交换完后让原来的孩子变成父亲然后再去找新的孩子parent child;child parent * 2 1;}elsebreak;}
}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--;}
}
建堆的时间复杂度是oN排序的时间复杂度是N*logN所以堆排序的总时间复杂度是N*logN
二、冒泡排序
2.1 思想 基本思想所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。 2.2 冒泡排序的实现
方法从前往后逐一比较相邻元素前面的大于或小于后面的则进行交换每一轮将当前轮最大或最小的元素冒泡到当前论的最后。重复上述过程最后就是有序的。
该排序比较简单不画图了不懂得可以看看博主之前写的文章有介绍
C语言深入理解指针(2)-CSDN博客
代码实现
void BubbleSort(int* a, int n)
{for (int i 0; i n - 1; i)//每一趟拍好一个最后排完n-1个最后一个数就没必要比了{for (int j 0; j n - i - 1; j)//第一趟需要比较的n-1次第二次需要比较n-2次……//所以结束条件跟着i变化{if (a[j] a[j 1])Swap(a[j], a[j 1]);}}
}
2.3 冒泡排序的改进
如果比较的过程中比到中间的时候就有序了但是我们并不知道这个时候一直到后面进行的比较都是无效的所以为了优化这个情况我们设置一个标志如果一趟排序中没有发生交换说明后面都有序了这个时候就停止冒泡排序
void BubbleSort(int* a, int n)
{for (int i 0; i n - 1; i)//每一趟拍好一个最后排完n-1个最后一个数就没必要比了{int flag 1;//假设有序for (int j 0; j n - i - 1; j)//第一趟需要比较的n-1次第二次需要比较n-2次……//所以结束条件跟着i变化{if (a[j] a[j 1]){Swap(a[j], a[j 1]);flag 0;//如果没有发生交换说明不符合有序}}if (flag 1)break;}
}
2.4 复杂度分析
时间复杂度O(N^2)
空间复杂度O(1)
三、快速排序
3.1 思想 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法 其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。 根据区间按照基准值划分的过程有最早的hoare版本包括后来深入研究之后的挖坑法、前后指针法、快排法、非递归法……以下博主会用图文的方式和大家一起学习不同方法的实现并在这个过程中理解为什么说这中排序方法是二叉树结构。
3.2 hoare快排实现
hoare大佬最初的思想是 1、在数组中选取一个key值一般是选择第一个元素或者最后一个元素我们主要这边主要研究第一个元素做key值 2、设置两个指针一个指针right先从往右往左找比key小的值找到之后另一个指针left再从左往右走找比key大的值然后都找到后就交换两边的值重复上述过程最后当两个指针相遇的时候再将相遇点的值与key点的值交换此时key的左边都是比key小的值key的右边都是比key大的值这样就完成了一次选基准值的排序。 3、完成一次找基准值的排序后使数组有序的问题通过基准值key转化成使key左边和右边都有序的问题也就是这个key为基准再分割成两块区间再分别用上述方法找各自区间的key值继续重复之前的步骤递归直到区间不能被分割此时的数组就实现了有序。 以上的说法可能大家还不太能理解我们通过画图来理解hoare大佬的思想。 我们通过上图可以理解为什么说快速排序是一种二叉树结构的排序这个过程和二叉树的前序遍历非常相似。既然我们知道了hoare大佬具体想怎么干我们就明白了这个快排是用递归去实现的当然现在问题的关键就是我们如果进行基准排序去找到key值对应的位置下面我们来分析一趟基准排序的过程 以上就是完成一次基准排序的过程大家会发现此时恰好key的左边是比key小的key的右边都是比key大的其实这并不是巧合我们后面会分析这边我们先实现一下一次基准排序的代码 基准排序代码实现
int PartSort1(int* a, int left, int right)//hoare基准排序
{int keyi left;while (left right){//右先找比key大的while (left righta[right] a[keyi])right--;//左找比key小的while (left right a[left] a[keyi])left;//找到后就交换Swap(a[left], a[right]);}//此时相遇了把相遇的位置和keyi的位置交换Swap(a[left], a[keyi]);return left;
}
根据上述的一次基准排序的实现我们来通过递归实现整体快排的代码
void QuickSort(int* a, int left, int right)
{if (left right)return;int keyi PartSort1(a, left, right);//根据基准值去分割区间继续进行基准排序QuickSort(a, left, keyi - 1);QuickSort(a, keyi1,right);
}
思考以下问题
1、怎么判断递归的结束条件呢 2、hoare大佬是怎么确定每次相遇的时候相遇点的位置的值一定比key的值小呢 3、left可以从第二个位置开始走吗 通过上述的分析相信大家对hoare大佬的思想已经理解了
3.3 挖坑法快排实现 hoare大佬的思想真的是超凡脱俗非常厉害但是也有很多不容易理解的地方后面就有人进行了改进发明了挖坑版本的快排虽然名字叫挖坑但是比hoare会好理解很多下面我们来进行挖坑版本的分析
发明挖坑版本大佬的思想是 1、先把keyi对应的值记住然后在这个位置挖坑right找大找到了就停下来将停下来的位置的值去填坑然后right的位置变成新坑left找小找到后就把对应的值填坑然后left成为新坑以此类推下去直到left和right相遇将之前记住keyi的值填入坑内这个时候就完成了一次基准排序。 2、除了基准排序的方法和hoare大佬不同其余地方都是一样的也是用递归去解决。 通过这个方法我们来实现对应的基准排序算法
int PartSort2(int* a, int left, int right)//挖坑基准排序
{int key a[left];//记住key的值int hole left;//开始挖坑while (left right){//右先找比key大的while (left right a[right] key)right--;//找到后填坑然后挖新坑a[hole] a[right];hole right;//左找比key小的while (left right a[left] key)left;//找到后填坑然后挖新坑a[hole] a[left];hole left;}//此时相遇了把key值放在坑里a[hole] key;return hole;
}
整体实现
void QuickSort(int* a, int left, int right)
{if (left right)return;int keyi PartSort2(a, left, right);//根据基准值去分割区间继续进行基准排序QuickSort(a, left, keyi - 1);QuickSort(a, keyi1,right);
}
我们发现挖坑和填坑的思想特别好理解然后接下去就是前后指针版本快排
3.4 前后指针法快排实现
发明前后指针版本大佬的思想是 1、设置前指针prev指向首元素后指针cur指向第二个元素如果cur开始找小如果没找到小就一直往前走如果找到小的了就先停下来然后prev往前走一步在和cur交换值然后cur接着走……重复上述步骤最后cur走出数组返回后循环终止此时prev指向的位置和keyi的位置交换。 下面我们来实现前后指针快排的基准排序
int PartSort3(int* a, int left, int right) //前后指针基准排序
{int prev left;int cur left 1;int keyi left;while (cur right)//cur走出数组循环停止{//cur一直在走如果遇到比keyi小的就停下来等perv走一步后交换再接着走if (a[cur] a[keyi]){prev;Swap(a[prev], a[cur]);}cur;}//cur出去后prev的值和keyi交换Swap(a[keyi], a[prev]);return prev;
} 因为prev和cur指向一个位置的时候其实没有交换的必要所以可以将上面代码的优化一下
int PartSort3(int* a, int left, int right) //前后指针基准排序
{int prev left;int cur left 1;int keyi left;while (cur right)//cur走出数组循环停止{//cur一直在走如果遇到比keyi小的就停下来等perv走一步后交换再接着走if (a[cur] a[keyi]prev!cur)Swap(a[prev], a[cur]);cur;}//cur出去后prev的值和keyi交换Swap(a[keyi], a[prev]);return prev;
}
整体快排的实现
void QuickSort(int* a, int left, int right)
{if (left right)return;int keyi PartSort3(a, left, right);//根据基准值去分割区间继续进行基准排序QuickSort(a, left, keyi - 1);QuickSort(a, keyi1,right);
}
3.5 快排的复杂度分析
时间复杂度O(logN*N) 如果使用了三数取中的优化方法后面会介绍那么快排就不可能出现ON^2的情况所以最后时间复杂度是O(logN*N)
空间复杂度O(logN) 因为递归是要开销栈帧的空间可以重复利用而时间不可重复利用。所以这里至多递归到他的深度即h logN,所以他的空间复杂度是O(logN)
3.6 快排的优化
快排优化的过程源于这道OJ题
力扣排序数组 看到这题你可能会很开心这不就是一个排序吗我把最厉害的快排用上肯定能过的
结果是这样的—— 为什么呢因为力扣的测试用例设置了一个有序的数组来针对快排复杂度分析过原因了本质上就是因为有序的时候前面的keyi太小了所以我们设置一个改进方法——三数取中解决有序的情况
3.6.1 三数取中——针对有序
int GetMidIndex(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//a[left] a[mid]{if (a[mid] a[right])return mid;else if (a[right] a[left])return left;elsereturn right;}
}封装后我们前面三种方法的基准值排序都要加上以下代码这样就可以确保keyi的值是中间值了
int mid GetMidIndex(a, left, right);
Swap(a[mid], a[left]);
你可能觉得这样子应该能过了 那我们再测试一下—— 结果你发现又被针对了有序的情况解决了又面临着有大量重复数据的排序问题我们来分析一下 你会发现重复其实跟有序的情况是一样的每次right指针都会走到keyi的位置这样子时间复杂度也变成ON^2了。所以为了解决重复的问题我们有了三路划分的方法——
3.6.2 三路划分——针对重复 因为每次递归需要返回两个边界才行所以没办法单独封装一个partsort函数
代码实现
void QuickSort2(int* a, int left, int right)
{if (left right)return;int mid GetMidIndex(a, left, right);Swap(a[mid], a[left]);int phead left;int pcur left 1;int ptail right;int key a[left];while (pcur ptail){if (a[pcur] key){Swap(a[pcur], a[phead]);pcur;phead;}else if (a[pcur] key){Swap(a[pcur], a[ptail]);ptail--;}elsepcur;}QuickSort2(a, left, phead - 1);QuickSort2(a, ptail1,right);
} 结果我们发现还是过不了那究竟是哪里出问题了呢
因为里面有一组测试用例针对了三数取中也就是他把偏大和偏小的数都安排在恰好的位置所以我们为了针对这种情况将三数取中的其中一个数改成随机数接下来我们对三数取中再优化
3.6.3 三数取中再优化
将三数取中的其中一个数的下标变成随机下标
同时要记得在主函数加上时间种子
int GetMidIndex2(int* a, int left, int right)
{int mid left (rand() % (right - left));if (a[left] a[mid]){if (a[mid] a[right])return mid;else if (a[right] a[left])return left;elsereturn right;}else//a[left] a[mid]{if (a[mid] a[right])return mid;else if (a[right] a[left])return left;elsereturn right;}
}
void QuickSort2(int* a, int left, int right)
{if (left right)return;int mid GetMidIndex2(a, left, right);Swap(a[mid], a[left]);int phead left;int pcur left 1;int ptail right;int key a[left];while (pcur ptail){if (a[pcur] key){Swap(a[pcur], a[phead]);pcur;phead;}else if (a[pcur] key){Swap(a[pcur], a[ptail]);ptail--;}elsepcur;}QuickSort2(a, left, phead - 1);QuickSort2(a, ptail1,right);
} 终于过了要重点理解快排的优化思想
3.7 非递归法快排实现
3.7.1 栈实现
我们发现无论是hoare、挖坑还是前后指针本质区别就是基准排序方法不同但最后还是用递归去解决的递归虽好但是有些时候如果数据太大的话还是有可能造成栈空间不够的情况因此我们应该研究一下如果非递归实现——利用栈
利用栈实现非递归快排的大佬的思想是 利用栈来存储基准排序需要处理的区间每次从栈拿出需要处理的区间再将分割的区间放进栈中利用栈后进先出的特点每次都会先处理左边的区间再处理右边的区间模拟了递归的过程。 我们画个图来理解吧类似二叉树的前序遍历 非递归快排代码实现
需要包含栈的相关代码 void QuickSortNonR1(int* a, int left, int right)
{Stack st;StackInit(st);//把区间压进去,一定要先压右区间StackPush(st, right);StackPush(st, left);while (!StackEmpty(st)){//将数据弹出来进行进准计算int left StackTop(st);StackPop(st);int right StackTop(st);StackPop(st);//进行基准计算int keyi PartSort3(a, left, right);//分割区间left keyi-1keyikeyi1right//如果对应的区间还能分割就继续压,要注意要先压后面在压前面if (keyi 1 right){StackPush(st, right);StackPush(st, keyi1);}if (keyi - 1 left){StackPush(st, keyi-1);StackPush(st,left);}}//会一直到栈为空此时就拍好序了StackDestory(st);
}
3.7.2 队列实现
使用队列也是可以的就有点类似二叉树的层序遍历 代码实现 需要包含队列的一些文件 void QuickSortNonR2(int* a, int left, int right)
{Queue q;QueueInit(q);QueuePush(q, left);QueuePush(q, right);while (!QueueEmpty(q)){int left QueueFront(q);QueuePop(q);int right QueueFront(q);QueuePop(q);int keyi PartSort3(a, left, right);if (keyi - 1 left){QueuePush(q, left);QueuePush(q, keyi-1);}if (keyi 1 right){QueuePush(q, keyi 1);QueuePush(q, right);}}QueueDestory(q);
}
