> For the complete documentation index, see [llms.txt](https://jun-wang.gitbook.io/learnjava/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jun-wang.gitbook.io/learnjava/ji-shu-xue-xi/suan-fa/pai-xu-suan-fa/kuai-su-pai-xu.md).

# 快速排序

## 快排思路

基于冒泡排序，通过比较和交换。

1. 首先设定一个分界值，将小于等于分界值的放在左边，将大于分界值的放在右边；
2. 然后左边和右边的数据可以单独进行排序，也按照上述思路分为左右两部分；
3. 重复上述过程，这是一个递归排序。

**时间复杂度：O(nLog2n) 最好情况：O(nLog2n) 最坏情况：O(n^2)**

**空间复杂度：O(1)**

**稳定性：不稳定**

**复杂性：较复杂**

## Java实现

```java
package com.wangjun.arithmetic;

import java.util.Arrays;

/*
 * 快速排序
 */
public class SortQuick {

    public static void main(String[] args) {
        int[] arr = {2,3,7,5,43,8,9,0,3,1};
        SortQuick ss = new SortQuick();
        ss.sortQuick(arr);
        System.out.println(Arrays.toString(arr));
    }

    public void sortQuick(int[] arr) {
        sortHelper(arr, 0, arr.length - 1);
    }

    public void sortHelper(int[] arr, int start, int end) {
        int left = start;
        int right = end;
        int middle = arr[(left+right)/2];
        while(left < right) {
            /*
             * ? left不会越界么
             * 不会，因为它最多走到middle的位置，就相等了，不满足while条件；
             * 就算left和right都与middle相等然后交换了，剩下的交给递归去做
             */
            while(middle > arr[left]) {
                left++;
            }
            while(middle < arr[right]) {
                right--;
            }
            if(left < right) {
                int tem = arr[left];
                arr[left] = arr[right];
                arr[right] = tem;
                left++;
                right--;
            }
        }
        /*
         * ? 为啥要有这一步，为了完全隔开左右两边
         * 考虑到这种情况 7 5 3 排好序后是 3 5 7 这时left=right=1
         * 如果不让left++，那么左边和右边递归排序就重复了 5 这个值
         * 由于是同步的，右边先排好后，中间这个值可能已经不是5了
         * 还可能导致迭代死循环
         */
        if(left == right) {
            if(arr[left] > middle) { //处理边界值，保证左边都是小于等于middle的值，右边都是大于等于middle的值
                right--;
            }else {
                left++;
            }
        }
        if(left < end) {
            sortHelper(arr,left,end);
        }
        if(right > start) {
            sortHelper(arr, start, right);
        }
    }
}
```

写快排的时候可以分2步：

1. 写一个算法实现：取一个值，将小于它的放在左边，大于它的放在右边；
2. 将左右部分分别递归调用，注意下处理边界值就行了；


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jun-wang.gitbook.io/learnjava/ji-shu-xue-xi/suan-fa/pai-xu-suan-fa/kuai-su-pai-xu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.