您的浏览器不支持CSS3,建议使用Firfox、Chrome等浏览器,以取得最佳显示效果

快速排序算法分析与实现

开发技术 306℃ 0 4个月前 (03-03)

摘要

快速排序算法的多种实现方案,动画示意,Java代码实现。

基本思路

使用分治思想。选择一个Pivot,把小于Pivot的放到Pivot左边,大于Pivot的放到Pivot右边。之后继续对Pivot分隔开的左右两侧做相同的操作,直到所有元素有序。

复杂度

这里讨论的是原地算法的复杂度。

1、最好的情况下,每次选取的Pivot,都能把数组平分为两部分,时间复杂度为 O(N·logN),空间复杂度为O(logN)

2、最坏的情况下,每次选取的Pivot,都是最大值(最小值),每次只能排好一个元素,退化为冒泡排序,时间复杂度为 O(N^2),空间复杂度为O(N)

总结:

  • 时间复杂度:最好:O(N·logN),最坏:O(N^2),平均:O(N·logN)
  • 空间复杂度:最好:O(logN),最坏:O(N)

具体的推导过程可以参考:https://blog.csdn.net/YuZhiHui_No1/article/details/44198701

Pivot选择

Pivot的选择是快速排序的关键,对复杂度起到决定作用。Pivot的选择有很多种,例如:

  • 选第一个
  • 选最后一个
  • 选中间一个
  • 随机选一个
  • 三数取中法

为了便于算法实现,需要取中间某个Pivot时,可以通过交换元素,转换成取第一个(或最后一个)。

随机选取

使用Random随机选一个,并交换到开头。

static void movePivotToStart(int[] array, int start, int end) {
    // 随机选一个作为pivot并移动到开头
    int pivotIndex = start + new Random().nextInt(end - start);
    swap(array, pivotIndex, start);
}

其中swap是通用的元素交换方法:

static void swap(int[] array, int x, int y) {
    int tmp = array[x];
    array[x] = array[y];
    array[y] = tmp;
}

三数取中法

三数取中法的策略是,分别取开头、末尾和中间三个数,并将值处于中间的那个数作为Pivot。

代码实现如下,利用类似冒泡排序的思路,将start,mid,end按照从小到大的顺序排列起来。然后再把中间值即mid交换到start。

static void movePivotToStart(int[] array, int start, int end) {
    int mid = (start + end) / 2;
    if (array[start] > array[mid]) {
        swap(array, start, mid);
    }
    if (array[mid] > array[end]) {
        swap(array, mid, end);
    }
    if (array[start] > array[mid]) {
        swap(array, start, mid);
    }
    swap(array, start, mid);
}

因为最后两步可能会对start和mid进行两次交换,还可以进一步优化为:

static void movePivotToStart(int[] array, int start, int end) {
    int mid = (start + end) / 2;
    if (array[start] > array[mid]) {
        swap(array, start, mid);
    }
    if (array[mid] > array[end]) {
        swap(array, mid, end);
    }
    if (array[start] <= array[mid]) {
        swap(array, start, mid);
    }
}

非原地算法

快排又分为非原地排序和原地排序。非原地排序思路很简单,但是给数组排序需要消耗额外内存。这个思路更适合链表排序。伪代码如下(来自维基百科 ):

function quicksort(q)
{
    var list less, pivotList, greater
    if length(q) ≤ 1 
    	return q
    else {
        select a pivot value pivot from q
        for each x in q except the pivot element {
            if x < pivot then add x to less
            if x ≥ pivot then add x to greater
        }
        add pivot to pivotList
        return concatenate(quicksort(less), pivotList, quicksort(greater))
    }
}

原地算法partition实现

通常会把选取pivot和移动元素的操作放到partition方法中,而partition有多种实现。

static void quickSort(int[] array, int start, int end) {
    // start = end时,size为1,不需要排序
    if (start >= end) {
        return;
    }
    // 处理并返回pivot
    int index = partition(array, start, end);
    quickSort(array, start, index - 1);
    quickSort(array, index + 1, end);
}

实现一:遍历

最常见的实现,选第一个作为Pivot,然后直接从左到右遍历,把数据分割为两部分。

