Java综合整理堆排序 快速排序 归并排序

目录
  • 堆排序
  • 快速排序
    • 递归
    • 非递归
  • 归并排序
    • 递归
    • 非递归

堆排序

  • 时间复杂度:0(N*log(N))
  • 空间复杂度:0(1)
  • 稳定性:不稳定
private static void heapSort(int[] arr) {
		//建堆
        crearHeap(arr);
        for (int i = 0; i < arr.length-1; i++) {
            int heapSize=arr.length-i;
            swap(arr,heapSize-1,0);
            heapSize--;
            shiftDown(arr,heapSize,0);
        }
        System.out.println(Arrays.toString(arr));
    }

    private static void crearHeap(int[] arr) {
    	// 从后往前遍历(右边非叶子节点开始), 依次进行向下调整
        for (int i = (arr.length-1-1)/2; i >=0 ; i--) {
            shiftDown(arr,arr.length,i);
        }

    }
	//向下调整,形成大堆
    private static void shiftDown(int[] arr, int size, int i) {
        int parent = i;
        int child = parent*2+1;
        while (child<size){
            if (child +1< size && arr[child +1]> arr[child]){
                child=child+1;
            }
            if (arr[child]>arr[parent]){
                swap(arr,child,parent);
            }else {
                break;
            }
            parent=child;
            child=parent*2+1;
        }
    }
	//交换
    private static void swap(int[] arr, int child, int parent) {
        int tmp =arr[child];
        arr[child] =arr[parent];
        arr[parent]=tmp;
    }

快速排序

  • 时间复杂度:O(N^ logN) 最坏的时候O(N^2) 和基准值密切相关
  • 空间复杂度:0(logN) 最坏的时候O(N)
  • 稳定性:不稳定

递归

