快排的迭代，递归实现及其优化

男娘i 2022-12-06 15:54 152阅读 0赞

## 快排的思想 ##

首先 **快排是一种比较排序**。  
具体思想是 选出一个基准值，通过比较找出待排序区间中基准值该放置的位置。  
**实现逻辑**：

*  先从数列中取出一个数作为基准数(通常取第一个数)。
 *  分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
 *  再对左右区间重复第二步，直到各区间只有一个数。

## 分区的三种方式 ##

**通常有三种方式来进行基准数的左右分区**。

1.  左右指针法。
2.  挖坑法
3.  前后指针法。

左右指针实现：

//左右指针法
    int PartSort(int* a, int begin, int end) {
        // 降序
    	int key = a[end];
    	int index = end;
    	while (begin < end){
        
    		while(begin < end && a[begin] <= key){
        
    			++begin;
    		}
    		while(begin < end && a[end] >= key){
        
    			--end;
    		}
    		swap(a[begin], a[end]);
    	}
    	swap(a[begin], a[index]);
    	return begin;
    }

挖坑法实现：

//挖坑法
    int PartSort2(int* a, int begin, int end) {
        //降序
    	int key = a[end];
    	while (begin < end){
        
    		while(begin < end && a[begin] <= key){
        
    			++begin;
    		}
    		a[end] = a[begin];
    		while (a[begin] < a[end] && a[end] >= key){
        
    			--end;
    		} 
    		a[begin] = a[end];
    	}
    	a[begin] = key;
    	return begin;
    }

前后指针法实现：

//前后指针法 思路cur一直向前走遇到小的就置换到前面 这样一来 一次循环 就达到目的
    int PartSort3(int* a, int begin, int end) {
        //降序
    	int key = a[end];
    	int prev = begin - 1;
    	int cur = begin;
    	while (cur < end){
        
    		if (a[cur] < key && ++prev != cur) {
        
    			swap(a[cur], a[prev]);
    		}
    		++cur;
    	}
    	++prev;
    	swap(a[prev], a[end]);
    	return prev;
    }

## 递归与非递归实现 ##

递归：

void QuickSort(int* a, int begin, int end) {
        
    	if (begin >= end){
        
    		return;
    	}
    	int mid = PartSort(a, begin, end);//也可以写进函数内部
    	QuickSort(a, begin, mid-1);
    	QuickSort(a, mid+1, end);
    }

迭代：

void QuickOfStack(int* a, int n) {
        
    	int begin = 0;
    	int end = n-1;
    	stack<int> s1;
    	s1.push(begin);
    	s1.push(end);
    	while(!s1.empty()) {
        
    		int right = s1.top();
    		s1.pop();
    		int left = s1.top();
    		s1.pop();
    		int mid = PartSort(a, left, right);
    		if (left < mid-1) {
        
    			s1.push(left);
    			s1.push(mid-1);	
    		}
    		if (mid+1 < end){
        
    			s1.push(mid+1);
    			s1.push(right);
    		}
    	}
    }

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

## 快排的优化 ##

快排的平均时间复杂度是O(nlogn), 但是最坏的情况下，也就是有序的情况下回达到n^2的复杂度，因此我们考虑快排进行优化。为了避免有序情况下每次都取到最大值或者最小值。因此提出了**三数取中**的方法。

int SelectMid(int* a, int begin, int end) {
        //返回中间大小的下标
    	int mid = (begin+end) >> 1;
    	if (a[begin] >= a[mid] && a[mid] >= a[end]) {
        
    		return mid;
    	}else if (a[mid] >= a[begin] && a[begin] >= a[end]) {
        
    		return begin;
    	}
    	return end;
    }

稳定性： 快排是一种不稳定的算法。  
时间复杂度：O(nlogn)  
空间复杂度：O(logn)