快速排序模板（循环+递归）

朴灿烈づ我的快乐病毒、 2023-02-16 05:59 27阅读 0赞

快速排序是对冒泡排序的一种改进。  
它的基本思想是：通过一次排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归或者非递归进行，以此达到整个数据变成有序序列。

快排实现方式：循环+递归

#include<cstdio>
    #include<string.h>
    #define ll long long
    using namespace std;
    int n;
    ll arr[100010];
    
    void swaps(int a, int b){ 
    	int tmp = arr[a];
    	arr[a] = arr[b];
    	arr[b] = tmp;
    }
    
    void qsort(int begin, int end){ 
    	if(begin>=end) return;
    	
    	int l=begin, r=end;		//边界 
    	int tmp=arr[begin];		//基准 
    	do{ 
    		while(arr[l]<tmp) l++;
    		while(arr[r]>tmp) r--;
    		if(l<=r){ 
    			swaps(l, r);
    			l++;
    			r--;
    		}
    	}while(l<=r);
    	
    	//分治 
    	qsort(begin, r);
    	qsort(l, end);	
    }
    
    
    int main(){ 
    	memset(arr, 0, sizeof(arr));
    	scanf("%d", &n);
    	for(int i=0; i<n; i++) scanf("%lld", &arr[i]);
    	qsort(0, n-1);
    	for(int i=0; i<n; i++) printf("%lld ", arr[i]);
    	return 0;
    }

--------------------

值得注意的是取基准值最好不要有序的取（例如从区间的开头取或从结尾取）。  
当数组顺序是从大到小而快排要实现从小到大的排序，按顺序取基准值会导致**元素替换次数增多**。

改良方案：为了使每次基准都在合适的区间内，可以修改上述代码中的基准为

int tmp=arr[(begin+end)/2];		//基准

这样一来既能使基准在begin~end的范围内，又可以将取基准的顺序打乱。  
[洛谷测试平台][Link 1]

经典递归实现快排  
（以区间第一个为基准）

#include<cstdio>
    #include<string.h>
    #define ll long long
    using namespace std;
    int n;
    ll arr[100010];
    
    void swaps(int a, int b){ 
    	int tmp = arr[a];
    	arr[a] = arr[b];
    	arr[b] = tmp;
    }
    
    //只排一个元素 
    int p(int begin, int end){ 
    	if(begin>=end) return begin;
    	
    	//每次都以区间第一个元素为基准
    	if(arr[begin]>arr[begin+1]){ 	
    		swaps(begin+1, begin);
    		return p(begin+1, end);
    	}
    	else if(arr[begin]==arr[begin+1]){ 
    		return p(begin+1, end);
    	}
    	else{ 
    		swaps(begin+1, end);
    		return p(begin, end-1);
    	}
    }
    
    
    void f(int begin, int end){ 
    	if(begin>=end){ 
    		return;
    	}
    	//a为已排好序元素的下标 
    	int a = p(begin, end);
    	//分治 
    	f(begin, a-1);
    	f(a+1, end);	
    	return;
    }
    
    
    int main(){ 
    	scanf("%d", &n);
    	memset(arr, 0, sizeof(arr));
    	for(int i=0; i<n; i++){ 
    		scanf("%lld", &arr[i]);
    	}
    	f(0, n-1);
    	for(int i=0; i<n; i++){ 
    		printf("%lld ", arr[i]);
    	}
    	return 0;
    }

ps:  
递归与循环那种方式更高效？  
循环更高效，实现逻辑简单相比于递归简单。

递归调用函数中的变量的压栈、出栈操作，如果递归的层次太多肯定会导致内存溢出、系统崩溃。例如：计算 n !，如果 n 太大了的话，就不能够使用递归的方法来实现了。

递归好处：编写代码简单，程序可读性好。

[Link 1]: https://www.luogu.com.cn/problem/P1177