#快速排序
快速排序就是将一个需要排序的数组A[ a0,…,a(n-1)]顺序排列输出,首先从数组中随便找到一个元素x,然后将小于这个元素x的所有元素放到这个元素左边,将大于这个元素x的所有元素放到这个元素的右边,最后运用递归再对x左边和右边的元素进行快速排序,最后就可以将这个数组成功排序
具体如下:
数组A[ a0,a1,a2,…,a(n-3),a(n-2),a(n-1)],我们设两个变量i,j 。i=0,j=n-1;
然后i向后搜索,j向前搜索,找到第一个ai>r,aj<r,两个元素互换位置。然后依次方法,i继续向后搜索,j继续向后搜索。直到i>=j,结束。此时元素r左边全是小于r的元素,右边全是大于r的元素。然后我们再用此方法对左边和右边的元素快速排序。
代码实现如下:
void change(int arr[],int L,int R){
//L代表最左边 R代表最右边
int i=L;
int j=R;
int r=arr[(L+R)/2];//取中间位置的元素
while(i<=j){
while(arr[i]<=r){
i++;
}
while(arr[j]>=r){
j--;
}
if(i<=j){//交换位置
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
//递归继续排序
if(L<j){
change(arr[],L,j);
}
if(i<R){
change(arr[],i,R)
}
}