快速排序算法c/c++

快速排序

思想（分治思想）

1、确定分界的数x
可以是开头q[left]、中间q[(left+right+1)/2]和结尾q[right]的数。
2、调整区间
保证左区间所有数都<=x，右区间所有数都>=x。

3、分别对左右区间进行递归处理。

代码实现

//快速排序
//快速排序
#include <iostream>
using namespace std;void quick_sort(int q[],int left,int right)
{//如果只剩一元素则结束if (left == right) return;//定义左右指针int i = left -1;int j = right +1;//定义分界数int x = q[left];//如果ij没有相遇，继续偏移并适时交换值while (i<j){do i++; while(q[i]<x);do j-- ; while(q[j]>x);if(i<j) swap(q[i],q[j]);}//递归处理两边，此时ij相遇，取j为分界点quick_sort(q,left,j);quick_sort(q,j+1,right);
}int main()
{int arr[8] = {3, 5, 4, 2, 7, 1, 6,10};quick_sort(arr,0,7);for (int i = 0; i < 8; i++)printf("%d ", arr[i]);
}

备注

如果选择最右边的数为分界数，那么递归时需要使用的是i而不是j，否则有边界问题

    quick_sort(q,i,right);quick_sort(q,left,i-1);