美文网首页Android进阶之路Android开发积累Android开发
Java常见排序算法详解——快速排序

Java常见排序算法详解——快速排序

作者: Demo_Yang | 来源:发表于2019-04-14 23:08 被阅读49次

概念:

通过一趟排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分小,则可分别对这两部分记录继续进行排序,直到整个序列有序。

原理:

  1. 在数据集之中,选择一个元素作为”基准”(pivot)。
  2. 所有小于”基准”的元素,都移到”基准”的左边;所有大于”基准”的元素,都移到”基准”的右边。这个操作称为分区 (partition) 操作,分区操作结束后,基准元素所处的位置就是最终排序后它的位置。
  3. 对”基准”左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。

图解:
例如我们有个一个数组[29 4 10 11 7]
1.首先我们先选定一个基准元素,这里我们选择10作为基准元素,然后把基准元素放在最后一个,如果选择最后一个元素作为基准元素,那么可以省略

快速排序
                   ↓
29   4   11   7   10

2.从左到右(除了最后的元素),循环移动小于基准元素到数据开头,留下大于等于基准元素的接在后面。
循环i = 1的时候,找到一个小于基准元素的元素4
这个时候storeIndex = 1

快速排序
                    ↓
4   29   11   7    10

之后循环到i=3时7小于10和storeIndex = 1换位置

4   7   11   29    10

这个时候storeIndex = 2
3.再然后,我们把基准元素放到storeIndex的位置,其他元素位置依次+1得到了我们想要的数组

4   7   10   11    29

代码:

    public static void qSort(int[] arr, int head, int tail) {
        if (head >= tail || arr == null || arr.length <= 1) {
            return;
        }
        int i = head, j = tail, pivot = arr[(head + tail) / 2];
        while (i <= j) {
            while (arr[i] < pivot) {
                ++i;
            }
            while (arr[j] > pivot) {
                --j;
            }
            if (i < j) {
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                ++i;
                --j;
            } else if (i == j) {
                ++i;
            }
        }
        qSort(arr, head, j);
        qSort(arr, i, tail);
    }

算法系列:

冒泡排序
选择排序
直接插入排序
二分插入排序
希尔排序
堆排序
归并排序
快速排序

完整代码:

Java和Kotlin代码我均放在了GitHub上,欢迎Star!

GitHub地址:https://github.com/yang0range/MyAlgorithm

欢迎关注公共号

关注公共号会有更多收获!

扫一扫,据说年轻、优秀、颜值高的互联网人都在这个群里

相关文章

  • 排序算法

    常见排序算法比较 参考资料:各种排序算法比较 参考资料:快速排序算法 必须知道的八大种排序算法【java实现】(一...

  • LeetCode大全

    1.常见排序算法: 常见的排序算法:冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序、堆排序、计数排序、...

  • Java常见排序算法详解——快速排序

    概念: 通过一趟排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分小,则可分别对这两部分记录继...

  • 数据结构&算法(一)

    一、Java实现快速排序算法 二、Java实现折半插入排序算法 三、Java实现冒泡排序算法

  • 盘点常用Java排序算法

    本文主要介绍Java的七种常见排序算法的实现,对选择排序、插入排序、冒泡排序、归并排序、快速排序、希尔排序、最小堆...

  • 盘点常用Java排序算法

    本文主要介绍Java的七种常见排序算法的实现,对选择排序、插入排序、冒泡排序、归并排序、快速排序、希尔排序、最小堆...

  • IOS常见算法

    常见算法: 快速排序: 选择排序: 冒泡排序: 测试代码:

  • Python知识点:常见算法的python实现

    提到排序算法,常见的有如下几种:冒泡排序、选择排序、插入排序、快速排序、堆排序、归并排序、希尔排序;查找算法最常见...

  • 7 天时间,我整理并实现了这 9 种最经典的排序算法

    回顾 我们前面已经介绍了 3 种最常见的排序算法: java 实现冒泡排序讲解 QuickSort 快速排序到底快...

  • 排序算法

    常见的排序算法 常见的排序算法有:插入、希尔、选择、冒泡、归并、快速、堆排序。。。 插入排序 算法步骤一、从数组的...

网友评论

    本文标题:Java常见排序算法详解——快速排序

    本文链接:https://www.haomeiwen.com/subject/rliewqtx.html