Sort

sort.md

##Sort

• 算法导论版本

从左开始与pivot比较，左边始终是<=pivot的元素，使用随机化pivot版本

    int partition(int arr[], int begin, int end){
    	int pivot_index = rand() % (end - begin + 1) + begin;
    	swap(arr[pivot_index],arr[end]);
    	int pivot = arr[end];
    
    	int i = begin - 1;
    	for(int j = begin; j <= end - 1; ++j){
    		if(arr[j] <= pivot){
    			++i;
    			swap(arr[i],arr[j]);
    		}
    	}
    	++i;
    	swap(arr[i],arr[end]);
    	return i;
    }

sort的过程通过递归的调用partition过程

    void quick_sort(int arr[], int begin, int end){
    	if(begin < end){
    		int pivot = partition(arr,begin,end);
    		quick_sort(arr,begin,pivot-1);
    		quick_sort(arr,pivot+1,end);
    	}
    }

• STL版本

利用SGI STL的median of three法挑选pivot元素，使得复杂度不至于恶化至O(N^2) 迭代的过程使用STL __unguarded_partition的思想

    int __median(const int a,const int b,const int c){
    	if(a < b)
    		if(b < c)
    			return b;
    		else if(a < c)
    			return c;
    		else
    			return a;
    	else if(a < c)
    		return a;
    	else if (b < c)
    		return c;
    	else
    		return b;
    }
    int partition2(int arr[], int begin, int end){
    	int median_index = ((begin + (end - begin)) >> 1);
    	int pivot = __median(arr[begin],arr[median_index],arr[end]);
    	while(true){
    		while(arr[begin] < pivot ) ++begin;
    		while(arr[end] > pivot) --end;
    		if(!(begin < end)) return begin;
    		swap(arr[begin],arr[end]);
    	}
    }
    
    void quick_sort2(int arr[], int begin, int end){
    	if(begin < end){
    		int pivot = partition2(arr,begin,end);
    		quick_sort2(arr,begin,pivot-1);
    		quick_sort2(arr,pivot+1,end);
    	}
    }
    

• 链表快排

基于partition的思想，每次将链表分拆成小于pivot的左边和大于等于pivot的右边，然后递归调用

    /*
    struct ListNode{
        int val;
        ListNode* next;
        ListNode(int value):val(value),next(nullptr){};
    };
    */
    void list_quicksort(ListNode* first, ListNode* last){
    	if(first == nullptr || last == nullptr){
    		return;
    	}
    
    	if(first == last){
    		return;
    	}
    
    	ListNode* pivot = first;
    	ListNode* prev = first;
    	ListNode* slow = first;
    	ListNode* fast = first->next;
    
    	while(fast != nullptr){
    		if(fast->val < pivot->val){
    			prev = slow;
    			slow = slow->next;
    			swap(slow->val,fast->val);
    
    		}
    		fast = fast->next;
    	}
    	swap(slow->val,pivot->val);
    
    	list_quicksort(first,prev);
    	list_quicksort(slow->next,last);
    }