程序员必知必会的排序二：快速排序

快速排序时间复杂度

快速排序的时间复杂度在最坏情况下是O(N2)，平均的时间复杂度是O(N*lgN)。

这句话很好理解：假设被排序的数列中有N个数。遍历一次的时间复杂度是O(N)，需要遍历多少次呢？至少lg(N+1)次，最多N次。

(01) 为什么最少是lg(N+1)次？快速排序是采用的分治法进行遍历的，我们将它看作一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是lg(N+1)。因此，快速排序的遍历次数最少是lg(N+1)次。

(02) 为什么最多是N次？这个应该非常简单，还是将快速排序看作一棵二叉树，它的深度较大是N。因此，快读排序的遍历次数最多是N次。

快速排序实现

快速排序C实现

实现代码(quick_sort.c)

/** 

* 快速排序：C 语言 
* 
* @author skywang 
* @date 2014/03/11 
*/ 
#include <stdio.h> 
// 数组长度 
#define LENGTH(array) ( (sizeof(array)) / (sizeof(array[0])) ) 
/* 
* 快速排序 
* 
* 参数说明： 
* a -- 待排序的数组 
* l -- 数组的左边界(例如，从起始位置开始排序，则l=0) 
* r -- 数组的右边界(例如，排序截至到数组末尾，则r=a.length-1) 
*/ 
void quick_sort(int a[], int l, int r) 
{ 
if (l < r) 
{ 
int i,j,x; 
i = l; 
j = r; 
x = a; 

while (i < j) 
{ 
while(i < j && a[j] > x) 
j--; // 从右向左找第一个小于x的数 
if(i < j) 
a[i++] = a[j]; 
while(i < j && a < x) 

i++; // 从左向右找第一个大于x的数 
if(i < j) 
a[j--] = a; 

} 
a = x; 

quick_sort(a, l, i-1); /* 递归调用 */ 
quick_sort(a, i+1, r); /* 递归调用 */ 
} 
} 
void **in() 
{ 
int i; 
int a[] = {30,40,60,10,20,50}; 
int ilen = LENGTH(a); 
printf("before sort:"); 
for (i=0; i<ilen; i++) 
printf("%d ", a); 

printf("\n"); 
quick_sort(a, 0, ilen-1); 
printf("after sort:"); 
for (i=0; i<ilen; i++) 
printf("%d ", a); 

printf("\n"); 
}

/** 

* 快速排序：C++ 
* 
* @author skywang 
* @date 2014/03/11 
*/ 
#include <iostream> 
using namespace std; 
/* 
* 快速排序 
* 
* 参数说明： 
* a -- 待排序的数组 
* l -- 数组的左边界(例如，从起始位置开始排序，则l=0) 
* r -- 数组的右边界(例如，排序截至到数组末尾，则r=a.length-1) 
*/ 
void quickSort(int* a, int l, int r) 
{ 
if (l < r) 
{ 
int i,j,x; 
i = l; 
j = r; 
x = a; 

while (i < j) 
{ 
while(i < j && a[j] > x) 
j--; // 从右向左找第一个小于x的数 
if(i < j) 
a[i++] = a[j]; 
while(i < j && a < x) 

i++; // 从左向右找第一个大于x的数 
if(i < j) 
a[j--] = a; 

} 
a = x; 

quickSort(a, l, i-1); /* 递归调用 */ 
quickSort(a, i+1, r); /* 递归调用 */ 
} 
} 
int **in() 
{ 
int i; 
int a[] = {30,40,60,10,20,50}; 
int ilen = (sizeof(a)) / (sizeof(a[0])); 
cout << "before sort:"; 
for (i=0; i<ilen; i++) 
cout << a << " "; 

cout << endl; 
quickSort(a, 0, ilen-1); 
cout << "after sort:"; 
for (i=0; i<ilen; i++) 
cout << a << " "; 

cout << endl; 
return 0; 
}

/** 

* 快速排序：Java 
* 
* @author skywang 
* @date 2014/03/11 
*/ 
public class QuickSort { 
/* 
* 快速排序 
* 
* 参数说明： 
* a -- 待排序的数组 
* l -- 数组的左边界(例如，从起始位置开始排序，则l=0) 
* r -- 数组的右边界(例如，排序截至到数组末尾，则r=a.length-1) 
*/ 
public static void quickSort(int[] a, int l, int r) { 
if (l < r) { 
int i,j,x; 
i = l; 
j = r; 
x = a; 

while (i < j) { 
while(i < j && a[j] > x) 
j--; // 从右向左找第一个小于x的数 
if(i < j) 
a[i++] = a[j]; 
while(i < j && a < x) 

i++; // 从左向右找第一个大于x的数 
if(i < j) 
a[j--] = a; 

} 
a = x; 

quickSort(a, l, i-1); /* 递归调用 */ 
quickSort(a, i+1, r); /* 递归调用 */ 
} 
} 
public static void **in(String[] args) { 
int i; 
int a[] = {30,40,60,10,20,50}; 
System.out.printf("before sort:"); 
for (i=0; i<a.length; i++) 
System.out.printf("%d ", a); 

System.out.printf("\n"); 
quickSort(a, 0, a.length-1); 
System.out.printf("after sort:"); 
for (i=0; i<a.length; i++) 
System.out.printf("%d ", a); 

System.out.printf("\n"); 
} 
}