首页 > 编程语言 >荷兰国旗问题与快速排序算法

荷兰国旗问题与快速排序算法

时间:2022-09-28 20:58:16浏览次数:86  
标签:国旗 int arr ++ 算法 数组 排序

荷兰国旗问题与快速排序算法

作者:Grey

原文地址:

博客园:荷兰国旗问题与快速排序算法

CSDN:荷兰国旗问题与快速排序算法

荷兰国旗问题

问题描述

给定一个整数数组,给定一个值K,这个值在原数组中一定存在,要求把数组中小于K的元素放到数组的左边,大于K的元素放到数组的右边,等于K的元素放到数组的中间。

时间复杂度要求O(N),空间复杂度要求O(1)

主要思路

设置两个变量lr,其中<i位置的值都是比 K 小的数,i……r都是等于 K 的数,>r都是大于 K 的数。

初始值l = - 1, r = arr.length; 表示都还没考察过数组的任何一个元素,然后开始遍历数组,遍历到的位置为i,arr[i]有三种情况

情况 1

arr[i] > K

情况 2

arr[i] == K

情况 3

arr[i] < K

对于情况 1, 只需要将i位置的值和r - 1位置的值交换,然后r--,i++

对于情况 3, 只需要将i位置的值和l + 1位置的值交换,然后l++,i++

对于情况 2, 只需要将i位置的值和r-1位置的值交换,然后i++

数组遍历完毕后,原始数组就形成了:小于K的元素放到数组的左边,大于K的元素放到数组的右边,等于K的元素放到数组的中间。

题目链接:LeetCode 75. Sort Colors

完整代码见

class Solution {
    public static void sortColors(int[] arr) {
        int l = -1;
        int r = arr.length;
        int i = 0;
        while (i < r) {
            if (arr[i] > 1) {
                swap(arr, i, --r);
            } else if (arr[i] < 1) {
                swap(arr, i++, ++l);
            } else {
                // arr[i] == 1
                i++;
            }
        }
    }

    private static void swap(int[] arr, int l, int r) {
        if (l == r) {
            return;
        }
        arr[l] = arr[l] ^ arr[r];
        arr[r] = arr[l] ^ arr[r];
        arr[l] = arr[l] ^ arr[r];
    }
}

快速排序

基于上述荷兰国旗算法的原型,我们可以实现快速排序算法,流程是

arr[L……R]范围上,进行快速排序的过程如下

0)在这个范围上,随机选一个数记为num

1)用num对该范围使用荷兰国旗算法,< num 的数在左部分,== num 的数中间,> num 的数在右部分。假设== num的数所在范围是[a,b]

2)对arr[L..a-1]进行快速排序(递归)

3)对arr[b+1..R]进行快速排序(递归)

因为每一次荷兰国旗算法都会搞定一批数的位置且不会再变动,所以排序能完成

1)通过分析知道,划分值越靠近中间,性能越好;越靠近两边,性能越差

2)随机选一个数进行划分的目的就是让好情况和差情况都变成概率事件

3)把每一种情况都列出来,会有每种情况下的时间复杂度,但概率都是1/N

4)那么所有情况都考虑,时间复杂度就是这种概率模型下的长期期望!

时间复杂度O(N*logN),额外空间复杂度O(logN)都是这么来的。

题目链接:LintCode 464 · Sort Integers II

完整代码见

public class Solution {
    /**
     * @param a: an integer array
     * @return: nothing
     */
    public static void sortIntegers2(int[] arr) {
        if (null == arr || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    public static void process(int[] arr, int s, int e) {
        if (s >= e) {
            return;
        }
        swap(arr, e, s + (int) (Math.random() * (e - s)));
        int[] range = sortColors(arr, s, e);
        process(arr, s, range[0] - 1);
        process(arr, range[1] + 1, e);
    }

    public static void swap(int[] arr, int i, int j) {
        if (i == j) {
            return;
        }
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

    public static int[] sortColors(int[] arr, int s, int e) {
        int l = s - 1;
        int r = e + 1;
        int p = arr[e];
        int i = s;
        while (i < r) {
            if (arr[i] > p) {
                swap(arr, i, --r);
            } else if (arr[i] < p) {
                swap(arr, i++, ++l);
            } else {
                i++;
            }
        }
        return new int[]{l + 1, r - 1};
    }
}

更多

算法和数据结构笔记

参考资料

算法和数据结构体系班-左程云

标签:国旗,int,arr,++,算法,数组,排序
From: https://www.cnblogs.com/greyzeng/p/16739515.html

相关文章

  • GC 清除算法--常用垃圾回收算法和常用垃圾回收器
    1:Mark-Sweep(标记清除)缺点-- 碎片话特别严重2:Copying(拷贝)找到可用的一半复制到另外一半,再把以前的一半给清除掉; 缺点:浪费内存3:Mark-Compact(标记压缩) --......
  • AcWing 算法提高课 treap平衡树
    1、基本性质tree+heap=treap平衡树包含treap红黑树splaysbtAVL等等splay比较常用treap=①BST二叉搜索树+②heap2、set不能做的操作  ⑤和⑥这种与排名相......
  • DFS算法练习 POJ1111; POJ1129; POJ2245; POJ2657
    POJ1111:importjava.util.Scanner;/***@Authorjinjun99*@DateCreatedin2022/9/279:49*@Description*@Sinceversion-1.0*/publicclassMain{......
  • 16 -- 排序算法之插入排序
    算法介绍:插入排序属于内部排序法,时对于待排序的元素以插入的方式找到改元素的适当位置,以达到排序的目的。【类似于生活中的斗地主游戏,每抓起一张牌按照便把改张牌按照指定......
  • 克鲁斯卡尔算法
    应用场景某城市新增7个站点(A,B,C,D,E,F,G),现在需要修路把7个站点连通各个站点的距离用边线表示(权),比如A–B距离12公里问:如何修路保证各个站点都能连通......
  • 排序
    Learningtorank指标介绍MAP(MeanAveragePrecision):假设有两个主题,主题1有4个相关网页,主题2有5个相关网页。某系统对于主题1检索出4个相关网页,其rank分别为1,2,4,......
  • AcWing 算法提高课 可持久化
    可持久化的前提:数据结构本身的拓扑结构不变trie、线段树、树状数组、堆等都可持久化平衡树(一般)需要左旋和右旋,不可持久化  可持久化希望将数据结构的全部修改记录下......
  • 分布式自增ID算法Snowflake简介
    背景过去的项目开发中,我们常常选用的数据库是mysql,mysql以其体积小、速度快等优势,备受中小型项目的青睐。随着项目数据量的迅速增长,mysql已无法满足我们的项目需求,数据迁移......
  • 贪心算法
    应用实例假设存在如下表的需要付费的广播台,以及广播台信号可以覆盖的地区。如何选择最少的广播台,让所有的地区都可以接收到信号思路分析目前并没有算法可以快速......
  • csp模拟13[排序,Xorum, 有趣的区间问题,无聊的卡牌问题]
    排序对于这个题,它真的很妙,我们可以先考虑一下(如果\(a\)是排列)暴力怎么打。考虑两个数,他们互为逆序对,如果交换它们两个,如何让影响降到最小?那就是在他俩交换之后,他......