> For the complete documentation index, see [llms.txt](https://jiek.gitbook.io/sorting-algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jiek.gitbook.io/sorting-algorithm/liu-hang-pai-xu-suan-fa-popular-sorting-algorithms/gao-xiao-pai-xu-efficient-sorts/quick_sort.md).

# 快速排序 Quicksort

## Quick sort快速排序

@See <https://en.wikipedia.org/wiki/Quick_sort> @See <https://github.com/jiek2529/java_algorithm> - QuickSort

![](https://2531019738-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6gnm_fO-nBQv_cernA%2Fsync%2Fc10710514fc1f6e3172da96c69184db4c06e5429.gif?generation=1588815968678589\&alt=media)

### principle原理

把列表按中间值进行左右大小换位。 左边第一个比中间值大的，与右边自右向左第一个比中间值小的进行换位。

在根据左边循环后最大的位置为界，进行小范围的再按此方式循环置换，达到排序。

## example示例

```java
public void sort(int[] list) {
        if (list != null && list.length > 1) {
            quickSort(list, 0, list.length - 1);
        }
    }

    private void quickSort(int list[], int left, int right) {
        int index = partition(list, left, right);
        if (left < index - 1) {
            quickSort(list, left, index - 1);
        }
        if (index < right) {
            quickSort(list, index, right);
        }
    }

    /**
     * 分区折中交换
     *
     * @param list  int数组
     * @param left
     * @param right
     * @return
     */
    private int partition(int list[], int left, int right) {
        int i = left, j = right;
        int pivot = list[(left + right) / 2];//取折中点的值
        while (i <= j) {//如果是倒序，就是把以下两while条件判断修改
            while (list[i] < pivot)
                i++;
            while (list[j] > pivot)
                j--;
            if (i <= j) {
                swap(list, i, j);
                i++;
                j--;
            }
        }
        return i;
    }
```