private static void quick(int[] arr) {
        quickSortHelper(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    private static void quickSortHelper(int[] arr, int left, int right) {
        if (left>=right){
            //区间只有一个元素,或者零个元素
            return;
        }
        int index = partition(arr,left,right);
        quickSortHelper(arr,left,index-1);
        quickSortHelper(arr,index+1,right);
    }

    private static int partition(int[] arr, int left, int right) {
        int i=left;
        int j=right;
        int baseValue=arr[right];
        while (i<j){
            while (i<j && arr[i]<=baseValue){
                i++;
            }
            while (i<j && arr[j]>=baseValue){
                j--;
            }
            if (i<j){
                swap(arr,i,j);
            }
        }
        swap(arr,i,right);
        return i;
    }

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

非递归

public static void quickSortByLoop(int[] arr) {
        Stack<Integer> stack =new Stack<>();
        stack.push(0);
        stack.push(arr.length-1);
        while (!stack.isEmpty()){
            int right = stack.pop();
            int left = stack.pop();
            if (left>=right){
                continue;
            }
            int index = partition(arr,left,right);
            //右子树
            stack.push(index+1);
            stack.push(right);
            //左子树
            stack.push(left);
            stack.push(index-1);
        }
        System.out.println(Arrays.toString(arr));
    }

    private static int partition(int[] arr, int left, int right) {
        int baseValue =arr[right];
        int i =left;
        int j =right;
        while (i<j){
            while (i<j && arr[i]<=baseValue){
                i++;
            }
            while (i<j && arr[j]>=baseValue){
                j--;
            }
            if (i<j){
                swap(arr,i,j);
            }
        }
        swap(arr,i,right);
        return i;
    }

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

归并排序

  • 时间复杂度:O(NlogN)
  • 空间复杂度:O(N) 如果是链表,可以为O(1)
  • 稳定性:稳定

递归

public static void mergeSort(int[] arr){
        mergeSortHelper(arr,0,arr.length);
        System.out.println(Arrays.toString(arr));
    }

    private static void mergeSortHelper(int[] arr, int left, int right) {
        if (right-left<=1){
            return;
        }
        int mid = (right+left)/2;

        mergeSortHelper(arr,left,mid);
        mergeSortHelper(arr,mid,right);
        merge(arr,left,mid,right);
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int cur1 =left;
        int cur2 =mid;
        //两个数组合并后的结果
        int[] output=new int[right-left];
        int outputIndex=0;

        while (cur1<mid && cur2<right){
            if (arr[cur1]<=arr[cur2]) {
                output[outputIndex++] = arr[cur1++];
            }else {
                output[outputIndex++] = arr[cur2++];
            }
        }
        while (cur1<mid){
            output[outputIndex++] = arr[cur1++];
        }
        while (cur2<right){
            output[outputIndex++] = arr[cur2++];
        }

        for (int i = 0; i < right-left ; i++) {
            arr[left+i] = output[i];
        }
    }

非递归

public static void mergeSortByLoop(int[] arr){
        // gap 当前每个组中的元素个数.
        for (int gap =1;gap<arr.length;gap*=2){
            for (int i = 0; i <arr.length ; i+=2*gap) {
                //相当于把两个长度为 gap 的相邻组进行了合并
                int left =i;
                int mid =i+gap;
                int right=i+2*gap;
                if (mid > arr.length){
                    mid =arr.length;
                }
                if (right>arr.length){
                    right=arr.length;
                }
                merge(arr,left,mid,right);
            }
        }
        System.out.println(Arrays.toString(arr));
    }

到此这篇关于Java综合整理堆排序 快速排序 归并排序的文章就介绍到这了,更多相关Java 排序算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • JAVA堆排序算法的讲解

    预备知识 堆排序 堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序.首先简单了解下堆结构. 堆 堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆:或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆.如下图: 同时,我们对堆中的结点按层进行编号,将这种逻辑结构映射到数组中就是下面这个样子 该数组从逻辑上讲就是一个堆结构,我们用简单的公式来描述一下堆的定义就是: 大顶

  • Java 十大排序算法之堆排序刨析

    二叉堆是完全二叉树或者是近似完全二叉树. 二叉堆满足二个特性︰ 1.父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值. 2.每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆). 任意节点的值都大于其子节点的值--大顶堆(最后输出从小到大排) 任意节点的值都小于其子节点的值---小顶堆(最后输出从大到小排) 堆排序步骤 1.堆化,反向调整使得每个子树都是大顶或者小顶堆(建堆) 2.按序输出元素∶把堆顶和最末元素对调,然后调整堆顶元素(排序) 堆排序代码实现(大顶堆) publ

  • JAVA十大排序算法之堆排序详解

    目录 堆排序 知识补充 二叉树 满二叉树 完全二叉树 二叉堆 代码实现 时间复杂度 算法稳定性 思考 总结 堆排序 这里的堆并不是JVM中堆栈的堆,而是一种特殊的二叉树,通常也叫作二叉堆.它具有以下特点: 它是完全二叉树 堆中某个结点的值总是不大于或不小于其父结点的值 知识补充 二叉树 树中节点的子节点不超过2的有序树 满二叉树 二叉树中除了叶子节点,每个节点的子节点都为2,则此二叉树为满二叉树. 完全二叉树 如果对满二叉树的结点进行编号,约定编号从根结点起,自上而下,自左而右.则深度为k的,有

  • Java 十大排序算法之归并排序刨析

    目录 归并排序原理 归并排序API设计 归并排序代码实现 归并排序的时间复杂度分析 归并排序原理 1.尽可能的一组数据拆分成两个元素相等的子组,并对每一个子组继续拆分,直到拆分后的每个子组的元素个数是1为止. ⒉将相邻的两个子组进行合并成一个有序的大组. 3.不断的重复步骤2,直到最终只有一个组为止. 归并排序API设计 类名 Merge 构造方法 Merge():创建Merge对象 成员方法 1.public static void sort(Comparable[] a):对数组内的元素进行

  • JAVA十大排序算法之归并排序详解

    目录 归并排序 怎么分 怎么治 代码实现 时间复杂度 算法稳定性 总结 归并排序 归并,指合并,合在一起.归并排序(Merge Sort)是建立在归并操作上的一种排序算法.其主要思想是分而治之.什么是分而治之?分而治之就是将一个复杂的计算,按照设定的阈值进行分解成多个计算,然后将各个计算结果进行汇总.即"分"就是把一个大的通过递归拆成若干个小的,"治"就是将分后的结果在合在一起. 若将两个有序集合并成一个有序表,称为2-路归并,与之对应的还有多路归并. 怎么分 对于

  • Java深入浅出理解快速排序以及优化方式

    可能经常看面经的同学都知道,面试所遇到的排序算法,快速排序占主要位置,热度只增不减啊,其次就是归并和堆排序. 其实以前写过一篇排序的文章,写的比较简单,只是轻描淡写.今天我再次重新拿起笔,将快速排序的几大优化,再次一一讲述一遍.各位同学,读完这篇文章,如若对你能够带来一些感悟,记得给个大大的赞哦!!! 前言 快速排序是在冒泡排序的基础之上,再次进行优化得来的.具体的步骤如下: 在待排序的序列中,选取一个数值,将大于它的数放到数组的右边,小于它的数放到数组的左边,等于它的数就放到数组的中间. 此时

  • Java实现堆排序和图解

    目录 堆排序基本介绍 堆排序基本思想 堆排序图解 步骤一 步骤二 代码实现 总结 堆排序基本介绍 1.堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序. 2.堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆, 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系. 3.每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆 4.大顶堆举例说明 大顶堆特点:arr[i]

  • 图解Java排序算法之堆排序

    目录 预备知识 堆排序 堆 堆排序基本思想及步骤 再简单总结下堆排序的基本思路: 总结 预备知识 堆排序 堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序.首先简单了解下堆结构. 堆 堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆:或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆.如下图: 同时,我们对堆中的结点按层进行编号,将这种逻辑结构映射到数组中就是下面

  • java实现堆排序以及时间复杂度的分析

    完全二叉树:从上到下,从左到右,每层的节点都是满的,最下边一层所有的节点都是连续集中在最左边. 二叉树的特点就是左子节点是父节点索引值的2倍加一,右子节点是父节点索引值的2倍加二 堆分为两种:大顶堆和小顶堆         大顶堆:在完全二叉树基础上,每个节点的值都大于或等于其左右子节点的值         小顶堆:在完全二叉树基础上,每个节点的值都大于或等于其左右子节点的值 堆排序就是根据先构建好的大顶堆或小顶堆进行排序的. 怎么构建大顶堆:         假如一个数组是:int[] arr

  • Java综合整理堆排序 快速排序 归并排序

    目录 堆排序 快速排序 递归 非递归 归并排序 递归 非递归 堆排序 时间复杂度:0(N*log(N)) 空间复杂度:0(1) 稳定性:不稳定 private static void heapSort(int[] arr) { //建堆 crearHeap(arr); for (int i = 0; i < arr.length-1; i++) { int heapSize=arr.length-i; swap(arr,heapSize-1,0); heapSize--; shiftDown(a

  • Java综合整理堆排序 快速排序 归并排序

    目录 堆排序 快速排序 递归 非递归 归并排序 递归 非递归 堆排序 时间复杂度:0(N*log(N)) 空间复杂度:0(1) 稳定性:不稳定 private static void heapSort(int[] arr) { //建堆 crearHeap(arr); for (int i = 0; i < arr.length-1; i++) { int heapSize=arr.length-i; swap(arr,heapSize-1,0); heapSize--; shiftDown(a

  • java数据结构排序算法之归并排序详解

    本文实例讲述了java数据结构排序算法之归并排序.分享给大家供大家参考,具体如下: 在前面说的那几种排序都是将一组记录按关键字大小排成一个有序的序列,而归并排序的思想是:基于合并,将两个或两个以上有序表合并成一个新的有序表 归并排序算法:假设初始序列含有n个记录,首先将这n个记录看成n个有序的子序列,每个子序列长度为1,然后两两归并,得到n/2个长度为2(n为奇数的时候,最后一个序列的长度为1)的有序子序列.在此基础上,再对长度为2的有序子序列进行亮亮归并,得到若干个长度为4的有序子序列.如此重

  • Java算法之堆排序代码示例

    堆是一种特殊的完全二叉树,其特点是所有父节点都比子节点要小,或者所有父节点都比字节点要大.前一种称为最小堆,后一种称为最大堆. 比如下面这两个: 那么这个特性有什么作用?既然题目是堆排序,那么肯定能用来排序.想要用堆排序首先要创建一个堆,如果对4 3 6 2 7 1 5这七个数字做从小到大排序,需要用这七个数创建一个最大堆,来看代码: public class HeapSort { private int[] numbers; private int length; public HeapSor

  • Java排序算法总结之归并排序

    本文实例讲述了Java排序算法总结之归并排序.分享给大家供大家参考.具体分析如下: 归并操作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作.和快速排序类似,让我们一起来看,归并在Java中的实现. 归并排序(Merge)是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的.然后再把有序子序列合并为整体有序序列. 归并排序是建立在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的

  • Java数据结构与算法之树(动力节点java学院整理)

    为什么使用树: 树结合了两种数据结构的有点:一种是有序数组,树在查找数据项的速度和在有序数组中查找一样快:另一种是链表,树在插入数据和删除数据项的速度和链表一样.既然这样,就要好好去学了.... (最主要讨论的是二叉树中的二叉搜索树,即一个节点的左子节点关键值小于这个节点,右子节点的关键值大于这个节点) 设计前的思考: 树-->元素(节点) class Node { public int iData ; public float fData ; public Node left ; public

  • Java异常继承结构解析_动力节点Java学院整理

    Java异常类层次结构图: 异常的英文单词是exception,字面翻译就是"意外.例外"的意思,也就是非正常情况.事实上,异常本质上是程序上的错误,包括程序逻辑错误和系统错误.比如使用空的引用.数组下标越界.内存溢出错误等,这些都是意外的情况,背离我们程序本身的意图.错误在我们编写程序的过程中会经常发生,包括编译期间和运行期间的错误,在编译期间出现的错误有编译器帮助我们一起修正,然而运行期间的错误便不是编译器力所能及了,并且运行期间的错误往往是难以预料的.假若程序在运行期间出现了错误

  • Nginx简介_动力节点Java学院整理

    1.什么是Nginx Nginx来自俄罗斯的Igor Sysoev在为Rambler Media(http://www.rambler.ru/)工作期间,使用C语言开发了Nginx.Nginx作为Web服务器,一直为俄罗斯著名的门户网站Rambler Media提供着出色.稳定的服务. Igor Sysoev将Nginx的代码开源,并且赋予其最自由的2-clause BSD-like license许可证.由于Nginx使用基于事件驱动的架构能够并发处理百万级别的TCP连接,高度模块化的设计和自

  • web压力测试工具_动力节点Java 学院整理

    0. Grinder –  Grinder是一个开源的JVM负载测试框架,它通过很多负载注射器来为分布式测试提供了便利. 支持用于执行测试脚本的Jython脚本引擎HTTP测试可通过HTTP代理进行管理.根据项目网站的说法,Grinder的 主要目标用户是"理解他们所测代码的人--Grinder不仅仅是带有一组相关响应时间的'黑盒'测试.由于测试过程可以进行编码--而不是简单地脚本 化,所以程序员能测试应用中内部的各个层次,而不仅仅是通过用户界面测试响应时间. 1. Pylot -Pylot 是

  • Java数据结构之链表(动力节点之Java学院整理)

    单链表: insertFirst:在表头插入一个新的链接点,时间复杂度为O(1) deleteFirst:删除表头的链接点,时间复杂度为O(1) find:查找包含指定关键字的链接点,由于需要遍历查找,平均需要查找N/2次,即O(N) remove:删除包含指定关键字的链接点,由于需要遍历查找,平均需要查找N/2次,即O(N) public class LinkedList { private class Data{ private Object obj; private Data next =

随机推荐