快速排序JavaC++版实现，和其他复制粘贴的不一样，既简单又有一点点小技巧

• 原理
• 实现
• java 完整代码
• C/C++版本

快速排序体现的是一种分治的思想，它的核心思想是化整为零。每次在待排序列A[p…r]中去一个标杆，然后我们将这个序列划分为两部分，使得A[p…q…r]满足q左边的元素都小于或等于q，q右边的元素都大于q。然后我们在对A[p…q]和A[q…r]实行相同的操作，重复下去最终会得到排好序的序列。

语言描述的或许不是很清晰，而且大部分人应该都知道快速排序的原理，可能与本文所说的有出入，但是大致都差不多。
所以我们要实现快速排序首先需要实现一个子函数partition(A,p,r)，这个函数的作用是将数组A中的p到r的元素进行一个划分，一边划分为大于A[r]的，一边小于等于A[r]。
Java版代码

public static void swap(int[] a,int x,int y) {
		int tem = a[x];
		a[x] = a[y];
		a[y] = tem;
	}
	
	public static int partition(int[] a,int p,int r) {
		int i,j;
		int key = a[r];
		for(i=p-1,j=p;j 
在实现了子函数partition(A,p,r)之后，我们就可以写出递归版本的快速排序了。
 
	public static void sort(int []a,int p,int r) {
		if(p 
java 完整代码 
public class QuickSort {
	
	public static void swap(int[] a,int x,int y) {
		int tem = a[x];
		a[x] = a[y];
		a[y] = tem;
	}
	
	
	public static int partition(int[] a,int p,int r) {
		int i,j;
		int key = a[r];
		//这里用两个指针，i和j，i指向的是最新一个小于等于key的元素，j从p到r-1扫描整个数组中元素
		for(i=p-1,j=p;j 
C/C++版本 
其实这个版本是基于C写的，没有涉及c++的迭代器，模板等。还是很简单的，就为了代码的复用性用的是空指针传参数，其他的没啥亮点。相对于java版本的多了一个 int (*comp) 这个函数用来规定比较的方法，通过传入不同的比较函数可以实现对不同数据类型的按规则排序，比如降序我就不用再写一个新的方法了，只需要始兴县一个intLess()。然后注意到这里用了一点点优化，因为快速排序如果按照我们之前的思路实现的话会出现一个问题，如果partition()函数每次划分完毕后的序列大小不一致，那么我们的递归树会很深，这样会消耗很多时间，所以为了让时间递归树的深度相对降低一点我们做一点小技巧，每次不再取key = A[r]，而是key = A[rand(p,r)]。
 
 
#include
#include
#include
using namespace std;

//比较两个整型变量的大小，返回差值
int intGreater(void* a,void*b){
    return (*(int*)a-*(int*)b);
}
//打印数组
void pa(void *a,int size,int l){
    cout<<"a:";
    for(int i =0;i=0){
            i++;
            swap(A+i*size,A+j*size,4);
        }
    }
       free(key);
       //当扫描到r-1之后，此时的i指向了一个元素，这个元素应该是比key小的最后一个元素，那么key
       //应该被置于i+1这个位置。
        i++;
        swap(A+r*size,A+i*size,size);
        return i;
    }

//对p,q的子序列进行排序
void quickSort(void *A,int size,int p,int q,int(*comp)(void*,void*)){
    if(p