数据结构和算法面试题系列—排序算法之快速排序

栏目: 编程工具 · 发布时间: 6年前

内容简介:快速排序也是基于分治模式,类似归并排序那样,不同的是快速排序划分最后不需要merge。对一个数组快速排序算法不算复杂的算法,但是实际写代码的时候却是最容易出错的代码,写的不对就容易死循环或者划分错误,本文代码见这个朴素的快速排序有个缺陷就是在一些极端情况如所有元素都相等时(或者元素本身有序,如

快速 排序 也是基于分治模式,类似归并排序那样,不同的是快速排序划分最后不需要merge。对一个数组 A[p..r] 进行快速排序分为三个步骤:

  • 划分: 数组 A[p...r] 被划分为两个子数组 A[p...q-1]A[q+1...r] ,使得 A[p...q-1] 中每个元素都小于等于 A[q] ,而 A[q+1...r] 每个元素都大于 A[q] 。划分流程见下图。
  • 解决: 通过递归调用快速排序,对子数组分别排序即可。
  • 合并:因为两个子数组都已经排好序了,且已经有大小关系了,不需要做任何操作。
数据结构和算法面试题系列—排序算法之快速排序

快速 排序算法 不算复杂的算法,但是实际写代码的时候却是最容易出错的代码,写的不对就容易死循环或者划分错误,本文代码见 这里

1 朴素的快速排序

这个朴素的快速排序有个缺陷就是在一些极端情况如所有元素都相等时(或者元素本身有序,如 a[] = {1,2,3,4,5} 等),朴素的快速算法时间复杂度为 O(N^2) ,而如果能够平衡划分数组则时间复杂度为 O(NlgN)

/**
 * 快速排序-朴素版本
 */
void quickSort(int a[], int l, int u)
{
    if (l >= u) return;

    int q = partition(a, l, u);
    quickSort(a, l, q-1);
    quickSort(a, q+1, u);
}

/**
 * 快速排序-划分函数
 */
int partition(int a[], int l, int u)
{
    int i, q=l;
    for (i = l+1; i <= u; i++) {
        if (a[i] < a[l])
            swapInt(a, i, ++q);
    }
    swapInt(a, l, q);
    return q;
}
复制代码

2 改进-双向划分的快速排序

一种改进方法就是采用双向划分,使用两个变量 iji 从左往右扫描,移过小元素,遇到大元素停止; j 从右往左扫描,移过大元素,遇到小元素停止。然后测试i和j是否交叉,如果交叉则停止,否则交换 ij 对应的元素值。

注意,如果数组中有相同的元素,则遇到相同的元素时,我们停止扫描,并交换 ij 的元素值。虽然这样交换次数增加了,但是却将所有元素相同的最坏情况由 O(N^2) 变成了差不多 O(NlgN) 的情况。比如数组 A={2,2,2,2,2} , 则使用朴素快速排序方法,每次都是划分 n 个元素为 1 个和 n-1 个,时间复杂度为 O(N^2) ,而使用双向划分后,第一次划分的位置是 2 ,基本可以平衡划分两部分。代码如下:

/**
 * 快速排序-双向划分函数
 */
int partitionLR(int a[], int l, int u, int pivot)
{
    int i = l;
    int j = u+1;
    while (1) {
        do {
            i++;
        } while (a[i] < pivot && i <= u); //注意i<=u这个判断条件,不能越界。

        do {
            j--;
        } while (a[j] > pivot);

        if (i > j) break;

        swapInt(a, i, j);
    }

    // 注意这里是交换l和j,而不是l和i,因为i与j交叉后,a[i...u]都大于等于枢纽元t,
    // 而枢纽元又在最左边,所以不能与i交换。只能与j交换。
    swapInt(a, l, j);

    return j;
}

/**
 * 快速排序-双向划分法
 */
void quickSortLR(int a[], int l, int u)
{
    if (l >= u) return;

    int pivot = a[l];
    int q = partitionLR(a, l, u, pivot);
    quickSortLR(a, l, q-1);
    quickSortLR(a, q+1, u);
}
复制代码

虽然双向划分解决了所有元素相同的问题,但是对于一个已经排好序的数组还是会达到 O(N^2) 的复杂度。此外,双向划分还要注意的一点是代码中循环的写法,如果写成 while(a[i]<t) {i++;} 等形式,则当左右划分的两个值都等于枢纽元时,会导致死循环。

3 继续改进—随机法和三数取中法取枢纽元

为了解决上述问题,可以进一步改进,通过随机选取枢纽元或三数取中方式来获取枢纽元,然后进行双向划分。三数取中指的就是从数组A[l... u]中选择左中右三个值进行排序,并使用中值作为枢纽元。如数组 A[] = {1, 3, 5, 2, 4} ,则我们对 A[0]、A[2]、A[4] 进行排序,选择中值 A[4](元素4) 作为枢纽元,并将其交换到 a[l] ,最后数组变成 A[] = {4 3 5 2 1} ,然后跟之前一样双向排序即可。

/**
 * 随机选择枢纽元
 */
int pivotRandom(int a[], int l, int u)
{
    int rand = randInt(l, u);
    swapInt(a, l, rand); // 交换枢纽元到位置l
    return a[l];
}

/**
 * 三数取中选择枢纽元
 */
int pivotMedian3(int a[], int l, int u)
{
     int m = l + (u-l)/2;

     /*
      * 三数排序
      */
     if( a[l] > a[m] )
        swapInt(a, l, m);

     if( a[l] > a[u] )
        swapInt(a, l, u);

     if( a[m] > a[u] )
        swapInt(a, m, u);

     /* assert: a[l] <= a[m] <= a[u] */
     swapInt(a, m, l); // 交换枢纽元到位置l

     return a[l];
}
复制代码

此外,在数据基本有序的情况下,使用插入排序可以得到很好的性能,而且在排序很小的子数组时,插入排序比快速排序更快,可以在数组比较小时选用插入排序,而大数组才用快速排序。

4 非递归写快速排序

非递归写快速排序着实比较少见,不过练练手总是好的。需要用到栈,注意压栈的顺序。代码如下:

/**
 * 快速排序-非递归版本
 */
void quickSortIter(int a[], int n)
{
    Stack *stack = stackNew(n);
    int l = 0, u = n-1;
    int p = partition(a, l, u);

    if (p-1 > l) { //左半部分两个边界值入栈
        push(stack, p-1); 
        push(stack, l);
    }

    if (p+1 < u) { //右半部分两个边界值入栈
        push(stack, u);
        push(stack, p+1);
    }

    while (!IS_EMPTY(stack)) { //栈不为空,则循环划分过程
        l = pop(stack);
        u = pop(stack);
        p = partition(a, l, u);

        if (p-1 > l) {
            push(stack, p-1);
            push(stack, l);
        }

        if (p+1 < u) {
            push(stack, u);
            push(stack, p+1);
        }
    }
}
复制代码

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

R语言实战

R语言实战

卡巴科弗 (Robert I.Kabacoff) / 高涛、肖楠、陈钢 / 人民邮电出版社 / 2013-1 / 79.00元

数据时代已经到来,但数据分析、数据挖掘人才却十分短缺。由于“大数据”对每个领域的决定性影响, 相对于经验和直觉,在商业、经济及其他领域中基于数据和分析去发现问题并作出科学、客观的决策越来越重要。开源软件R是世界上最流行的数据分析、统计计算及制图语言,几乎能够完成任何数据处理任务,可安装并运行于所有主流平台,为我们提供了成千上万的专业模块和实用工具,是从大数据中获取有用信息的绝佳工具。  本书从解决......一起来看看 《R语言实战》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码