10个Java函数，实现快速排序算法

快速排序是一种常用的排序算法，它的基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

下面介绍10个Java函数，实现快速排序算法。

1. 使用递归方式实现快速排序

public void quickSort(int[] arr, int left, int right) {
    if (left >= right) return; // 如果左指针大于等于右指针，直接返回
    int i = left, j = right, pivot = arr[left];
    while (i < j) {
        while (i < j && arr[j] >= pivot) j--;
        if (i < j) arr[i++] = arr[j];
        while (i < j && arr[i] < pivot) i++;
        if (i < j) arr[j--] = arr[i];
    }
    arr[i] = pivot;
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}

2. 使用栈方式实现快速排序

public void quickSort(int[] arr, int left, int right) {
    Stack<Integer> stack = new Stack<>();
    stack.push(left);
    stack.push(right);
    while (!stack.isEmpty()) {
        int r = stack.pop(), l = stack.pop();
        if (l >= r) continue;
        int i = l, j = r, pivot = arr[l];
        while (i < j) {
            while (i < j && arr[j] >= pivot) j--;
            if (i < j) arr[i++] = arr[j];
            while (i < j && arr[i] < pivot) i++;
            if (i < j) arr[j--] = arr[i];
        }
        arr[i] = pivot;
        stack.push(l);
        stack.push(i - 1);
        stack.push(i + 1);
        stack.push(r);
    }
}

3. 使用递归方式实现快速排序（优化版）

public void quickSort(int[] arr, int left, int right) {
    if (left >= right) return; // 如果左指针大于等于右指针，直接返回
    int i = left, j = right, pivot = arr[left + (right - left) / 2];
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    }
    quickSort(arr, left, j);
    quickSort(arr, i, right);
}

4. 使用栈方式实现快速排序（优化版）

public void quickSort(int[] arr, int left, int right) {
    Stack<Integer> stack = new Stack<>();
    stack.push(left);
    stack.push(right);
    while (!stack.isEmpty()) {
        int r = stack.pop(), l = stack.pop();
        if (l >= r) continue;
        int i = l, j = r, pivot = arr[l + (r - l) / 2];
        while (i <= j) {
            while (arr[i] < pivot) i++;
            while (arr[j] > pivot) j--;
            if (i <= j) {
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }
        }
        stack.push(l);
        stack.push(j);
        stack.push(i);
        stack.push(r);
    }
}

5. 使用递归方式实现快速排序（三路快排）

public void quickSort(int[] arr, int left, int right) {
    if (left >= right) return; // 如果左指针大于等于右指针，直接返回
    int i = left, j = right, m = left + (right - left) / 2, pivot = arr[m];
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    }
    quickSort(arr, left, j);
    quickSort(arr, i, right);
}

6. 使用递归方式实现快速排序（随机快排）

public void quickSort(int[] arr, int left, int right) {
    if (left >= right) return; // 如果左指针大于等于右指针，直接返回
    int i = left, j = right, m = left + (right - left) / 2, pivot = arr[m];
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    }
    int k = left + new Random().nextInt(right - left + 1);
    int tmp = arr[k];
    arr[k] = arr[j];
    arr[j] = tmp;
    quickSort(arr, left, j);
    quickSort(arr, i, right);
}

7. 使用递归方式实现快速排序（枢轴元素选取方法）

public void quickSort(int[] arr, int left, int right) {
    if (left >= right) return; // 如果左指针大于等于右指针，直接返回
    int i = left, j = right, pivot = getPivotElement(arr, left, right);
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    }
    quickSort(arr, left, j);
    quickSort(arr, i, right);
}

private int getPivotElement(int[] arr, int left, int right) {
    if (right - left <= 5) // 优化，当子序列长度小于等于5时，直接使用插入排序
        return getMedianOfFive(arr, left, right);
    int i, j, k, len = right - left + 1;
    int[] tmp = new int[(len + 4) / 5];
    for (i = left, j = 0; i <= right; i += 5, j++)
        tmp[j] = getMedianOfFive(arr, i, Math.min(i + 4, right));
    int pivot = getPivotElement(tmp, 0, tmp.length - 1);
    for (i = left, j = right; i <= j;) {
        for (; i <= j && arr[i] < pivot; i++);
        for (; i <= j && arr[j] > pivot; j--);
        if (i <= j) {
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
            i++;
            j--;
        }
    }
    if (j - left + 1 == (len + 1) / 2)
        return pivot;
    if (j - left + 1 > (len + 1) / 2)
        return getPivotElement(arr, left, j);
    return getPivotElement(arr, i, right);
}

private int getMedianOfFive(int[] arr, int left, int right) {
    insertSort(arr, left, right);
    int mid = left + (right - left) / 2;
    return arr[mid];
}

private void insertSort(int[] arr, int left, int right) {
    for (int i = left + 1; i <= right; i++) {
        int tmp = arr[i], j = i - 1;
        for (; j >= left && arr[j] > tmp; j--)
            arr[j + 1] = arr[j];
        arr[j + 1] = tmp;
    }
}

8. 使用递归方式实现快速排序（随机ized select）

`java

public void quickSort(int[] arr, int left, int right) {

if (left >= right) return; // 如果左指针大于等于右指针，直接返回

int i = left, j = right, k = left