排序：快速排序

  1 import java.util.Arrays;
  2 import java.util.Stack;
  3 
  4 
  5 public class QuickSort {
  6     
  7     
  8     public static void main(String[] args) {
  9         int[] arr = {72, 6, 57, 88, 60, 42, 83, 73, 48, 85} ;
 10 //        quickSort(arr, 0, arr.length-1) ;
 11         quickSort(arr) ;
 12         System.out.println(Arrays.toString(arr)) ;
 13     }
 14     
 15     /**
 16      * 递归方式实现快速排序
 17      * @param s
 18      * @param l
 19      * @param r
 20      */
 21     private static void quickSort(int[] s, int l, int r) {
 22         if(l >= r) {
 23             return ;
 24         }
 25         
 26         int i = l ;
 27         int j = r ;
 28         int x = s[l] ;
 29         
 30         while(i < j) {
 31             while(i < j && x <= s[j]) {
 32                 j-- ;
 33             }
 34             if(i < j) {
 35                 s[i++] = s[j] ;
 36             }
 37             
 38             while(i < j && x > s[i]) {
 39                 i++ ;
 40             }
 41             if(i < j) {
 42                 s[j--] = s[i] ;
 43             }
 44         }
 45         
 46         s[i] = x ;
 47         quickSort(s, l, i-1) ;
 48         quickSort(s, i+1, r) ;
 49     }
 50     
 51     /**
 52      * 非递归方式实现快速排序
 53      * @param s
 54      */
 55     private static void quickSort(int[] s) {
 56         Stack<Note> stack = new Stack<Note>() ;
 57         
 58         int l = 0 ;
 59         int r = s.length - 1 ;
 60         
 61         int i ;
 62         int j ;
 63         int x ;
 64         
 65         stack.push(new Note(l, r)) ;
 66         
 67         while(!stack.empty()) {
 68             l = stack.peek().l ;
 69             r = stack.peek().r ;
 70             
 71             i = l ;
 72             j = r ;
 73             
 74             stack.pop() ;
 75             
 76             if(l >= r) {
 77                 continue;
 78             }
 79             
 80             x = s[i] ;
 81             
 82             
 83             while(i < j) {
 84                 while(i < j && x <= s[j]) {
 85                     j-- ;
 86                 }
 87                 if(i < j) {
 88                     s[i++] = s[j] ;
 89                 }
 90                 
 91                 while(i < j && x > s[i]) {
 92                     i++ ;
 93                 }
 94                 if(i < j) {
 95                     s[j--] = s[i] ;
 96                 }
 97             }
 98             
 99             s[i] = x ;
100             
101             stack.push(new Note(l, i-1)) ;
102             stack.push(new Note(i+1, r)) ;
103         }
104         
105     }
106     
107     private static class Note {
108         public int l ;
109         public int r ;
110         public Note(int l, int r) {
111             super();
112             this.l = l;
113             this.r = r;
114         }
115     }
116     
117 }


自己整理了一下，具体细节就不说了，参考博客：http://www.cnblogs.com/morewindows/archive/2011/08/13/2137415.html