在网上搜了很多答案，但是还是不明白什么是快速排序？求大神帮忙详细讲解一下快速排序，并给个代码

快速排序是对普通排序的改进：
下面是稳定的快速排序，C语言版
int cmp(const void *x, const void *y)
{
        if((*(node *)x).a==(*(node *)y).a)
                return (*(node *)x).id>(*(node *)y).id?1:-1;
        else
                return (*(node *)x).a<(*(node *)y).a?1:-1;
}

快速排序（Quicksort）是对冒泡排序的一种改进。

1. import java.util.Arrays;
   
2. 
   
3. public class QuickSort {
   
4.         public static void main(String[] ary) {
   
5.                 int[] arry = { 49, 38, 65, 97, 76, 13, 27 };
   
6.                 sort(arry, 0, arry.length - 1);
   
7.         }
   
8. 
   
9.         /**
   
10.          * 一次排序单元，完成此方法，key左边都比key小，key右边都比key大。
    
11.          *
    
12.          * @param array
    
13.          *            排序数组
    
14.          * @param low
    
15.          *            排序起始位置
    
16.          * @param high
    
17.          *            排序结束位置
    
18.          * @return 单元排序后的数组
    
19.          */
    
20.         private static int sortUnit(int[] array, int low, int high) {
    
21.                 int key = array[low];
    
22.                 while (low < high) {
    
23.                         // 从后向前搜索比key小的值
    
24.                         while (array[high] >= key && high > low)
    
25.                                 --high;
    
26.                         // 比key小的放左边
    
27.                         array[low] = array[high];
    
28.                         // 从前向后搜索比key大的值，比key大的放右边
    
29.                         while (array[low] <= key && high > low)
    
30.                                 ++low;
    
31.                         // 比key大的放右边
    
32.                         array[high] = array[low];
    
33.                         System.out.println(low + "," + high);
    
34.                 }
    
35.                 // 左边都比key小，右边都比key大。将key放在游标当前位置。此时low等于high
    
36.                 array[high] = key;
    
37.                 System.out.println(Arrays.toString(array));
    
38.                 return high;
    
39.         }
    
40. 
    
41.         /**
    
42.          * 快速排序
    
43.          *
    
44.          * @param arry
    
45.          * @return
    
46.          */
    
47.         public static void sort(int[] array, int low, int high) {
    
48.                 if (low >= high) {
    
49.                         return;
    
50.                 }
    
51.                 // 完成一次单元排序
    
52.                 int index = sortUnit(array, low, high);
    
53.                 // 对左边单元进行排序
    
54.                 sort(array, low, index - 1);
    
55.                 // 对右边单元进行排序
    
56.                 sort(array, index + 1, high);
    
57.         }
    
58. }

复制代码

设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。
一趟快速排序的算法是：
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即 key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索（j -- ），找到第一个小于key的值A[j]，A与A[j]交换；
4）从i开始向后搜索，即由前开始向后搜索（i ++ ），找到第一个大于key的A，A与A[j]交换；
5）重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后令循环结束。）
示例
待排序的数组A的值分别是：（初始关键数据：key=49） 注意关键key永远不变，永远是和key进行比较，无论在什么位置，最后的目的就是把key放在中间，小的放前面大的放后面。

进行第一次交换后：27 38 65 97 76 13 49
( 按照算法的第三步从后面开始找，此时:J=6）
进行第二次交换后：27 38 49 97 76 13 65
( 按照算法的第四步从前面开始找>key的值，65>49,两者交换，此时：I=2 )
进行第三次交换后：27 38 13 97 76 49 65
( 按照算法的第五步将又一次执行算法的第三步从后开始找
进行第四次交换后：27 38 13 49 76 97 65
( 按照算法的第四步从前面开始找大于key的值，97>49，两者交换，此时：I=3,J=5 )
此时再执行第三步的时候就发现I=J=3，从而结束一趟快速排序，那么经过一趟快速排序之后的结果是：27 38 13 49 76 97 65，即所有大于key49的数全部在49的后面，所有小于key（49）的数全部在key（49）的前面。
还要不懂可以参考这个舞蹈。http://v.youku.com/v_show/id_XMzMyODk4NTQ4.html

快速排序是综合性能最好的一种排序，它的基本思想是：
分治法
即把待排序序列分而治之，划成很多小序列进行排序。
实现过程，首先可以在序列中选一个元素作为基准元素pivotkey，一般选定为第一个，在这里设为pivotkey=arr[low]，其中low定义为每个划分序列的最低位置，high为每次划分序列的最高位置。
然后拿最低位的元素和这个基准元素比较，如果最低位的元素比基准小，那么low++
直到比基准元素大，这时把low位置上的元素和high位置上的元素互换
然后拿基准元素和最高位比较，如果基准元素小，那么high--，否者再把low位置元素和high位置元素互换。直到什么时候结束呢？肯定是直到low>=high的时候，然后返回一个位置low
上面说的是一趟排序。
返回一个low后，我们就知道，low位置左边的元素都比基准元素小，low右边的元素都比基准元素大。这样，我们就得到了左右两边的序列，两边都不再包含基准元素
然后利用上面的方法在同样处理得到的两个序列。知道最后划分的序列只有一个元素。
其中用到了递归算法。
下面是代码？是我自己从c语言上修改过来的，你可以看看
希望能帮助你！

1. class  QSort
   
2. {
   
3.         public static void main(String[] args)
   
4.         {
   
5.                 int[] arr = {5,1,6,4,2,8};
   
6.                 System.out.println("排序前：");
   
7.                 printarray(arr);
   
8. 
   
9.                 int num=arr.length;
   
10. 
    
11.                 QSort(arr,0,num-1);
    
12.                 System.out.println("排序后：");
    
13.                 printarray(arr);
    
14.         }
    
15.         public static void printarray(int[] arr)
    
16.         {
    
17.                 System.out.print("[");
    
18.                 for(int i=0;i<arr.length;i++)
    
19.                 {
    
20.                         if (i!=arr.length-1)
    
21.                         System.out.print(arr[i]+", ");
    
22.                         else
    
23.                         System.out.println(arr[i]+"]");
    
24.                 }//for
    
25.         }
    
26. 
    
27.         public static int Partition(int[] arr,int low,int high)
    
28.         {
    
29.                 int pivotkey;
    
30.                 pivotkey = arr[low];
    
31.                 while(low<high)
    
32.                 {
    
33.                         while(low<high&&arr[high]>=pivotkey)
    
34.                                 high--;
    
35.                         arr[low] = arr[high]; //将比枢轴小的移到低端
    
36.                         while(low<high&&arr[low]<=pivotkey)
    
37.                                 low++;
    
38.                         arr[high] = arr[low]; //将比枢轴大的移到高端
    
39.                
    
40.                 }
    
41.                 arr[low] = pivotkey;
    
42.                 return low;
    
43.         }
    
44. 
    
45.         public static void QSort(int [] arr,int low,int high)
    
46.         {
    
47.                 int pivotloc;
    
48.                 if(low<high)
    
49.                 {
    
50.                         pivotloc = Partition(arr,low,high);
    
51.                         QSort(arr,low,pivotloc-1); //递归的调用，实现排序。
    
52.                         QSort(arr,pivotloc+1,high);
    
53.                 }
    
54.                
    
55.         }
    
56. 
    
57. }
    
58. 
    

复制代码

快速排序的动画演示