快速排序(Quick Sort)是对冒泡排序的一种改进，基本思想是选取一个数作为关键字 key_value ，经过一趟排序，将整段序列分为两个部分，其中一部分的值都小于关键字，另一部分都大关键字。然后继续对这两部分继续进行排序，从而使整个序列达到有序。
递归实现方法：
void quick_sort(int arr[], int left, int right) { if (left >= right) return; int div = sort_operate(arr, left, right); //执行sort_operate()后，此时div左边的元素都小于arr[div]，右边的元素都小于arr[div]，一次排序完成 quick_sort(arr, left, div-1); //递归的对div两边的数列执行sort_operate() quick_sort(arr, div+1, right); }
一次排序过程：
int sort_operate(int arr[], int left, int right) { int key = left; int key_value = arr[key]; while (left < right) { while (left < right && arr[right] >= key_value) right--; while (left < right && arr[left] <= key_value) left++; swap(arr[right], arr[left]); } swap(arr[key], arr[left]); return left; }
全部代码如下：
#include <iostream> #include <algorithm> using namespace std; int sort_operate(int arr[], int left, int right) { int key = left; int key_value = arr[key]; while (left < right) { while (left < right && arr[right] >= key_value) right--; while (left < right && arr[left] <= key_value) left++; swap(arr[right], arr[left]); } swap(arr[key], arr[left]); return left; } void quick_sort(int arr[], int left, int right) { if (left >= right) return; int div = sort_operate(arr, left, right); quick_sort(arr, left, div-1); quick_sort(arr, div+1, right); } int main() { int n; cout << "Please input the number of arr: " << endl; cin >> n; int* arr = new int(n); cout << "Please input the element of arr (separate by space): " << endl; for (int i = 0; i < n; i++) cin >> arr[i]; quick_sort(arr, 0, n-1); for (int i = 0; i < n; i++) cout << arr[i] << ‘ ‘; cout << endl; return 0; }
原文：https://www.cnblogs.com/huwt/p/10924464.html