快速排序 golang - Go语言中文社区

快速排序 golang


快速排序 golang

快速排序(英语:Quicksort),又称划分交换排序(partition-exchange sort),简称快排,一种排序算法,最早由东尼·霍尔提出。在平均状况下,排序 个项目要(大O符号)次比较。在最坏状况下则需要次比较,但这种状况并不常见。

快排应用

  • 快排是一般语言内置排序包中的实现,当然在数组大小不同的情况下会有不同的选择,但是整体以快排为主,为了防止出现一般采用随机选择中间节点的方式来实现。
  • 作为算法题,要求实现。

分治法

分而治之,先将原问题的规模下降,分解为子问题,此所谓“分”,然后解决子问题,此为“治”。

分治法的基本思想是将一个规模为n的原问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同。递归地解这些子问题,然后将子问题的解合并为原问题的解。

算法描述

步骤为:

  1. 从数列中挑出一个元素,称为”基准”(pivot),
  2. 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任何一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
  3. 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。

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

一般采用的都是原地排序版本,这样不需要分配额外的空间,对速度有提升。

伪代码如下:

 procedure quicksort(a, left, right)
     if right > left
         select a pivot value a[pivotIndex]
         pivotNewIndex := partition(a, left, right, pivotIndex)
         quicksort(a, left, pivotNewIndex-1)
         quicksort(a, pivotNewIndex+1, right)

实现

单路快排

递归版本实现

  1. 首先通过随机数选取比较的点
  2. 遍历 head + 1-> tail
    • 大于mid 则和tail交换 并且tail–
    • 小于等于 则交换head 并且head++ i++

疑问:

  • 为什么在大于的情况下 index i 没有移位?

因为交换后的tail,并没有保证一定会大于mid元素,所以需要再次进行比较

  • 为什么在小于的情况下 index i 需要移位?

因为第一次交换的时候是arr[0] -> mid,所以交换后一定满足arr[i] <= mid,所以可以移位操作。否则遍历无法结束

func QSortRecursion(arr []int){
    arrLen := len(arr)
    if arrLen <= 1{
        return
    }

    randNum := getRandNum(arrLen -1)
    arr[randNum], arr[0] = arr[0],arr[randNum]
    mid := arr[0]//取出用于比较的元素

    head, tail := 0, arrLen -1

    for i := 1; i <= tail;{// 从 head + 1 到 tail 遍历 case 大于比较元素 换 else 小于等于 换 并且head++ 维护左边的数组
        if arr[i] > mid{
            arr[i], arr[tail] = arr[tail], arr[i]
            tail--
        }else{
            arr[i], arr[head] = arr[head], arr[i]
            head++
            i++
        }
    }

    QSortRecursion(arr[:head])
    QSortRecursion(arr[head+1:])
}

func getRandNum(totalNum int)int{
    rand.Seed(time.Now().Unix())// 设置随机种子
    return rand.Intn(totalNum)
}

双路快排

上面的实现方法是单路快排,常用的我们会用双路快排的方式,更加快。

可以看到当数据比较多重复的时候,单路快排会有非常冗余的swap操作,双路快排避免了这一点。

/*
    双路快排
    从左向右找到大于pivot的元素
    从右向左找小于pivot的元素
    判断是否越界 交换元素 head++ tail--
*/
func QSortTwoWay(arr []int){
    arrLen := len(arr)
    if arrLen <= 1{
        return
    }

    randNum := getRandNum(arrLen -1)
    arr[randNum], arr[0] = arr[0],arr[randNum]
    mid := arr[0]//取出用于比较的元素

    head, tail := 0, arrLen -1

    for {
        for head <= tail && arr[head] < mid{
            head ++
        }

        for tail > head && arr[tail] > mid{
            tail --
        }

        if head > tail{
            break
        }

        swap(arr, head,tail)
        head++
        tail--
    }

    QSortTwoWay(arr[:head])
    QSortTwoWay(arr[head+1:])
}

三路快排

当遇到非常多重复元素的时候,会使用三路快排的方式解决。
这里写图片描述

三路快排复杂的地方就在于对指定的变量的描述以及边界问题上。

这里写图片描述

由于时间关系暂时来一版c语言实现 详细信息情况下文参看链接

private void quickSort(int[] a, int left, int right) {
    if (right <= left)
        return;

    /* 
     * 工作指针
     * p指向序列左边等于pivot元素的位置
     * q指向序列右边等于Pivot元素的位置
     * i指向从左向右扫面时的元素
     * j指向从右向左扫描时的元素
     */
    int p, q, i, j;
    int pivot;// 锚点
    i = p = left;
    j = q = right - 1;
    /*
     * 每次总是取序列最右边的元素为锚点
     */
    pivot = a[right];
    while (true) {
        /*
         * 工作指针i从右向左不断扫描,找小于或者等于锚点元素的元素
         */
        while (i < right && a[i] <= pivot) {
            /*
             * 找到与锚点元素相等的元素将其交换到p所指示的位置
             */
            if (a[i] == pivot) {
                swap(a, i, p);
                p++;
            }
            i++;
        }
        /*
         * 工作指针j从左向右不断扫描,找大于或者等于锚点元素的元素
         */
        while (left <= j && a[j] >= pivot) {
            /*
             * 找到与锚点元素相等的元素将其交换到q所指示的位置
             */
            if (a[j] == pivot) {
                swap(a, j, q);
                q--;
            }
            j--;
        }
        /*
         * 如果两个工作指针i j相遇则一趟遍历结束
         */
        if (i >= j)
            break;

        /*
         * 将左边大于pivot的元素与右边小于pivot元素进行交换
         */
        swap(a, i, j);
        i++;
        j--;
    }
    /*
     * 因为工作指针i指向的是当前需要处理元素的下一个元素
     * 故而需要退回到当前元素的实际位置,然后将等于pivot元素交换到序列中间
     */
    i--;
    p--;
    while (p >= left) {
        swap(a, i, p);
        i--;
        p--;
    }
    /*
     * 因为工作指针j指向的是当前需要处理元素的上一个元素
     * 故而需要退回到当前元素的实际位置,然后将等于pivot元素交换到序列中间
     */
    j++;
    q++;
    while (q <= right) {
        swap(a, j, q);
        j++;
        q++;
    }

    /*
     * 递归遍历左右子序列
     */
    quickSort(a, left, i);
    quickSort(a, j, right);
}

参考:维基百科

三路快排

版权声明:本文来源CSDN,感谢博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。
原文链接:https://blog.csdn.net/u012279631/article/details/80717445
站方申明:本站部分内容来自社区用户分享,若涉及侵权,请联系站方删除。
  • 发表于 2019-08-27 18:27:21
  • 阅读 ( 3616 )
  • 分类:Go

0 条评论

请先 登录 后评论

官方社群

GO教程

猜你喜欢