剑指offer 快速排序-白红宇

剑指offer 快速排序

阅读量：6914 次

发布时间：2019-06-27

本文共 1624 字，大约阅读时间需要 5 分钟。

　　题目链接：剑指offer

　　题目描述：快速排序

　　解题思路：快速排序

　　代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #include 
                 
                  #include 
                  
                   #define lson l, m, rt<<1#define rson m+1, r, rt<<1|1#define mem0(a) memset(a,0,sizeof(a))#define mem1(a) memset(a,-1,sizeof(a))#define sca(x) scanf("%d",&x)#define de printf("=======\n")typedef long long ll;using namespace std;int RandomInRange(int s, int e) { return rand() % (e-s+1) + s;}void swap(int &a, int &b) { int temp = a; a = b; b = temp;}int Partition(int data[], int len, int start, int end) { if( data == NULL || len <= 0 || start < 0 || end >= len ) { throw new std::exception(); } int index = RandomInRange(start, end); if( index != end ) swap(data[index], data[end]); int small = start-1; for( int index = start; index < end; index++ ) { if( data[index] < data[end] ) { small++; if( small != index ) { swap(data[small], data[index]); } } } small++; swap(data[small], data[end]); return small;}void QuickSort(int data[], int len, int start, int end) { if(start == end) return; int index = Partition(data, len, start, end); if( index > start ) { QuickSort(data, len, start, index-1); } if( index < end ) { QuickSort(data, len, index+1, end); }}int main() { int data[10] = { 134,32,13,510,5,5,7,78,96,15}; QuickSort(data, 10, 0, 9); for( int i = 0; i < 10; i++ ) { cout << data[i] << " "; } cout << endl; return 0;}