企业官网建设流程全解析

网站怎么做的,网站备案幕布设计,网站每天做多少外链合适,网站开发 需要用到什么软件有哪些文章目录前言一.思想二.具体例子三.代码实现1.具体代码2.代码运行过程四.算法效率分析1.时间复杂度1.基本分析2.进一步分析3.总结2.空间复杂度3.稳定性4.适用性五.快速排序的优化1.思路2.随机选取基准代码实现3.三数取中法代码实现六.知识回顾与重要考点结语前言 快速排序是一种…文章目录前言一.思想二.具体例子三.代码实现1.具体代码2.代码运行过程四.算法效率分析1.时间复杂度1.基本分析2.进一步分析3.总结2.空间复杂度3.稳定性4.适用性五.快速排序的优化1.思路2.随机选取基准代码实现3.三数取中法代码实现六.知识回顾与重要考点结语前言快速排序是一种基于交换的排序算法通过分治策略将待排序序列划分为两部分。算法首先选取基准元素通常为首元素使用双指针low和high从序列两端向中间扫描确保low指针左侧元素均小于基准high指针右侧元素均大于等于基准。通过不断交换元素位置最终将基准元素放置到正确位置完成一次划分。然后递归地对左右子序列重复上述过程直至所有元素有序。示例中展示了以49为基准的一次完整划分过程通过双指针交替移动和元素交换实现排序。该算法平均时间复杂度为O(nlogn)是一种高效的排序方法。基于“交换”的排序根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置一.思想算法思想在待排序表L [ 1... n ] L[1 ... n]L[1...n]中任取一个元素pivot \text{pivot}pivot作为枢轴或基准通常取首元素通过一趟排序将待排序表划分为独立的两部分L [ 1... k − 1 ] L[1 ... k-1]L[1...k−1]和L [ k 1... n ] L[k1 ... n]L[k1...n]使得L [ 1... k − 1 ] L[1 ... k-1]L[1...k−1]中的所有元素小于pivot L [ k 1... n ] \text{pivot}L[k1 ... n]pivotL[k1...n]中的所有元素大于等于pivot \text{pivot}pivot则pivot \text{pivot}pivot放在了其最终位置L(k)上这个过程称为一次“划分”。然后分别递归地对两个子表重复上述过程直至每部分内只有一个元素或空为止即所有元素放在了其最终位置上。二.具体例子增序我们用low和high两个指针分别指向此时我们要处理的这个序列的头和尾两个位置然后我们选择low所指向的这个元素让它作为所谓的基准元素(枢轴元素)接下来我们会让low和high这两个指针开始往中间移动,把所有的这些带排序的元素都给扫描一遍,在整个扫描的过程当中,我们需要保证high所指的这个指针的右边都是大于等于当前的基准元素49,而low指针它的左边,我们要保证都是小于49的元素由于此时low所指的这个位置是空的,所以我们先让high向左移动,那high当前所指的元素49 ≥ 49,所以下标为7的这个元素并不需要移动,然后high–此时high所指的这个元素是要小于49的,由于所有小于49的元素都应该放到low指针它所指的位置的左边,所以我们可以把27这个元素,让它移动到low所指的这个位置现在high所指的这个位置空出来了,那接下来我们让low指针往右移动,此时low所指的位置是要小于49的,所以不需要把它移到右边,接下来让low指针右移当前low指向的这个元素同样小于49,不需要把它移到右边,接下来让low指针右移当前low指向的这个元素已经大于了49,因此将其移动到high所指的位置接下来low所指的这个位置空了,因此我们看high指针,此时 high所指的元素是要大于等于49的,所以不需要移动,因此让high指针左移当前high所指的元素小于49,因此将49移动到low指向的位置由于high指向空,因此接下来切换回low指针,1349,因此low指针右移此时low所指元素为9749,因此需要将97右移到high所指向的位置现在又切换回high指针,9749,因此直接将high左移即可此时high指向元素为76≥49,所以high–当low和high碰到一起的时候,就说明其实我们已经把所有的这些带排序的元素,都给扫了一遍,所有比基准元素49更小的元素,都把它放到了low指针所指位置的左边,而所有比49这个基准元素更大的或者相等的元素,我们统统把它放在了high指针所指的右半部分,因此49一定放在low和high相遇的这个位置此时49这个元素的最终位置已确定对已经确定位置的元素49的左右这两个子表,再一次的用同样的方法进行划分左子表,依旧用low和high分别指向表的首元素和尾元素选中最前边的一个元素27作为基准元素,后面也是和之前一样的步骤low和high相遇的位置就是基准元素27的插入位置接下来0~2这个子表又再一次的被我们刚才选中的数轴元素,划分为了左右两个部分,那由于我们剩余的左右两个部分都只有一个元素,所以显然这两个部分我们不需要再进行别的处理也就是说0~2这个子表当中,所有这些元素的最终位置,我们此时都已经确定了右子表,和之前一样的操作,不做赘述对于4~7这个子表,通过基准元素76,再次的把它划分成了更小的两个部分,对于左半部分的处理思路是一样的,不做赘述显然,65和97这两个元素的最终位置也被确定了这就是最终结果三.代码实现1.具体代码//用第一个元素将待排序序列分成左右两个部分intPartition(intA[],intlow,inthigh){intpivotA[low];//第一个元素作为枢轴while(lowhighA[high]pivot)--high;A[low]A[high];//比枢轴小的元素移动到左端while(lowhighA[low]pivot)low;A[high]A[low];//比枢轴大的元素移动到右端}A[[low]pivot;//枢轴元素存放到最终位置returnlow;}93//快速排序94voidQuickSort(intA[],intlow,inthigh){95if(lowhigh){//递归跳出的条件96intpivotpospartition(A,low,high);//划分97QuickSort(A,low,pivotpos-1);//划分左子表98QuickSort(A,pivotpos1,high);//划分右子表99}100}2.代码运行过程刚开始会传入整个数组a的值,同时指明最左边的元素和最右边的元素,下标应该是0~7这个范围此时满足if条件low小于high,因此进入if条件进行处理if(low high),接下来会调用Partition这个函数int pivotpos partition(A, low, high);,这个函数的功能就是进行一次划分,我们要把a这个数组的low到high内的元素进行一个划分,所以接下来在函数调用栈当中会压入和Partition这个函数相关的一些的信息,同时记录QuickSort函数执行到了第几行,此时是执行到了96行(#96)此时我们传入的low 0和high 7值给Partition函数,此时用临时变量pivot(基准/枢轴)存放low指针所指向的这个元素作为基准int pivotA[Low];此时外层while循环判断low highwhile(lowhigh)因此进入第一个内层while循环,第一个内层while循环会判断low是否小于high且此时high指向的元素是否大于等于基准,如果是,则直接左移high很显然,这层while循环做的事情是让high指针不断地左移,直到找到一个比枢轴元素更小的元素为止while(lowhighA[high]pivot)--high;此时发现high所指元素比pivot更小,因此将high所指元素覆盖到low所指元素A[low]A[high];接下来就是进入第二个内层循环,第二个内层while循环会判断low是否小于high且此时low指向的元素是否小于基准,如果是,则直接右移low很显然,这层while循环做的事情是让low指针不断地右移,直到找到一个比枢轴元素更大的元素为止while(lowhighA[low]pivot)low;此时发现low所指元素比pivot更大,因此将low所指元素覆盖到high所指元素A[high]A[low];此时发现low仍小于high,因此继续重复上面的操作,结果如下此时由于low high,因此A[high]A[low];或者A[low]A[high];不再起作用,并且可以跳出外层循环,将pivot的值复制到low和high一起指向的位置A[low]pivot;最终返回这个low的值作为新的边界分割原表,同时将第一层QuickSor函数pivotpos 3,函数代码执行到97的信息更新到函数调用栈int pivotpospartition(A, low, high);查看函数调用栈中之前是执行到了96行,因此此时我们需要执行第97行,划分左子表(low 0 ~ pivotpos - 1 2)QuickSort(A, low, pivotpos-1);,此时将low 0,high等于2,的QuickSort函数信息压入栈中处理过程和之前的一层QuickSort函数处理一致,不多赘述同时将第二层函数pivotpos 1,函数代码执行到96的信息更新到函数调用栈查看函数调用栈中最顶层函数的执行行数为96行,因此接下来执行97行,也就是划分左子表由于low等于high,说明此时这个子表当中其实只剩余一个元素,不满足if的条件if(lowhigh),因此可以直接返回执行第二层QuickSort,通过查看这一层的信息得知之前是执行到了第97行,因此此时执行第98行,也就是划分右子表QuickSort(A,pivotpos1,high);由于low high,因此直接回到第二层,发现第二层执行到了第98行,后面已经没有可执行语句,因此返回第一层此时发现第一层函数执行到了第97行,因此接下来执行第98行QuickSort(A,pivotpos1,high);后面的步骤也差不多,因此不再赘述,图片过程如下接着更新第二层函数的函数调用栈处理左子表更新第三层函数的函数调用栈接下来不再赘述,结果如下四.算法效率分析1.时间复杂度1.基本分析初始序列:由于Partition函数是两个指针不断往中间移动,因此其时间复杂度不会超过O(n)第一层QuickSort处理后:由于Partition函数是两个指针不断往中间移动,因此其时间复杂度不会超过O(n)第二层QuickSort处理后:同样不会超过O(n)第三层QuickSort处理后:同样不会超过O(n)第四层QuickSort处理后,得到最终序列可以看出:每一层的QuickSort只需要处理剩余的待排序元素时间复杂度不超过O(n)因此:时间复杂度 O ( n ∗ 递归层数 ) 时间复杂度O(n*递归层数)时间复杂度O(n∗递归层数)2.进一步分析递归可以画成如下图进行表示把n个元素组织成二叉树二叉树的层数就是递归调用的层数由于n 个结点的二叉树最小高度 ⌊ log ⁡ 2 n ⌋ 1 最小高度 \lfloor\log_{2}n\rfloor 1最小高度⌊log2​n⌋1最大高度 n 最大高度 n最大高度n因此:最好时间复杂度 O ( n ∗ ⌊ log ⁡ 2 n ⌋ 1 ) → O ( n l o g 2 n ) 最好时间复杂度O(n*\lfloor\log_{2}n\rfloor 1)\rightarrow O(nlog_2n)最好时间复杂度O(n∗⌊log2​n⌋1)→O(nlog2​n)最坏时间复杂度 : O ( n 2 ) 最坏时间复杂度:O(n^2)最坏时间复杂度:O(n2)3.总结最好时间复杂度:O ( n l o g 2 n ) O(nlog_2n)O(nlog2​n)平均时间复杂度O ( n l o g 2 n ) O(nlog_2n)O(nlog2​n)最坏时间复杂度:O ( n 2 ) O(n^2)O(n2)快速排序是所有内部排序算法中平均性能最优的排序算法2.空间复杂度空间复杂度 O ( 递归层数 ) 空间复杂度O(递归层数)空间复杂度O(递归层数)因此:最好空间复杂度O ( l o g 2 n ) O(log_2n)O(log2​n)最坏空间复杂度O ( n ) O(n)O(n)若每一次选中的“枢轴”将待排序序列划分为很不均匀的两个部分则会导致递归深度增加算法效率变低若每一次选中的“枢轴”将待排序序列划分为均匀的两个部分则递归深度最小算法效率最高总结:若初始序列有序或逆序则快速排序的性能最差因为每次选择的都是最靠边的元素3.稳定性不稳定例4.适用性普通的快速排序可以应用于链表但由于链表结构的特性其性能优势不如在数组上明显方法选择基准通常选择链表的头节点作为基准元素pivot。划分分区使用两个指针例如small和cur。small指针指向已处理部分中所有小于基准的节点的最后一个。cur指针遍历链表。当cur指向的节点值小于基准值时将small指针后移然后交换small和cur节点的值。这样就能将小于基准的节点逐步归拢到链表前半部分。基准归位遍历完成后将基准节点与small指针所指节点交换值。此时基准节点就位于正确位置其左边节点的值都小于它右边节点的值都大于等于它。递归排序递归地对基准左边和右边的两个子链表进行快速排序五.快速排序的优化1.思路尽量选择可以把数据中分的枢轴元素。eg①选头、中、尾三个位置的元素取中间值作为枢轴元素②随机选一个元素作为枢轴元素2.随机选取基准代码实现// 交换函数voidSwap(int*a,int*b){inttemp*a;*a*b;*btemp;}// 快速排序辅助函数(划分左右子表)intPartition(intarr[],intlow,inthigh){// 优化随机选择基准避免最坏情况intrandomIndexlowrand()%(high-low1);Swap(arr[low],arr[randomIndex]);// 将随机基准交换到首位intpivotarr[low];while(lowhigh){// 从右往左找到一个小于基准元素的数while(lowhigharr[high]pivot)high--;arr[low]arr[high];// 覆盖// 从左往右找到一个大于基准元素的数while(lowhigharr[low]pivot)low;// 修正lowarr[high]arr[low];// 覆盖}arr[low]pivot;// 基准归位returnlow;}// 快速排序主函数voidQuickSort(intarr[],intlow,inthigh){if(lowhigh){// 划分子表intpivotPartition(arr,low,high);// 递归左子表QuickSort(arr,low,pivot-1);// 递归右子表QuickSort(arr,pivot1,high);}}// 快速排序启动函数voidQuickSortStrart(intarr[],intlength){intlow0,highlength-1;// 将分别用low和high指向数组的首尾QuickSort(arr,low,high);}3.三数取中法代码实现// 快速排序辅助函数(划分左右子表)intPartition(intarr[],intlow,inthigh){intpivotarr[low];// 定下基准元素while(lowhigh){// 从右往左找到一个小于基准元素的数while(lowhigharr[high]pivot)high--;// 找到后将arr[high]覆盖到arr[low]arr[low]arr[high];// 从左往右找到一个大于基准元素的数while(lowhigharr[low]pivot)low;// 找到后将arr[low]覆盖到arr[high]arr[high]arr[low];}// 将基准元素插入到最终位置arr[low]pivot;// 返回基准元素的位置returnlow;}// 交换两个元素的值voidswap(int*a,int*b){inttemp*a;*a*b;*btemp;}// 三数取中函数返回中位数的索引intmedianOfThree(intarr[],intlow,inthigh){// 计算中间位置的索引避免直接相加可能导致的整数溢出intmidlow(high-low)/2;// 通过三次比较对arr[low], arr[mid], arr[high]进行排序// 目标使得 arr[low] arr[mid] arr[high]if(arr[mid]arr[low]){swap(arr[low],arr[mid]);}if(arr[high]arr[low]){swap(arr[low],arr[high]);}if(arr[high]arr[mid]){swap(arr[mid],arr[high]);}// 此时arr[mid]就是三个元素中的中位数// 返回中位数的索引returnmid;}// 三数取中法选择基准快速排序voidMidQuickSort(intarr[],intlow,inthigh){if(lowhigh){// 1. 使用三数取中法选择基准并交换到起始位置intmidIndexmedianOfThree(arr,low,high);swap(arr[low],arr[midIndex]);// 2. 进行分区操作intpivotIndexPartition(arr,low,high);// 3. 递归排序左右子数组MidQuickSort(arr,low,pivotIndex-1);MidQuickSort(arr,pivotIndex1,high);}// 当 low high 时递归终止}六.知识回顾与重要考点注408原题中说对所有尚未确定最终位置的所有元素进行一遍处理称为“一趟”排序因此一次“划分”≠一趟排序。一次划分可以确定一个元素的最终位置而一趟排序也许可以确定多个元素的最终位置。结语八更如果想查看更多章节,请点击:一、数据结构专栏导航页