导航 品达服务导航
当前位置: 主页 搜索引擎优化
  • SEO优化怎么做
  • 什么是单页面优化
  • 关键词优化需注意什么
  • 网站优化的技巧
  • 企业推广需要注意什么
  • 一看就懂的快速排序

    作者
    发布时间2020-01-11
    阅读量2202
    概念

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

    紫色:基准元素

    绿色:大于基准元素

    黄色:小于基准元素

    一看就懂的快速排序

    这种思路叫做分治法。

    基准元素

    基准元素的选取可随机选取。下面使用中我会使用第一位的元素作为基准元素。

    排序过程

    排序拆分过程如下图:

    紫色为基准元素,(每一轮都重新选取)

    绿色为其他元素

    第一轮

    一看就懂的快速排序

    第二轮

    一看就懂的快速排序

    第三轮

    一看就懂的快速排序

    如上图所示:

    若元素个数为n,因为排序过程中需要和全部元素都比较一遍,所以时间复杂度为O(n),

    而平均情况下排序轮次需要logn轮,因此快速排序的平均时间复杂度为O(nlogn)。

    排序的实现方法

    实现方法有双边循环法和单边循环法

    双边循环法

    首选选取基准元素(pivot)4,并设置指针left和right,指向数组最左和最右两个元素,如下:

    一看就懂的快速排序

    第一次循环,先从right指针指向的数据(rightData)开始和基准元素比较

    若 rightData >= pivot,则right指针向左移动,若 rightData < pivot,则right指针不移动,切换到left指针

    left指针指向数据(leftData)与基准元素比较,若 leftData < pivot,则left指针向右移动,若 leftData > pivot,交换left和right指向的元素。

    第一轮指针移动完后,得到如下结构:

    一看就懂的快速排序

    然后 left和right指向的元素进行交换:

    一看就懂的快速排序

    第一轮循环结束,重新切换到right指针,重复上述步骤。

    第二轮循环后,得:

    一看就懂的快速排序

    第三轮循环后,得:

    一看就懂的快速排序

    第四轮循环后,得:

    一看就懂的快速排序

    判断到left和right指针指向同一个元素,指针停止移动,使pivot和指针元素进行交换,得:

    一看就懂的快速排序

    宣告该轮循环结束,并根据Pivot元素切分为两部分,这两部分的数组再根据上述步骤进行操作。

    实现代码
    public class DoubleSort {
    public static void quickSort(int[] arr, int startIndex, int endIndex) {

    //递归结束条件
    if (startIndex >= endIndex) {
    return;
    }

    // 基准元素位置
    int pivotIndex = partition(arr, startIndex, endIndex);

    // 根据基准元素,分成两部分进行递归排序
    quickSort(arr, startIndex, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, endIndex);
    }

    public static int partition(int[] arr, int startIndex, int endIndex) {
    // 取第一个元素为基准元素,也可以随机抽取
    int pivot = arr[startIndex];
    int left = startIndex;
    int right = endIndex;

    while (left != right) {
    // 控制right指针比较并左移
    while (left < right && arr[right] >= pivot) {
    right--;
    }

    // 控制left指针比较并右移
    while (left < right && arr[left] <= pivot) {
    left++;
    }

    // 交换left和right指针所指向的元素
    if (left < right) {
    int temp = arr[right];
    arr[right] = arr[left];
    arr[left] = temp;
    }
    }

    arr[startIndex] = arr[left];
    arr[left] = pivot;
    return left;
    }

    public static void main(String[] args) {
    int[] arr = new int[]{4, 7, 6, 5, 3, 2, 8, 1};
    quickSort(arr, 0, arr.length - 1);
    System.out.println(Arrays.toString(arr));
    }
    }

    单边循环法

    双边循环法从数组的两边比较并交换元素,而单边循环法则从数组的一边遍历,一直往后比较和交换,实现起来更加的简单。

    过程如下:

    首先也是选取基准元素pivot(可以随机选择)

    设置一个mark指针指向数组的起始位置,代表小于基准元素的区域边界(不理解的就把它理解成是等会用来交换元素的就好了)

    原始数组如下:

    一看就懂的快速排序

    从基准元素下一位开始遍历数组

    如果该元素大于基准元素,继续往下遍历

    如果该元素小于基准元素,mark指针往右移,因为小于基准元素的区域边界增大了1(即小于基准元素的多了1位),所以mark就 +1,并且该元素和mark指向元素进行交换。

    遍历到元素3时,因为3 < 4,所以mark右移

    一看就懂的快速排序

    然后交换元素

    一看就懂的快速排序

    然后就继续遍历,根据上面的步骤进行判断,后面的过程就不写了。

    实现代码
    public class SingleSort {
    public static void quickSort(int[] arr, int startIndex, int endIndex) {

    //递归结束条件
    if (startIndex >= endIndex) {
    return;
    }

    // 基准元素位置
    int pivotIndex = partition(arr, startIndex, endIndex);

    // 根据基准元素,分成两部分进行递归排序
    quickSort(arr, startIndex, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, endIndex);
    }

    /**
    * 分治(单边循环法)
    * @param arr
    * @param startIndex
    * @param endIndex
    * @return
    */
    public static int partition(int[] arr, int startIndex, int endIndex) {
    // 取第一个元素为基准元素,也可以随机抽取
    int pivot = arr[startIndex];
    int mark = startIndex;

    for(int i = startIndex + 1; i< arr.length; i++) {
    if (pivot < arr[i]) {
    continue;
    }

    mark ++;
    int temp = arr[mark];
    arr[mark] = arr[i];
    arr[i] = temp;
    }
    arr[startIndex] = arr[mark];
    arr[mark] = pivot;
    return mark;
    }

    public static void main(String[] args) {
    int[] arr = new int[]{4, 7, 6, 5, 3, 2, 8, 1};
    quickSort(arr, 0, arr.length - 1);
    System.out.println(Arrays.toString(arr));
    }
    }

    总结

    本人也是初次接触算法,慢慢的去理解算法的思路和实现过程后,真是为自己以往写的算法感到羞愧。该文章也是为了加深自己对快排算法的印象,若文章有不足之处,恳请各位在下方留言补充。感谢各位的阅读。Thanks?(?ω?)?。

    还没有解决您的问题?

    请留下问题以及联系方式会有专业的人员为您解答

    0/500
    姓名 姓名
    手机 手机
    微信 微信

    项目服务

    在线客服

    返回顶部