做技术网站赚钱吗,浙江网站开发工程师,15年做那些网站致富,一般使用的分辨率的显示密度是#xff01;#xff01;#xff01;排序仅针对于数组哦本次排序是按照升序来的哦代码后边有图解哦 介绍
快速排序英文名为Quick Sort
基本思路
快速排序采用的是分治思想#xff0c;即在一个无序的序列中选取一个任意的基准元素base#xff0c;利用base将待排序的序列分… 排序仅针对于数组哦本次排序是按照升序来的哦代码后边有图解哦 介绍
快速排序英文名为Quick Sort
基本思路
快速排序采用的是分治思想即在一个无序的序列中选取一个任意的基准元素base利用base将待排序的序列分成两部分前面部分元素均小于或等于基准元素后面部分均大于或等于基准元素然后采用递归的方法分别对前后两部分重复上述操作直到将无序序列排列成有序序列
代码
!----java-----
import java.util.Arrays;public class QuickSort {public static void main(String[] args) {int[] arr {7,2,3,6,1,5,4}; // 待排序数组sort(arr,0, arr.length-1); // 方法调用left和right为带排序数组的起始位置和最终位置所以rightarr.length-1System.out.println(Arrays.toString(arr));}public static void sort(int[] arr,int left,int right){if(leftright){return;} // 判断带排序数组的长度严格的左边游标要不大于右边游标int base arr[left]; // 定义基准数int i left; // 定义左边的游标。这里不用left是因为left位置为基准数基准数不能变int j right; // 定义右边的游标。这里不用right是因为后续递归的时候需要一个参数while(i!j){ // 循环走起当i和j相遇时跟基准数交换。不相遇时i位置大于基准数j位置小于基准数时i位置和j位置的数交换/** 思考下为啥这里先是j在i前边 */while(arr[j]base ij){j--;} // 循环停止说明j指向的数值要比基准数小。降序为 while(arr[i]base ij){i;} // 循环停止说明i指向的数值要比基准数大。降序为 /** 【公布问题答案啦】* 因为j停下的时候代表当前数比基准数小i停下是当前数比基准数大。我们此次排序是升序相遇数要和基准数交换所以需要保证相遇数一定要小于基准数*/// 本次排序为升序即需要找到一个位置这个位置的左边都是比基准数小的右边都是比基准数大的int temp arr[i]; // i比基准数大j比基准数小交换。交换完成后i和j不等两个游标继续前走或后走arr[i] arr[j];arr[j] temp;}// i和j相遇,i也行j也行因为都指向一个嘛跟基准数交换。然后对基准数左右两遍递归arr[left] arr[i];arr[i] base;sort(arr,left,i-1);sort(arr,i1,right);}
}!------------------------
运行结果
[1, 2, 3, 4, 5, 6, 7]!----python-----
def quickSort(arr, left, right):if left right:return arr;base arr[left];i, j left, right;while i ! j:while arr[j] base and i j:j - 1while arr[i] base and i j:i 1arr[j], arr[i] arr[i], arr[j];arr[i], arr[left] arr[left], arr[i];quickSort(arr,left,i-1);quickSort(arr,i1,right);return arrarr [7,2,3,6,1,5,4]
print(quickSort(arr, 0, len(arr) - 1))
!------------------------
运行结果
[1, 2, 3, 4, 5, 6, 7]代码思路及流程图直接上图不清楚可以对照代码看哦 复杂度
时间复杂度最好和平均情况下为O(n log n)最坏情况下为O(n^2)。空间复杂度最好情况下为O(log n)最坏情况下为O(n)额外空间为O(1)。 (复杂度先记住吧等后续研究彻底了会再写篇文章的)它是非稳定排序
扩展一下
Python的一个更简单的方法
# 该方法不适用java哦
def quickSort(arr):if len(arr)2:return arr;basearr[0];left [x for x in arr if xbase];middle [x for x in arr if xbase];right [x for x in arr if xbase];return quickSort(left)middlequickSort(right);arr[7,2,3,6,1,5,4];
print(quickSort(arr)) # [1, 2, 3, 4, 5, 6, 7]巩固一下
给定一个数组用上述方法进行排序流程是不是跟下图一样呢 int[] arr {3,7,1,6,2,5,4}
文章推荐
实在是不会做动画如果还看不懂可以移步这里 十大经典排序算法 【漫画】不要再问我快速排序了有错误请指正谢谢各位~
