C语言 快速排序

基本思路：递归分治
1.可以将数组首元素设定为基准点（基准元素），设begin代表第一个元素，end代表最后一个元素。
2.从第二个元素开始遍历数组，分成比基准元素大或小的两部分，再将基准元素交换至某个位置，使得左侧元素都比它小，右侧元素都比它大。
3.将基准元素两侧的两部分分别采取上述相同的操作，这不免联想到递归。
下面是相关代码

#include<bits/stdc++.h>
using namespace std;

void display(int array[],int n)//打印数组中的数据
{
for(int i=0;i<n;i++)
{
cout<<array[i]<<’ ';
}
cout<<endl;
}

void swap(int *a,int b)//交换数组中两元素的值
{
int temp;//千万不能写成temp

temp=*a;
*a=*b;
*b=temp;

}

void quick_sort(int array[],int begin,int end)
{
int i,j;

if(begin<end)
{
i=begin+1;
j=end;

//遍历数组
while(i<j)//循环结束时，一定是i=j，不会存在i>j的情况
{
    if(array[i]>array[begin])
    {
        swap(&array[i],&array[j]);
        j--;
    }
    else
    {
        i++;
    }
}


if(array[i]>=array[begin])//将begin处元素交换位置，使左侧元素均比它小，右侧元素均比它大
{
    i--;
}

swap(&array[begin],&array[i]);
quick_sort(array,begin,i);//递归
quick_sort(array,j,end);//递归
}

}

int main()
{
int array[10]={17,29,50,10,49,70,100,1,58,40};//定义初始数组
cout<<“初始数据”<<endl;
display(array,10);
quick_sort(array,0,9);//调用快排函数
cout<<“快排后数据”<<endl;
display(array,10);
return 0;
}