1 #include
     
       2 using namespace std; 3 int quick_sort(int (&a)[1000],int low,int high){    //一趟快速排序,快排的核心!!! 4     int key=a[low]; 5     a[0]=a[low]; //临时存放枢轴的元素值 6     while(low
      
       =key) high--; 8         a[low]=a[high]; 9         while(low
       
        <=key) low++;10         a[high]=a[low];11     }12     a[low]=a[0];13     return low;   //返回枢轴的位置14 }15 void QuickSort(int (&a)[1000],int low,int high){   //快速排序16     if(low
        
         high){24         return -1; //说明没有找到元素,返回-125     }26     int mid=(low+high)/2;27     if(a[mid]==value){28         return mid; //说明查找到了元素所在下标并且返回29     }else if(a[mid]
         
          >n;38     for(int i=1;i<=n;i++){39         cin>>a[i];40     }41     QuickSort(a,1,n);42     cout<<"按从小到大快速排序后的序列为: "<
          
           >value){ //输入value,能够多次查询,ctrl+z 结束输入49 int ans=Binary_search(a,1,n,value); //进行折半查找算法50 if(ans==-1) cout<<"未查找到值 "<
           
            <
           
          
         
        
       
      
     

 

快排的核心思想就是枢轴左边要么都是比它值大的，要么就是都是值比它小的，右边同理。

快排最优的时间复杂度为O(n*logn)，最坏情况为要么全是逆序或者正序，时间复杂度为O(n*n)，根据推导，平均时间复杂度为O(n*logn)。

就空间复杂度来说，主要是递归造成的栈空间的使用，最好情况，递归树的深度为log2n，其空间复杂度也就为O(logn)，最坏情况，需要进行n‐1递归调用，其空间复杂度为O(n)，平均情况，空间复杂度也为O(logn)。

折半查找就是二分