课程咨询 :186 8716 1620      qq:2066486918

昆明Java培训 > 达内新闻 > 快速排序(QuickSort)-Java实现
  • 快速排序(QuickSort)-Java实现

    发布:昆明Java培训      来源:达内新闻      时间:2016-10-21

  • 昆明Java培训的老师先给大家讲讲快速排序的背景。

    快速排序,是在上世纪60年代,由美国人东尼·霍尔提出的一种排序方法。这种排序方式,在当时已经是非常快的一种排序了。因此在命名上,才将之称为“快速排序”。这个算法是二十世纪的七大算法之一,平均情况下时间复杂度为Ο(nlogn),而且在O(nlogn)的情况下,实际的运算速度都要快于其他同时间复杂度的排序方法。

    排序思想

    快速排序的思路想到很困难,但是理解起来却非常容易

    他的思路是这样的:

    1、先选定队列中,某一个元素为基数Value(一般选择头元素,或尾元素)。

    2、将基数Value依次与所有元素比较大小。按照比较结果将元素分为两个队列A、B。一个所有元素比基数Value大,一个所有元素比基数Value小。

    3、将A作为新的队列,再次选定基数,然后分成两个更小的队列

    4、就这样一直将每一个小的队列无限的拆分成更小的两个队列。

    5、一直到一个队列已经拆分成不能拆封为止(也就是一个元素)

    6、因为队列之间的顺序都是固定的。将这些队列一次组合起来,整体的排序就算完成了。

    昆明Java培训的老师提醒注意这里有两个最核心的步骤,就是

    1、选出Value元素,将整体队列划分成两个子队列

    2、然后将子队列重新作为一个新的,整体规模比当前要小的,新的队列,进行计算,直到计算起来非常容易为止。

    这两个核心步骤造就了快排天生的优势:

    1、通过比较大小划分到子队列中的元素,在未来的比较过程中,这个元素的比较范围始终都停留在这个子队列中,不再做多余的比较。这使得早期的比较对后期的比较仍然有很大的影响。而类似于冒泡的排序方法,则前期很多的比较,对后期的作用非常小。这点和kmp算法很像,前期的比较尽量做到最大的利用。

    2、将原有规模的队列,拆分成若干个规模小的子队列,这些子队列要解决的问题与原有队列一致,只是规模变小了。这样不断的拆分,形成一种分而治之的思想。这种思想与背包算法也是不谋而合。

    下边是java实现的代码

    1 import java.util.Arrays;

    2

    3 public class QuickSort

    4 {

    5    public static void main(String args[])

    6    {

    7        QuickSort quicksort = new QuickSort();

    8        int[] arrays = new int[]

    9        { 1, 12, 2, 13, 3, 14, 4, 15, 5, 16, 17, 17, 177, 18, 8, 8, 19 };

    10        quicksort.quickSort(arrays);

    11        System.out.println(Arrays.toString(arrays));

    12    }

    13    

    14    private void quickSort(int[] arrays)

    15    {

    16        subQuickSort(arrays, 0, arrays.length - 1);

    17    }

    18    

    19    private void subQuickSort(int[] arrays, int start, int end)

    20    {

    21        if (start >= end)

    22        {

    23            return;

    24        }

    25        int middleIndex = subQuickSortCore(arrays, start, end);

    26        subQuickSort(arrays, start, middleIndex - 1);

    27        subQuickSort(arrays, middleIndex + 1, end);

    28    }

    29    

    30    private int subQuickSortCore(int[] arrays, int start, int end)

    31    {

    32        int middleValue = arrays[start];

    33        while (start < end)

    34        {

    35            while (arrays[end] >= middleValue && start < end)

    36            {

    37                end--;

    38            }

    39            arrays[start] = arrays[end];

    40            while (arrays[start] <= middleValue && start < end)

    41            {

    42                start++;

    43            }

    44            arrays[end] = arrays[start];

    45        }

    46        arrays[start] = middleValue;

    47        return start;

    48    }

    49 }

    推荐文章

上一篇:kafka需要注意的事项

下一篇:【昆明Java培训】 java知识点之多态

最新开班日期  |  更多

Java--零基础全日制班

Java--零基础全日制班

开班日期:12/29

Java--零基础业余班

Java--零基础业余班

开班日期:12/29

Java--周末提升班

Java--周末提升班

开班日期:12/29

Java--零基础周末班

Java--零基础周末班

开班日期:12/29

  • 网址:http://km .java.tedu.cn      地址:昆明市官渡区春城路62号证券大厦附楼6楼
  • 课程培训电话:186 8716 1620      qq:2066486918    全国服务监督电话:400-827-0010
  • 服务邮箱 ts@tedu.cn
  • 2001-2016 达内国际公司(TARENA INTERNATIONAL,INC.) 版权所有 京ICP证08000853号-56