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

栏目: 编程工具 · 发布时间: 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);
        }
    }
}
复制代码

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

查看所有标签

猜你喜欢:

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

智能革命

智能革命

李彦宏 等 / 中信出版集团 / 2017-5-1 / 68.00元

人类历史上的历次技术革命,都带来了人类感知和认知能力的不断提升,从而使人类知道更多,做到更多,体验更多。以此为标准,李彦宏在本书中将人工智能定义为堪比任何一次技术革命的伟大变革,并且明确提出,在技术与人的关系上,智能革命不同于前几次技术革命,不是人去适应机器,而是机器主动来学习和适应人类,并同人类一起学习和创新这个世界。“人工智能”正式写入2017年政府工作报告,折射出未来人工智能产业在我国经济发......一起来看看 《智能革命》 这本书的介绍吧!

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

在线图片转Base64编码工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具