快速排序算法

算法一：快速排序##

快速排序算法是由东尼·霍尔所发展的一种排序算法。
在平均状况下，排序 n 个项目要Ο(n log n)次比较。
在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。
事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来.

快速排序的基本思想##

** 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。**

算法步骤##

1 从数列中挑出一个元素，称为 “基准”（pivot），
2 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

Paste_Image.png

代码：
          public class quickSort {  

    inta[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};  

          public quickSort(){  

                  quick(a);  

                  for(int i=0;i<a.length;i++)  

                  System.out.println(a[i]);  

      }  

          public  int getMiddle(int[] list, int low, int high) {     

                        int tmp = list[low];    //数组的第一个作为中轴     

                        while (low < high) {     

                                    while (low < high && list[high] >= tmp) {     

                                    high--;     

                          }     

                      list[low] = list[high];   //比中轴小的记录移到低端     

                      while (low < high && list[low] <= tmp) {     

                                low++;     

                        }     

                    list[high] = list[low];   //比中轴大的记录移到高端     

            }     

                   list[low] = tmp;              //中轴记录到尾     

                    return low;                   //返回中轴的位置     

            }    

        public   void _quickSort(int[] list, int low, int high) {     

                  if (low < high) {     

                              int middle = getMiddle(list, low, high);  //将list数组进行一分为二     

                              _quickSort(list, low, middle - 1);        //对低字表进行递归排序     

                             _quickSort(list, middle + 1, high);       //对高字表进行递归排序     

        }     

    }   

        public  void quick(int[] a2) {     

                    if (a2.length > 0) {    //查看数组是否为空     

                          _quickSort(a2, 0, a2.length - 1);     

                  }     

         }   

    }