网站建设及优化,wordpress出错,数字营销名词解释,品牌网站建设3a小蝌蚪理解快速排序
首先了解以下快速排序
快速排序#xff08;QuickSort#xff09;是一种常用的排序算法#xff0c;属于比较排序算法的一种。它是由英国计算机科学家Tony Hoare于1960年提出的#xff0c;是一种分而治之#xff08;divide and conquer#xff09;的算法。 …理解快速排序
首先了解以下快速排序
快速排序QuickSort是一种常用的排序算法属于比较排序算法的一种。它是由英国计算机科学家Tony Hoare于1960年提出的是一种分而治之divide and conquer的算法。
快速排序的基本思想是通过选择一个基准元素将数组分成两个子数组然后对这两个子数组进行递归排序。具体步骤如下 选择基准元素 从数组中选择一个元素作为基准元素通常选择数组的第一个元素。 分区操作 将数组中小于基准元素的元素移到基准元素的左边大于基准元素的元素移到基准元素的右边。基准元素在这个过程中找到了最终的排序位置。这个操作称为分区操作。 递归排序 对基准元素左右两侧的子数组分别进行递归排序。
这个过程递归进行直到整个数组有序。由于快速排序采用了分治的思想它的平均时间复杂度为O(n log n)其中n是数组的长度。在最坏情况下快速排序的时间复杂度为O(n^2)但通常情况下它的性能很好而且它是原地排序算法不需要额外的空间。
快速排序是许多排序算法中最快的一种它在实际应用中被广泛使用。
下面给大家画一下图来理解以下快速排序以中间元素为基准
首先确定基准元素 然后就是对序列进行遍历如果比基准元素大的就放到右边比基准元素小的就放到左边确定一个变量left排序的起点这里为数列开始从左边开始如果遇到一个比基准元素大的就停下确定一个变量right排序的终点这里为数列结尾从右边开始遇到一个比基准元素小的节点停止然后交换两个停止索引的值然后继续进行遍历遇到上面同样的情况进行交换如果leftright 就停止此时第第一个分区结束进行下一次的基准选择与分区其实这里就是递归调用的抵挡。分为左右两边。 此时第一次区分结束使得基准的左边都小于基准右边都大于 分为两个数列然后重复上面的操作。知道只有一个那就是排序完成 代码实现
第一个版本
public static void method2(int[] arr,int left , int right){int start left ;int end right;if(startend){return;}while(left right){int pivot arr[(left right)/2];while(leftright arr[left]pivot) left;while(leftright arr[right] pivot) right--;if(left right){int temp arr[right];arr[right] arr[left];arr[left] temp;left ;right--;}}method2(arr,start,right);method2(arr,left,end);}第二个版本
public static void method1(int[] arr,int left,int right){if(left right){int i left -1 ;int pivot arr[right];for(int j left ; j right ;j){if(arr[j] pivot){i;int temp arr[j];arr[j] arr[i];arr[i] temp;}}int pivotIndex i 1;int temp arr[right];arr[right] arr[pivotIndex];arr[pivotIndex] temp;method1(arr,left,pivotIndex-1);method1(arr,pivotIndex1,right);}}代码的理解细看上面文字就好了。 点击链接我正在「编程导航」和朋友们讨论有趣的话题你⼀起来吧 也可以加我QQ2837468248咨询说明来意
