• 网站首页
  • 微服务
  • 设计模式
  • 并发编程
  • 源码分析
  • 中间件
  • 数据库
  • 文献
  • 工具
  • 其他
  • 算法从小白到大神之荷兰国旗问题&快排&堆排

    发布时间: 2020-01-02 14:48首页:架构技术精选 > 文献 > 阅读()

     

    题目一:

    给定一个数组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,有一道题目,是奇数放在数组左边,偶数放在数组右边,还 要求原始的相对次序不变,碰到这个问题,可以怼面试官。面试官非良人。

    特别声明:文章内容仅供参考,不造成任何投资建议。投资者据此操作,风险自担。

    网站首页 - 微服务 - 设计模式 - 并发编程 - 源码分析 - 中间件 - 数据库 - 文献 - 工具 - 其他

    本站不良内容举报联系客服QQ:483966038 官方微信:MYKT-xiaowei 服务热线:

    未经本站书面特别授权,请勿转载或建立镜像

    Copyright © 2016-2020 架构技术精选 版权所有 XMl地图