数据结构--快速排序

原理

选择一个关键值作为基准值（一般选择第一个元素为基准值元素），将比基准值大的都放在右边的序列中，将比基准值小的都放在左边的序列中。

流程

1. 从后往前比较，用基准值和最后一个值进行比较。如果比基准值小，则交换位置；如果比基准值大，则继续比较下一个值，指导找到第1个比基准值小的值才交换位置；
2. 在从后往前找到第1个比基准值小的值并交换位置之后，从前往后比较。如果有比基准值大的，则交换位置；如果没有，则继续比较下一个，直到找到第1个比基准值大的值才交换位置；
3. 重复执行以上过程，指导从前往后比较的索引大于等于从后往前的索引，则结束以此循环。此时，对于基准值来说，左右两边都是有序的数据序列。
4. 重复以上过程，分别比较左右两边的序列，直到整个数据序列有序。

图解

代码

public static int[] quicksort(int []arr,int low,int high) { int start = low;//从前往后的索引 int end = high;//从后往前的索引 int key = arr[low];//基准值 while (start < end) { //1.从后往前比较 while (start < end && arr[end] >= key) end--; //如果没有比基准值小的，比较下一位，直到找到比基准值小的，交换位置；然后从前往后比较 if (arr[end] <=key) { int tmp = arr[start]; arr[start] = arr[end]; arr[end] = tmp; } //2.从前往后比较 while (start < end && arr[start] <= key) start++; //如果没有比基准值大的，比较下一位，直到找到比基准值大的，交换位置； if (key <= arr[start]) { int tmp = arr[start]; arr[start] = arr[end]; arr[end] = tmp; } } //3.递归左边序列：从第1个索引位置到“关键字索引-1” if (start < low) quicksort(arr, low, start - 1); //4.递归右边索引，从“关键值索引+1”到最后一个位置 if (end < high) quicksort(arr, end + 1, high); return arr; } 

【补充：Python实现的快排】

def quicksort(array): if len(array) < 2: return array  ←------基线条件：为空或只包含一个元素的数组是“有序”的 else: pivot = array[0] ←------递归条件
    less = [i for i in array[1:] if i <= pivot] ←------由所有小于基准值的元素组成的子数组
    greater = [i for i in array[1:] if i > pivot] ←------由所有大于基准值的元素组成的子数组 return quicksort(less) + [pivot] + quicksort(greater) 

本文地址：https://blog.csdn.net/qq_31278903/article/details/108232691