文档章节

算法从小白到大神之荷兰国旗问题&快排&堆排

须臾之余
 须臾之余
发布于 08/22 20:27
字数 1016
阅读 19
收藏 0

题目一:

给定一个数组arr,和一个数num,请把小于等于num的数放在数 组的左边,大于num的数放在数组的右边。
要求额外空间复杂度O(1),时间复杂度O(N)

问题二(荷兰国旗问题)
给定一个数组arr,和一个数num,请把小于num的数放在数组的 左边,等于num的数放在数组的中间,大于num的数放在数组的 右边。
要求额外空间复杂度O(1),时间复杂度O(N)

/**
 * 问题:(荷兰国旗问题)
 * 给定一个数组arr,和一个数num,请把小于num的数放在数组的 左边,等于num的数放在数组的中间,大于num的数放在数组的 右边。
 * 要求额外空间复杂度O(1),时间复杂度O(N)
 */
public class NetherLandsFlag {
    public static int[] partition(int [] arr,int L,int R,int num){
        int less=L-1;
        int more=R+1;
        int cur=L;
        while (cur<more){
            if (arr[cur]<num){
                swap(arr,++less,cur++);
            }else if(arr[cur]>num){
                swap(arr,--more,cur);
            }else {
                cur++;
            }
        }
        return arr;
    }

    private static void swap(int[] arr, int i, int j) {
        arr[i]=arr[i]^arr[j];
        arr[j]=arr[i]^arr[j];
        arr[i]=arr[i]^arr[j];
    }
    public static int [] generateArray(){
        int [] arr=new int[10];
        for (int i = 0; i < arr.length; i++) {
            arr[i]=(int)(Math.random()*3);
        }
        return arr;

    }

    public static void main(String[] args) {
        int [] arr=generateArray();
        int[] res=partition(arr,0,arr.length-1,2);
        System.out.println(Arrays.toString(res));
    }
}

题目二:

随机快速排序的细节和复杂度分析
可以用荷兰国旗问题来改进快速排序
时间复杂度O(N*logN),额外空间复杂度O(logN)

/**
 * 快排
 */
public class QuickSort {
    public static void quickSort(int [] arr){
        if (arr==null || arr.length<2){
            return;
        }
        quickSort(arr,0,arr.length-1);
    }

    private static void quickSort(int[] arr, int L, int R) {
        if (L<R){
            int [] p=partition(arr,L,R);
            quickSort(arr,L,p[0]-1);
            quickSort(arr,p[1]+1,R);
        }
    }

    private static int[] partition(int[] arr, int L, int R) {
        int less=L-1;
        int more=R;
        int cur=L;
        while (cur<more){
            if (arr[cur] < arr[R]) {
                swap(arr,++less,cur++);
            }else if(arr[cur]> arr[R]){
                swap(arr,--more,cur);
            }else {
                cur++;
            }
        }
        swap(arr,more,R);
        return new int[]{less+1,more};
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int [] arr={12,10,4,10,10,8,9,10};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

题目三
堆排序的细节和复杂度分析
时间复杂度O(N*logN),额外空间复杂度O(1)
堆结构非常重要

1,堆结构的heapInsert与heapify

2,堆结构的增大和减少

3,如果只是建立堆的过程,时间复杂度为O(N)

4,优先级队列结构,就是堆结构

/**
 *  堆排
 */
public class HeapSort {
    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        int size = arr.length;
        swap(arr, 0, --size);
        while (size > 0) {
            heapify(arr, 0, size);
            swap(arr, 0, --size);
        }
    }

    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    public static void heapify(int[] arr, int index, int size) {
        int left = index * 2 + 1;
        while (left < size) {
            int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }

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

    public static void main(String[] args) {
        int []arr={1,34,4,5,76,8,9};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

有关排序问题的补充:

1,归并排序的额外空间复杂度可以变成O(1),但是非常难,不 需要掌握,可以搜“归并排序 内部缓存法”

2,快速排序可以做到稳定性问题,但是非常难,不需要掌握, 可以搜“01 stable sort”

3,有一道题目,是奇数放在数组左边,偶数放在数组右边,还 要求原始的相对次序不变,碰到这个问题,可以怼面试官。面试官非良人。

参考:牛客算法进阶

 

© 著作权归作者所有

须臾之余
粉丝 125
博文 68
码字总数 178724
作品 0
吉安
程序员
私信 提问
快速排序,找中位

陆小凤原创 小白:快速排序算法,这么上古的东西,而且每一种语言都有相应的实现,还需要学吗? 陆小凤:如果目标是解决常规的业务开发,那就没有理由去做这样的事情,有时间还不如去理解业务...

奇哥十年程序
2017/12/08
0
0
排序算法C语言实现——冒泡、快排、堆排对比

对冒泡、快排、堆排这3个算法做了验证,结果分析如下: 一、结果分析 时间消耗:快排 < 堆排 < 冒泡。 空间消耗:冒泡O(1) = 堆排O(1) < 快排O(logn)~O(n) 。 应用推荐:   1、速度最快、且...

Jo_ZSM
2018/10/14
0
0
【Top K 问题】[Leetcode-215] Kth Largest Element in an Array 数组中第K大的数

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/xidiancoder/article/details/77781379 0. 本文概要 Top K问题在大数据领域非常普遍,而且是在面试中经常被提...

zxca368
2017/09/02
0
0
数据结构学习(一)

数据结构与算法 1. 链表与数组。 2. 队列和栈,出栈与入栈。 3. 链表的删除、插入、反向。 4. 字符串操作。 5. Hash表的hash函数,冲突解决方法有哪些。 6. 各种排序:冒泡、选择、插入、希尔...

技术小甜
2017/11/16
0
0
算法初级02——荷兰国旗问题、随机快速排序、堆排序

题目一 给定一个数组arr,和一个数num,请把小于等于num的数放在数组的左边,大于num的数放在数组的右边。 要求额外空间复杂度O(1),时间复杂度O(N) 参考下面的代码即可 问题二(荷兰国旗问题...

kent鹏
2018/11/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

实战项目-学成在线(一)

之前看的黑马程序员实战项目之一,打算以博客的形式写出来,也让自己重新温习一下。 1、项目背景 略(就是当前这东西很火,我们重点在开发,这些就略过) 2、功能模块 门户,学习中心,教学管...

lianbang_W
18分钟前
1
0
基于Vue的数字输入框组件开发

本文转载于:专业的前端网站➫基于Vue的数字输入框组件开发 1、概述 Vue组件开发的API:props、events和slots 2、组件代码 github地址:https://github.com/MengFangui/VueInputNumber 效果:...

前端老手
27分钟前
2
0
百度地图根据经纬度获取运动轨迹

<!DOCTYPE html><html><head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <meta name="viewport" content="initial-scale=1.0, user-scalable=n......

泉天下
29分钟前
4
0
学习记录(day04-axios增删改查、v-for循环、页面加载成功处理函数)

[TOC] 1.1 基本语法:插值表达式 <template> <div> {{username}} <br/> {{1+2+3}} <br/> {{'你的名字是:' + username}} <br/> {{'abc'.split('')}} </div><......

庭前云落
今天
3
0
CentOS Linux 7上将ISO映像文件写成可启动U盘

如今,电脑基本上都支持U盘启动,所以,可以将ISO文件写到U盘上,用来启动并安装操作系统。 我想将一个CentOS Linux 7的ISO映像文件写到U盘上,在CentOS Linux 7操作系统上,执行如下命令: ...

大别阿郎
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部