# 快速排序

Harshit Jindal 2023年10月12日

## 快速排序算法实现

``````#include <bits/stdc++.h>
using namespace std;

int partition(int arr[], int beg, int end) {
// Select the last element as pivot element
int pivot = arr[end];
int i = (beg - 1);
// Move smaller elements to left side and larger on right side
for (int j = beg; j < end; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1],
arr[end]);  // Move pivot element to its right position in array
return (i + 1);
}

void quickSort(int arr[], int beg, int end) {
if (beg < end) {
int pi = partition(arr, beg, end);
quickSort(arr, beg,
pi - 1);  // Recursive Sort element on left side of partition
quickSort(arr, pi + 1,
end);  // Recursive Sort element on right side of partition
}
}
int main() {
int n = 6;
int arr[6] = {5, 3, 4, 2, 1, 6};
cout << "Input array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
quickSort(arr, 0, n - 1);  // Sort elements in ascending order
cout << "Output array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
``````

## 快速排序算法的复杂度

### 时间复杂度

• 平均情况

`````` T(n) = T(k) + T(n-k-1) + θ(n)
``````

• 最坏情况
``````T(n) = T(n-1) + θ(n)
``````

• 最佳情况
`````` T(n) = 2T(n/2) + θ(n)
``````

### 空间复杂度

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.