C++实现快速排序算法

快速排序算法，又称分区交换排序，基本思想原理：从被排序数据中选择一个轴值，将待排序记录划分成两个独立的部分，左边放的是小于轴值的数据，右边放的是大于轴值的数据。然后进行不断的递归，直到每部分只剩下一个数据为止。

现在我测试一组数据：14 23 12 43 5 7 15 10 3 70

这里我设两个变量 start 、end 分别指向待划分区间的最左边和最右边的位置

如这组数据 14 23 12 43 5 7 15 10 3 70

初始

start指向14的位置—0 ，end 指向 70的位置—9 取轴值 14
即start = 0 和 end = 9

从右边往左边扫描因为70>14 大小和位置关系符合，数据不变
14 23 12 43 5 7 15 10 3 70
此时end前移（end=8）

再把 3 和 14 比较

因为3 <14，大小和位置关系不符合，则交换 3 和 14 的位置，变成如下:

3 23 12 43 5 7 15 10 14 70
此时 start 后移（start=1）

再把 23 和 14 比较

因为23 >14，大小和位置关系不符合，则交换 23 和 14 的位置，变成如下:
3 14 12 43 5 7 15 10 23 70
此时 end 前移（end=7）

再把 10 和 14 比较

因为10 <14，大小和位置关系不符合，则交换 10 和 14 的位置，变成如下:

3 10 12 43 5 7 15 14 23 70
此时start 后移（start=2）

再把 12 和 14 比较

因为12 <14，大小和位置关系符合，数据不变，如下:

3 10 12 43 5 7 15 14 23 70
此时 start 后移（start=3）

再把 43 和 14 比较

因为43 >14，大小和位置关系不符合，则交换43 和 14 的位置，变成如下：

3 10 12 14 5 7 15 43 23 70
此时 end 前移（end=6）

再把 15 和 14 比较

因为15 >14，大小和位置符合，数据不变，如下：

3 10 12 14 5 7 15 43 23 70
此时end 前移（end=5）

再把 7 和 14 比较

因为7 <14，大小和位置不符合，交换 7 和14的位置，数据变成如下：

3 10 12 7 5 14 15 43 23 70
此时start 后移（start=4）

再把 5 和 14 比较

因为5 <14，大小和位置符合，数据不变，如下：

3 10 12 7 5 14 15 43 23 70
此时 start 后移（start=5）

此时 start=5，end=5 因为它们的值相等，所以这次的一次划分算法结束。

现在出现了两个分区，
待划分左分区 3 10 12 7
待划分右分区 15 43 23 70

再把这些分区如上算法进行递归，即可

下面是我的C++演示代码：

#include<iostream>  
using namespace std;  
void quick_sort(int a[],int,int);   
int parcition(int a[],int,int);
int main()  
{  
    int data[]={14,23,12,43,5,7,15,10,3,70},k;  
    int len=sizeof(data)/sizeof(int);  
    cout<<"未排序前数据:"<<endl;  
    for(k=0;k<len-1;k++){  
        cout<<data[k]<<",";
    }
    cout<<data[len-1];
    cout<<endl;  
    cout<<endl;
    cout<<endl;
    
    quick_sort(data,0,len-1);                            

    cout<<"排序后数据:"<<endl;  
    for(k=0;k<len-1;k++){  
        cout<<data[k]<<",";
    }
    cout<<data[len-1];
    cout<<endl;  
    system("pause");  
    return 0;  
}  

int parcition(int data[],int start,int end){       //快速排序一次划分算法
    int temp;                                      //给两个数交换使用的
    while(start<end){
        while(data[start]<=data[end] && start<end){
            end--;
        }
        if(start<end){
            temp = data[end];
            data[end] = data[start];
            data[start] = temp;
            start++;
        }
        while(data[start]<=data[end] && start<end){
            start++;
        }
        if(start<end){
            temp = data[end];
            data[end] = data[start];
            data[start] = temp;
            end--;
        }
    
    }
    return start;

}
  
void quick_sort(int s[], int start, int end)  
{  
    if(start<end){
        int center = parcition(s,start,end);
        quick_sort(s,start,center-1);
        quick_sort(s,center+1,end);
    
    }
     
}