动力节点首页 全国咨询热线:400-8080-105

绑定手机号,登录
手机号

验证码

微信登录
手机号登录
手机号

验证码

微信登录与注册
微信扫码登录与注册

扫码关注微信公众号完成登录与注册
手机号登录
首页 > 文章

一文秒懂快速排序算法

05-12 11:29 941浏览
举报 T字号
  • 大字
  • 中字
  • 小字

快速排序(Quicksort)实际上是对冒泡排序的一种改进,借用了分治的思想,由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

1.算法描述

快速排序使用分治策略来把一个序列(list)分为两个子序列(sub-lists)。步骤为:

(1)从数列中挑出一个元素,称为”基准”(pivot)。

(2) 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。

(3) 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时,数列的大小是零或一,也就是已经排序好了。这个算法一定会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

2.代码实现

1)挖坑法 用伪代码描述如下:

(1)low = L; high = R; 将基准数挖出形成第一个坑a[low]。

(2)high--,由后向前找比它小的数,找到后挖出此数填前一个坑a[low]中。

(3)low++,由前向后找比它大的数,找到后也挖出此数填到前一个坑a[high]中。

(4)再重复执行②,③二步,直到low==high,将基准数填入a[low]中。

举例说明: 一个无序数组:[4, 3, 7, 5, 10, 9, 1, 6, 8, 2]

(1)随便先挖个坑,就在第一个元素(基准元素)挖坑,挖出来的“萝卜”(第一个元素4)在“篮子”(临时变量)里备用。 挖完之后的数组是这样:[ 坑, 3, 7, 5, 10, 9, 1, 6, 8,2]

(2)挖右坑填左坑:从右边开始,找个比“萝卜”(元素4)小的元素,挖出来,填到前一个坑里面。 填坑之后:[ 2, 3, 7, 5, 10, 9, 1, 6, 8,坑]

(3)挖左坑填右坑:从左边开始,找个比“萝卜”(元素4)大的元素,挖出来,填到右边的坑里面。 填坑之后:[ 2, 3,坑, 5, 10, 9, 1, 6, 8, 7]

(4)挖右坑填左坑:从右边开始,找个比“萝卜”(元素4)小的元素,挖出来,填到前一个坑里面。 填坑之后:[ 2, 3, 1, 5, 10, 9,坑, 6, 8, 7]

(5)挖左坑填右坑:从左边开始,找个比“萝卜”(元素4)大的元素,挖出来,填到右边的坑里面。 填坑之后:[ 2, 3, 1,坑, 10, 9, 5, 6, 8, 7]

(6)挖右坑填左坑:从右边开始,找个比“萝卜”(元素4)小的元素,挖出来,填到前一个坑里面,这一次找坑的过程中,找到了上一次挖的坑了,说明可以停了,用篮子里的的萝卜,把这个坑填了就行了,并且返回这个坑的位置,作为分而治之的中轴线。 填坑之后:[ 2, 3, 1, 4, 10, 9, 5, 6, 8, 7]

上面的步骤中,第2,4, 6其实都是一样的操作,3和5的操作也是一样的,代码如下:

  /**
     *  快速排序(挖坑法递归)
     * @param arr   待排序数组
     * @param low   左边界
     * @param high  右边界
     */
    public static void sort(int arr[], int low, int high) {
        if (arr == null || arr.length <= 0) {
            return;
        }
        if (low >= high) {
            return;
        }

        int left = low;
        int right = high;
        int temp = arr[left]; //挖坑1:保存基准的值

        while (left < right) {
            while (left < right && arr[right] >= temp) {
                right--;
            }
            arr[left] = arr[right]; //坑2:从后向前找到比基准小的元素,插入到基准位置坑1中
            while (left < right && arr[left] <= temp) {
                left ++;
            }
            arr[right] = arr[left]; //坑3:从前往后找到比基准大的元素,放到刚才挖的坑2中
        }
        arr[left] = temp; //基准值填补到坑3中,准备分治递归快排
        System.out.println("Sorting: " + Arrays.toString(arr));
        sort(arr, low, left-1);
        sort(arr, left + 1, high);
    }

2)左右指针法

用伪代码描述如下:

(1)low = L; high = R; 选取a[low]作为关键字记录为key。

(2)high--,由后向前找比它小的数

(3)low++,由前向后找比它大的数

(4)交换第(2)、(3)步找到的数

(5)重复(2)、(3),一直往后找,直到left和right相遇,这时将key和a[low]交换位置。

代码如下:

/**
 * 快速排序
 * Created by zhoujunfu on 2018/8/6.
 */
public class QuickSort {
    /**
     * 快速排序(左右指针法)
     * @param arr 待排序数组
     * @param low 左边界
     * @param high 右边界
     */
    public static void sort2(int arr[], int low, int high) {
        if (arr == null || arr.length <= 0) {
            return;
        }
        if (low >= high) {
            return;
        }

        int left = low;
        int right = high;

        int key = arr[left];

        while (left < right) {
            while (left < right && arr[right] >= key) {
                right--;
            }
            while (left < right && arr[left] <= key) {
                left++;
            }
            if (left < right) {
                swap(arr, left, right);
            }
        }
        swap(arr, low, left);
        System.out.println("Sorting: " + Arrays.toString(arr));
        sort2(arr, low, left - 1);
        sort2(arr, left + 1, high);
    }

    public static void swap(int arr[], int low, int high) {
        int tmp = arr[low];
        arr[low] = arr[high];
        arr[high] = tmp;
    }
}

3.算法效率

快速排序并不稳定,快速排序每次交换的元素都有可能不是相邻的, 因此它有可能打破原来值为相同的元素之间的顺序。

平均时间复杂度 最好情况 最坏情况 空间复杂度
O(nlogn) O(nlogn) O(n2) O(1)

正如我们前面所说,快速排序算法是冒泡排序算法的一种改进,只有我们学好了冒泡排序算法,自然而然也就掌握了快速排序算法的核心,学习起来事半功倍。当然,想要学习全部的排序算法还是要花费一点时间和精力的,推荐动力节点在线的视频课程。名师讲解,通俗易懂,能够很大程度上帮助我们节省学习的时间,提高学习效率。

0人推荐
共同学习,写下你的评论
0条评论
代码小兵498
程序员代码小兵498

153篇文章贡献528999字

相关课程 更多>

作者相关文章更多>

推荐相关文章更多>

Java面试题及答案整理

提枪策马乘胜追击04-21 20:01

Spring常见面试题

代码小兵92504-17 16:07

Java零基础实战项目——五子棋

代码小兵98804-25 13:57

Java string类详解

杨晶珍05-11 14:54

6道经典算法面试题

杨晶珍05-12 16:39

发评论

举报

0/150

取消