Java实现快速排序的代码教程，java排序教程

Java实现快速排序的代码教程，java排序教程

一、快速排序的思想

　　基于分治的思想，是冒泡排序的改进型。首先在数组中选择一个基准点（该基准点的选取可能影响快速排序的效率，后面讲解选取的方法），然后分别从数组的两端扫描数组，设两个指示标志（lo指向起始位置，hi指向末尾)，首先从后半部分开始，如果发现有元素比该基准点的值小，就交换lo和hi位置的值，然后从前半部分开始扫秒，发现有元素大于基准点的值，就交换lo和hi位置的值，如此往复循环，直到lo>=hi,然后把基准点的值放到hi这个位置。一次排序就完成了。以后采用递归的方式分别对前半部分和后半部分排序，当前半部分和后半部分均有序时该数组就自然有序了。

排序过程：

二、下面我们来看一个具体的例子：

下面我们通过一个案例来演示一下快速排序的基本步骤： 以序列 46 30 82 90 56 17 95 15 共8个元素

　　　　初始状态： 46 30 82 90 56 17 95 15 选择46 作为基准值，i = 0， j = 7

　　　　　　　　　　　i = 0 j = 7

　　　　　　1530 82 90 56 17 954615 < 46， 交换 15 和 46，移动 i， i = 1

　　　　　　　　　　　　　i =1 j = 7

　　　　　　　　　　 1530 82 90 56 17 954630 < 46， 不需要交换，移动 i， i = 2

　　　　　　　　　　　　　　　i =2 j = 7

　　　　　　　　　　 153046 90 56 17 958282> 46， 交换82 和 46，移动j，j = 6

　　　　　　　　　　　　　　　i =2 j = 6

　　　　　　　　　　 153046 90 56 17 958295> 46， 不需要交换，移动j，j = 5

　　　　　　　　　　　　　　　i =2 j = 5

　　　　　　　　　　 1530 17 90 5646958217< 46， 交换46 和 17，移动i，i = 3

　　　　　　　　　　　　　　　　　i =3 j = 5

　　　　　　　　　　 1530 1746 5690958290> 46， 交换90 和 46，移动j，j = 4

　　　　　　　　　　　　　　　3 = ij = 4

　　　　　　　　　　 1530 1746 5690958256> 46， 不需要交换，移动j，j = 3

　　　　　　　　　　　　　　　 i=j = 3

　　　　

　　　　i = j = 3， 这样序列就这样分割成了两部分，左边部分{15， 30， 17} 均小于 基准值（46）；右边部分 {56， 90，95，82}，均大于基准值。这样子我们就达到了分割序列的目标。在接着对子序列用同样的办法进行分割，直至子序列不超过一个元素，那么排序结束，整个序列处于有序状态。

三、快速排序算法的实现：

public static 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 static 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);//对高字表进行递归排序
    }
}

所谓的中轴的位置就是选择的那个基准数所在的位置。

使用的时候直接调用_quickSort方法即可，low为数组的第一个元素的下标0，high为数组的最后一个元素的下标a.length-1。

快速排序的时间复杂度为O(NlogN)。