排序算法之快速排序

快速排序（Quick Sort）是一种高效的排序算法，基于分治法（Divide and Conquer）的思想。它的核心是通过选择一个基准元素（pivot），将列表分为两部分：一部分小于基准元素，另一部分大于基准元素，然后递归地对这两部分进行排序。快速排序的平均时间复杂度为 O(n log n)，在实际应用中性能优异。

算法步骤

1.选择基准元素

基准元素可以是列表中任何一个元素：第一个、最后一个、中间的，都可以

2.分区

将列表进行排序，让大于基准值的数据在列表右侧，大于基准值的数据在列表左侧

3.递归排序

对基准左右侧分别进行递归排序，之后随后排序结束。

代码实现

JAVA

import java.util.Arrays;

public class quickSort {
    static void main(String[] args) {
        int[] arr = new int[]{14,65,3,78,95,4,25,61,88,91,76,25,43,74};
        quick(arr,0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quick(int[] arr, int start, int end) {
        if (start >= end){
            return;
        }
        //1.取中间值作为基准值
        int pivot = arr[(start + end) / 2];
        int low = start;
        int high = end;
        //2.排序
        while (low < high) {
            while (low < high && pivot <= arr[high]) {
                high--;
            }
            arr[low] = arr[high];
            while (low < high && pivot >= arr[low]){
                low++;
            }
            arr[high] = arr[low];
        }
        arr[low] = pivot;
        //3.递归调用进行排序
        //对基准值前面的序列进行递归
        quick(arr,start,low -1);
        //对基准值后面的序列进行递归
        quick(arr,low+1,end);
    }

}