c/c++Qsort函数

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以 递归进行，以此达到整个数据变成有序 序列。

快排在排序算法中效率相对较高，但是使用的人却不多，大家一般使用的是相对简单但效率低下的冒泡排序

冒泡排序的时间复杂度为O（n*n）；

但是快排的时间复杂度为O(n*logn);  //如果数据较大的话，可以很容易看出快排比冒泡排序效率高太多

冒泡排序的空间复杂度为O(1);

最优的空间复杂度为：O(logn)  ；每一次都平分数组的情况

最差的时间复杂度为：O( n )  ；退化为冒泡排序的情况

#include <bits/stdc++.h>
using namespace std; 
void Qsort(int a[],int low,int high) {
    if(low>=high) { return; } //终止条件  当左指标大于或等于右指标，返回   
    int first=low;   //first等于区间第一个元素下标 
    int last=high;   //last等于区间第二个元素下标 
    int key=a[first];   //将区间中左边第一个元素值给key   
    while(first<last) {   
     while(first<last&&a[last]>=key) {   //从区间最右边开始遍历  如果a[last]小于key  跳出循环 
      --last; } 
      a[first]=a[last];     //将小于key的放在区间左边   大于key的放在右边 
      while(first<last&&a[first]<=key) {   //first右移遍历  找到a[first]大于key  将其和a[last]交换 
       ++first; } 
       a[last]=a[first];    
        } 
        a[first]=key;    //循环遍历完后  将key放回数组  
        Qsort(a,low,first-1); //将数组分成两个区间  左区间右区间进行递归调用 
        Qsort(a,first+1,high); 
 } 
int main() { 
  int a[10];
  for(int i=0;i<10;i++){
  	scanf("%d",&a[i]);   //输入数组 
  }
  Qsort(a,0,sizeof(a)/sizeof(a[0])-1);  //传递数组a地址和第一个元素下标   最后一个指针下标  
  for(int i=0;i<sizeof(a)/sizeof(a[0]);i++) {   //打印数组 
   printf("%d ",a[i]) ;} 
   return 0; 
   }