> For the complete documentation index, see [llms.txt](https://jen-hsuan-hsieh.gitbook.io/letcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jen-hsuan-hsieh.gitbook.io/letcode/2.algorithm/25quick-sort.md).

# 2.5.Quick sort

* **Introduction**
  * 目前被認為效率最高的排序演算法(sorting algorithm)
  * 快速排序法也是利用[divide and conquer](https://jenhsuan.gitbooks.io/letcode/content/2.algorithm/23divide-and-conquer.html),不斷地將資料分成兩部分以解決問題
  * [時間複雜度, 空間複雜度](https://jenhsuan.gitbooks.io/letcode/content/3data-structure/32shi-jian-fu-za-du-and-kong-jian-fu-za-du.html)
    * 最佳時間複雜度：O(nlog n)
    * 平均時間複雜度：O(nlog n)
    * 最差時間複雜度：O(n2)
    * 空間複雜度：O(n) 
  * 實作步驟:
    * 1.選擇序列中的一個數字為pivot(通常為最左邊的數字)
    * 2.將此序列中大於pivot的數字放到pivot右邊, 小於pivot的放到pivot左邊
    * 3.以pivot為中心, 將左半部與右半部各自進行步驟1\~2
* **程式碼**

```
void quicksort(int *data, int left, int right)
{
    if (left >= right){
        //function結束
        return;
    }
    //choose data[left] to be the pivot
    int pivot = data[left];
    int i = left + 1;
    int j = right;
    while (1){
        //找出大於pivort的數值
        while (i <= right){
            if (data[i] > pivot){
                break;
            }
            i = i + 1;
        }
        //找出大於pivort的數值
        while (j > left){
            if (data[j] < pivot){
                break;
            }
            j = j - 1;
        }
        //j會先結束while, 當i > j時跳出迴圈 
        if (i > j){
            break;
        }
        //將左右位置互換
        swap(&data[i], &data[j]);
    }
    //將左右位置互換
    swap(&data[left], &data[j]);
    quicksort(data, left, j - 1);
    quicksort(data, j + 1, right);    
}
void swap(int *a, int *b)
{
    int temp = *b;
    *b = *a;
    *a = temp;
}
```