快速排序算法

快速排序是一种非常高效的排序算法，它采用“分而治之”的思想，把大的拆分成小的，小的再拆分为更小的。

其原理如下：

对一组给定的记录，通过一趟排序后，将原序列分为两部分，其中前一部分的所有数据均比后一部分的所有的记录小，然后依次对前后两部分的记录进行快速排序，递归该过程，直到序列中的所有记录均有序为止。

快速排序的 Java 实现：

 1 package com.mianshi.easy;
 2 
 3 public class TestQuickSort {
 4 
 5     public static void quickSort(int[] a){
 6         sort(a, 0, a.length-1);
 7     }
 8     
 9     public static void sort(int[] a, int low, int high){
10         
11         int i, j;
12         int index;
13         
14         if(low >= high){
15             return;
16         }
17         
18         i = low;
19         j = high;
20         index = a[i];
21         while(i<j){
22             while(i<j && a[j]>=index){
23                 j--;
24             }
25             if(i<j)
26                 a[i++] = a[j];
27             while(i<j && a[i]<index){
28                 i++;
29             }
30             if(i<j){
31                 a[j--]=a[i];
32             }
33         }
34         a[i] = index;
35         sort(a, low, i-1);
36         sort(a, i+1, high);
37     }
38     
39     
40     public static void main(String[] args) {
41         
42         int[] a = {6,5,3,9,0,5,1,2,4,7,8};
43         //快速排序
44         quickSort(a);
45         for(int i = 0;i < a.length; i++){
46             System.out.print(a[i]+" ");
47         }
48     }
49     
50 
51 
52 }

View Code

结果：

0 1 2 3 4 5 5 6 7 8 9

算法稳定性：不稳定的排序算法。

时间复杂度：平均时间复杂度为O(nlogn)

优秀帖子帮助理解：

http://blog.csdn.net/morewindows/article/details/6684558