[C++知识库]C++实现快速排序

1）选择一个基准元素,通常选择第一个元素或者最后一个元素,

2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的?元素值比基准值大。

3）此时基准元素在其排好序后的正确位置

4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

#include

#include

using namespace std;

void swap(int& a, int& b)

{

int temp = a;

a = b;

b = temp;

}

//划分函数

int partition(vector& arr, int low, int high)

{

int i = low - 1;

int j = high;

int pivot = arr[high];

while (1)

{

while (i

while (j >= 0 && arr[--j] > pivot);

if (i < j)

swap(arr[i], arr[j]);

else

break;

}

//把枢纽元素放到正确的位置上

swap(arr[i], arr[high]);

return i;

}

//快速排序

void qsort(vector& arr, int low, int high)

{

if (low < high)

{

int mid = partition(arr, low, high);

qsort(arr, low, mid - 1);

qsort(arr, mid + 1, high);

}

}

//快速排序入口

void quick_sort(vector& arr, int n)

{

qsort(arr, 0, n - 1);

}

int main()

{

vector arr = { 9,5,2,11,12,4,3,1,7 };

int n = 9;

quick_sort(arr, n);

for (int i = 0; i < n; i++)

{

cout << arr[i] << " ";

}

return 0;

}