零、写在前面

CSDN21天学习挑战赛
本人蒟蒻一枚，文章若有不足之处请大家批评指出，欢迎大家留言。

活动地址：CSDN21天学习挑战赛

文章目录

零、写在前面
一、排序算法
二、快速排序

一、排序算法

排序(Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素的任意序列，重新排列成一个关键字有序的序列。

二、快速排序

快速排序是一种分而治之思想在排序算法上的典型应用。
是对冒泡排序算法的一种改进。

1. 快速排序步骤

快速排序算法多次比较和交换来实现排序。需要通过基准将数据划分成两个部分，这两个部分也通过一个基准划分，一直到不可再分。

1.1 步骤

以第一个数组元素作为 “基准”（pivot）
遍历数组，将所有比基准小的元素都移动到基准的左边。遍历结束后所有比基准小的元素都在基准的左边，比基准大的都在基准的右边，基准所在的位置将组分为左右两个子数组。
递归地，将左右两子数组重复1.2.的步骤。

2. 代码实现

public static void main(String[] args) {
    int[] arr = {10, 9, 7, 19, 99, 24, 71, 2, 25, 31};
    int[] a = {2,8,7,1,3,5,6,4};
    quickSort(a, 0, a.length - 1);
    for (int data : a){
        System.out.print(data + " ");
    }
}

private static int[] quickSort(int[] arr, int left, int right) {
    if (left < right) {
        int partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, right);
    }
    return arr;
}

private static int partition(int[] arr, int left, int right) {
    // 设定基准值（pivot）
    int pivot = arr[left];
    int index = left + 1;
    for (int i = index; i <= right; i++) {
        if (arr[i] < pivot) {
            // 交换两个元素
            int tmp = arr[i];
            arr[i] = arr[index];
            arr[index] = tmp;
            index++;
        }
    }
    // 将基准值交换到对应位置
    arr[left] = arr[index - 1];
    arr[index - 1] = pivot;
    return index - 1;
}