快速排序
思想(分治思想)
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);
更多推荐
算法,快速
发布评论