static int partition(int[] array, int start, int end) {
    // 取第一个作为轴
    int pivot = array[start];

    // index为pivot最终的位置,最终要满足 [start~index-1] < [index] < [index+1 ~ end]
    int index = start;

    // 循环过程中,先不移动pivot,满足 [start+1 ~ index] < pivot < [index+1 ~ end]
    for (int i = start + 1; i <= end; i++) {
        if (array[i] < pivot) {
            index++;
            swap(array, index, i);
        }
    }

    // 最终交换 start 和 index,让pivot移动到正确的位置,
    // 使得 [start~index-1] < [index] < [index+1 ~ end]
    swap(array, start, index);
    return index;
}

对应的示意图如下:

参考: https://www.cnblogs.com/onepixel/p/7674659.html

实现二:两端搜索交换

选中最后一个作为Pivot,先从左边找到第一个大于Pivot的元素,再从右边找到第一个小于Pivot的元素,将这两者交换。继续交互步骤直到两端相遇。

或者:选中第一个作为Pivot,先从右边找到第一个小于Pivot的元素,再从左边找到第一个大于Pivot的元素,将这两者交换。

注意选中一端作为Pivot,就必须先从另一端搜索,因为可能会有一个特殊情况,就是原始数组已经满足条件不需要调整。

static int partition(int[] array, int start, int end) {
    int pivot = array[start];

    // 这里有一种特殊情况,
    // 原始数组已经满足 [start] < [start+1 ~ end],执行循环后,应该得到 i = j = start

    // i必须从start开始,而不是 start + 1
    int i = start, j = end;
    while (i < j) {
        // 必须先执行--j的操作
        while (i < j && array[j] >= pivot) --j;
        while (i < j && array[i] <= pivot) ++i;
        if (i < j) {
            swap(array, i, j);
        }
    }
    // 移动pivot到正确位置
    swap(array, start, i);
    return i;
}

图片示意:

还可以参考:https://wiki.jikexueyuan.com/project/easy-learn-algorithm/fast-sort.html

顺便把图片摘录过来了:

实现三:挖坑法

挖坑法。选取第一个作为Pivot,并挖出来形成一个坑。先从右边找到第一个小于Pivot的元素,挖出来填到坑里。再从左边找到第一个大于Pivot的元素,挖出来填到坑里。继续填坑步骤直到两端相遇。

static int partition3(int[] array, int start, int end) {
    int pivot = array[start];
    // [start] 是第一个坑
    int i = start, j = end;
    while (i < j) {
        while (i < j && array[j] >= pivot) --j;
        if (i < j) {
            // [j] 挪到 [i] , [j] 形成了新的坑
            array[i] = array[j];
            ++i;
        }
        while (i < j && array[i] <= pivot) ++i;
        if (i < j) {
            // [i] 挪到 [j] , [i] 形成了新的坑
            array[j] = array[i];
            --j;
        }
    }
    //退出时,i == j。将 pivot 填到这个坑中。
    array[i] = pivot;
    return i;
}

参考: https://blog.csdn.net/MoreWindows/article/details/6684558

总结:快排完整写法示例

下面给出一个快排完整示例,Pivot使用随机选取,两端搜索交换。

static void quickSort(int[] array, int start, int end) {
    if (start >= end) {
        return;
    }
    int pivot = partition(array, start, end);
    quickSort(array, start, pivot - 1);
    quickSort(array, pivot + 1, end);
}

static int partition(int[] array, int start, int end) {
    movePivotToStart(array, start, end);
    int pivot = array[start];
    int i = start, j = end;
    while (i < j) {
        while (i < j && array[j] >= pivot) --j;
        while (i < j && array[i] <= pivot) ++i;
        if (i < j) {
            swap(array, i, j);
        }
    }
    swap(array, start, i);
    return i;
}

static void movePivotToStart(int[] array, int start, int end) {
    int pivotIndex = start + new Random().nextInt(end - start);
    swap(array, pivotIndex, start);
}

static void swap(int[] array, int x, int y) {
    int tmp = array[x];
    array[x] = array[y];
    array[y] = tmp;
}

最后,欢迎扫码关注微信公众号。微软 / Shopee / Coupang / BAT等国内外企业内推、行业和技术交流,也可以加我微信 jzj2015(注明来自博客),拉你进技术群。

本文由原创,转载请注明来源:https://www.paincker.com/quick-sort
(标注了原文链接的文章除外)

0

暂无评论

评论前:需填写以下信息,或 登录

用户登录

忘记密码?