专栏首页奇妙的算法世界排序算法之快速排序

排序算法之快速排序

快速排序

快速排序是一种非常优秀的排序算法,应用的也非常广泛,面试时面试官也经常让你手写一个快排,所以说学习快速排序是非常有必要的。

快速排序原理

同归并排序一样,快速排序也是一种分治的排序算法。在归并排序中,通过将数组分成两个子数组进行排序,然后对两个有序的子数组进行归并以将整个数组排序。而快速排序则是选定一个基准值,然后将大于该值的元素放在该元素后面,小于该值的元素放在该值前面。通过不断的递归调用来完成排序。

动图演示

代码实现

    public static void main(String[] args) {
        int[] a = {9, 45, 10, 35, 64, 99, 103, 56, 47, 12, 79, 0};
        sort(a, 0, a.length - 1);
    }

    public static void sort(int[] arr, int left, int right) {
        if (right <= left)
            return;
        }
        int t = partition(arr, left, right);
        sort(arr, left, t - 1);
        sort(arr, t + 1, right);
    }

    public static int partition(int[] arr, int left, int right) {
        int i = left;
        int j = right + 1;
        int t = arr[left];
        while (true) {
            while (arr[++i] < t) {
                if (i == right) {
                    break;
                }
            }
            while (arr[--j] > t) {
                if (j == left) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        int temp = arr[left];
        arr[left] = arr[j];
        arr[j] = temp;
        return j;
    }

代码也是很容易就能够看懂,通过使用双指针,不断地与基准值进行比较,将大于基准值的元素放在基准值后面,将小于基准值的元素放在基准值前面,当两个指针相遇时则说明已经摆放完毕,然后将基准值与j所对应的元素交换,通过这样不管的递归调用,即可完成排序。

三向切分快速排序

所谓三向切分,就是维护三个指针,维护一个指针使得某块元素小于基准值,维护一个指针使得某块元素等于基准值,维护一个指针使得某块元素大于基准值。

    public static void main(String[] args) {
        int[] a = {4, 1, 90, 14, 50, 64, 70, 7, 12, 36, 97, 43, 21, 12};
        sort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }

    public static void sort(int[] arr, int left, int right) {
        if (right <= left) {
            return;
        }
        int i = left, j = right, k = left + 1;
        int M = arr[left];
        while (k <= j) {
            if (arr[k] < M) {
                int temp = arr[i];
                arr[i] = arr[k];
                arr[k] = temp;
                i++;
                k++;
            } else if (arr[k] > M) {
                int temp = arr[k];
                arr[k] = arr[j];
                arr[j] = temp;
                j--;
            } else {
                k++;
            }
            sort(arr, left,  i- 1);
            sort(arr, j + 1, right);
        }
    }

和上面的双指针方法基本一样,只是多维护了一个指针。

三数取中法

在快排的过程中,我们需要取一个枢纽值,一般都是取left所对应元素的值,但那样容易出现数组一边倒的情况,所以我们使用三数取中法,也就是取左端、右端、中间三个数,然后对这些数进行排序,将中间值作为枢纽值。

    public static void main(String[] args) {
        int[] a = {9, 45, 10, 35, 64, 99, 103, 56, 47, 12, 79, 0};
        sort(a, 0, a.length - 1);
        for (int tt : a) {
            System.out.print(tt+" ");
        }
    }

    public static void sort(int[] arr, int left, int right) {
        if(right<=left) {
            return;
        }
            threeSplit(arr, left, right);
            int i = left, j = right - 1, t = right - 1;
            while (true) {
                while (arr[++i] < arr[t]) {
                    if (i == right) {
                        break;
                    }
                }
                while (j>left&&arr[--j] > arr[t]) {
                    if (j == left) {
                        break;
                    }
                }
                if (i >= j) {
                    break;
                }
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
            }
            if (i < right) {
            int temp = arr[i];
            arr[i] = arr[right - 1];
            arr[right - 1] = temp;
            }
            sort(arr, left, i - 1);
            sort(arr, i + 1, right);
        }

    public static void threeSplit(int[] arr, int left, int right) {
        int mid = (left + right)>>>1;
        if (arr[left] > arr[mid]) {
            int temp = arr[left];
            arr[left] = arr[mid];
            arr[mid] = temp;
        }
        if (arr[left] > arr[right]) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
        if (arr[mid] > arr[right]) {
            int temp = arr[mid];
            arr[mid] = arr[right];
            arr[right] = temp;
        }
        int temp = arr[right-1];
        arr[right - 1] = arr[mid];
        arr[mid] = temp;
    }

图解如下:

总结

通过对快速排序的不断改进,我们发现一个细小的改动就可以提升很多性能,快速排序应用非常广泛,一定要掌握的很熟练。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 排序算法之归并排序

    归并排序是一种非常优秀的排序算法,时间复杂度仅为O(nlogn),与选择排序和冒泡排序的O(n2)相比较,只是将n这个因子替换成了logn,但这是非常划算的一个...

    dejavu1zz
  • codeforces 1436C(二分+数学)

    由于二分是通过不断缩减寻找区间的操作,所以我们可以模拟二分操作,求出二分结束后位置停留在pos时的向左跳的次数left和向右跳的次数right,最后通过组合数来...

    dejavu1zz
  • 关于动态规划的练习题

    1.给出不同面额的硬币以及一个总金额. 写一个方法来计算给出的总金额可以换取的最少的硬币数量. 如果已有硬币的任意组合均无法与总金额面额相等, 那么返回 -1。

    dejavu1zz
  • 一看就懂的快速排序

    快速排序属于交换排序,主要步骤是使用基准元素进行比较,把小于基准元素的移动到一边,大于基准元素的移动到另一边。从而把数组分成两部分,然后再从这两部分中选取出基准...

    Johnson木木
  • 排序算法

    基本思想: 我们将一个待排序序列分为有序区和无序区(一般开始的时候将第一个元素作为有序区,剩下的元素作为无序区),每次将无序区的第一个元素作为待插入记录,按大小...

    Cloud-Cloudys
  • 详解快速排序算法

    本文的思路是以从小到大为例讲的。 快速排序的基本思想是任取待排序序列的一个元素作为中心元素(可以用第一个,最后一个,也可以是中间任何一个),习惯将其称为pivo...

    code随笔
  • [Go] Golang练习项目-快速排序的GO语言实现

    快速排序首先选一个基准(你也可以认为是要放到排序后数组正确位置的元素)pivot,然后将数组按照选取的基准 pivot 进行划分。而选取 pivot 的方式又有...

    陶士涵
  • 快速排序与寻找第k小的数算法

    慕课网 首发了,放在垂直领域吧。简书备份。 出现了一点小问题,就是index,要注意。想法网上一大堆,不多说了。 ubuntu18下输入法有问题,sogou...

    东风冷雪
  • Java中获取一个数组的最大值和最小值

    3,然后对数组进行遍历循环,若循环到的元素比最大值还要大,则将这个元素赋值给最大值;同理,若循环到的元素比最小值还要小,则将这个元素赋值给最小值;

    程序员的时光001
  • 排序算法算法对比

    排序大的分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。下面讲的排序都是属于内排序。...

    朱晓霞

扫码关注云+社区

领取腾讯云代金券