当前位置：首页 > news >正文

北京通信管理局网站备案wordpress首页静态页面

news 2025/9/17 20:10:45

北京通信管理局网站备案,wordpress首页静态页面,商标注册网上,wordpress免签约！！！排序仅针对于数组哦本次排序是按照升序来的哦代码后边有图解哦介绍快速排序英文名为Quick Sort 基本思路快速排序采用的是分治思想，即在一个无序的序列中选取一个任意的基准元素base，利用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为带排序数组的起始位置和最终位置，所以right=arr.length-1System.out.println(Arrays.toString(arr));}public static void sort(int[] arr,int left,int right){if(left>=right){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 && i<j){j--;}    // 循环停止，说明j指向的数值要比基准数小。降序为<= while(arr[i]<=base && i<j){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,i+1,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,i+1,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;base=arr[0];left = [x for x in arr if x<base];middle = [x for x in arr if x==base];right = [x for x in arr if x>base];return quickSort(left)+middle+quickSort(right);arr=[7,2,3,6,1,5,4];
print(quickSort(arr))  # [1, 2, 3, 4, 5, 6, 7]