文档章节

常见排序之Java实现

绝世武神
 绝世武神
发布于 2016/07/09 18:00
字数 985
阅读 166
收藏 11

主程序

public class Test {
    public static void main(String[] args) {
        int[] arrs = {1, 9, 4, 50, 63, 82, 37} ;
        System.out.println(Arrays.toString(arrs)) ;
        //mergeSort(arrs, 0, arrs.length-1) ;    
        //quickSort(arrs, 0, arrs.length - 1) ;
        heapSort(arrs) ;
        System.out.println(Arrays.toString(arrs)) ;
    }

}

交换数组中的两个元素

    private static void swap(int[] array, int low, int high) {
        int temp = array[low] ;
        array[low] = array[high] ;
        array[high] = temp ;
    }

插入排序

    public static void insertSort(int[] arr) {
        int key ;   //用于保存要插入的值
        for(int i=1 ; i<=arr.length-1 ; i++) {
            key = arr[i] ;
            for(int j=i-1 ; j>=0 ; j--) {
                if(key < arr[j]) {
                    arr[j+1]=arr[j] ;   //记录后移
                }
                else {
                    arr[j+1] = key ;    //找到插入的位置
                    break ;
                }
            }
        }
    }

选择排序(当前元素 VS 余下元素)

    public static void selectSort(int[] arr) {
        for(int i=0; i<=arr.length-2; i++) {
            for(int j=i+1; j<=arr.length-1; j++) {
                if(arr[i] > arr[j]) {
                    swap(arr, i, j) ;
                }
            }
        }
    }

冒泡排序(两两比较)

    public static void bubbleSort(int[] arr) {
        for(int i=arr.length-1; i>=1; i--) {
            for(int j=0; j<=i-1; j++) {
                if(arr[j] > arr[j+1]) {
                    swap(arr, j, j+1) ;
                }
            }
        }
    }

二路归并排序(递归版本)

    public static void mergeSort(int[] arr, int low, int high) {
        if(low < high) {
            int mid = (low+high) / 2 ;
            mergeSort(arr, low, mid) ;
            mergeSort(arr, mid+1, high) ;
            merge(arr, low, mid, high) ;
        }
    }

    public static void merge(int[] arr, int left, int center, int right) {
        int[] temp = new int[right-left+1] ;    //归并排序的空间复杂度为O(n)
        int k = 0 ;
        int r1 = center+1 ;     //右边起始下标
        int start = left ;      //保存拷贝的起始位置

        while(left<=center && r1<=right) {
            if(arr[left] < arr[r1]) { temp[k++] = arr[left++] ; }
            else { temp[k++] = arr[r1++] ; }
        }

        //拷贝剩余元素
        while(left <= center) { temp[k++] = arr[left++] ; }
        while(r1 <= right) { temp[k++] = arr[r1++] ; }

        //将临时数组中的元素拷贝至原数组
        k = 0 ;
        for(int i=start; i<=right ; i++) { arr[i] = temp[k++] ; }
    }

二路归并排序(非递归版本)

    public static void mergeSort(int[] arr) {
        int length = arr.length ;
        int low, mid, high ;
        for(int step = 1 ; step <= length; step*=2) {   //step为步长
            low = 0 ;
            while(low+step <= length) {
                mid = low + step - 1 ;
                high = mid + step ;
                if(high >= length) { high = length - 1 ; }      //元素个数小于step
                merge(arr, low, mid, high);
                low = high + 1 ;    //下次归并的下界
            }
        }
    }

    public static void merge(int[] arr, int left, int center, int right) {
        int[] temp = new int[right-left+1] ;    //归并排序的空间复杂度为O(n)
        int k = 0 ;
        int r1 = center+1 ;     //右边起始下标
        int start = left ;      //保存拷贝的起始位置

        while(left<=center && r1<=right) {
            if(arr[left] < arr[r1]) { temp[k++] = arr[left++] ; }
            else { temp[k++] = arr[r1++] ; }
        }

        //拷贝剩余元素
        while(left <= center) { temp[k++] = arr[left++] ; }
        while(r1 <= right) { temp[k++] = arr[r1++] ; }

        //将临时数组中的元素拷贝至原数组
        k = 0 ;
        for(int i=start; i<=right ; i++) { arr[i] = temp[k++] ; }
    }

快速排序(递归版本)

    public static void quickSort(int[] array, int low, int high) {
        if(low < high) {
            int i = partition(array, low, high) ;
            quickSort(array, low, i-1);
            quickSort(array, i+1, high);
        }
    }

    private static int partition(int[] array, int low, int high) {
        int pivot = array[low] ;

        while(low < high) {
            while(low < high && pivot <= array[high]) { high-- ; }
            swap(array, low, high) ;
            while(low < high && pivot >= array[low]) { low++ ; }
            swap(array, low, high) ;
        }

        return low ;
    }

快速排序(非递归版本)

    public static void quickSort(int[] array) {
        if(array==null || array.length==1) { return ; }

        //保存划分后所形成空间的左右端点
        Stack<Integer> stack = new Stack<Integer>() ;
        stack.push(0) ;
        stack.push(array.length - 1) ;
        int low, high ;
        while(! stack.isEmpty()) {
            high = stack.pop() ;
            low = stack.pop() ;

            if(low >= high) { continue ; }
            int i = partition(array, low, high) ;

            stack.push(low) ;   //保存左边的区间
            stack.push(i-1) ;

            stack.push(i+1) ;   //保存右边的区间
            stack.push(high) ;
        }
    }

    private static int partition(int[] array, int low, int high) {
        int pivot = array[low] ;

        while(low < high) {
            while(low < high && pivot <= array[high]) { high-- ; }
            swap(array, low, high) ;
            while(low < high && pivot >= array[low]) { low++ ; }
            swap(array, low, high) ;
        }

        return low ;
    }

堆排序

    public static void heapSort(int[] heap) {
        buildHeap(heap) ;   //构建堆

        for(int size=heap.length-1 ; size >= 1 ; ) {
            swap(heap, 0, size);    //交换首末元素
            adjustHeap(heap, --size, 0);  //对剩余元素进行调整
        }
    }

    public static void buildHeap(int[] heap) {
        int size = heap.length-1 ;
        //自底向上调整堆
        for(int begin = size/2 ; begin>=0 ; begin--){
            adjustHeap(heap, size, begin) ;
        }
    }

    public static void adjustHeap(int[] heap, int size, int start) {
        int big = start ;   //保存较大元素下标
        int left = 2*start + 1 ;    //左叶子节点
        int right = 2*start + 2 ;   //右叶子节点
        while(left<=size || right<=size) {
            if(left<=size && heap[left]>heap[big]) { big=left ; }
            if(right<=size && heap[right]>heap[big]) { big=right ; }

            if(start == big) {  break ; }   //调整完毕
            else {
                swap(heap, start, big) ;    //较大元素上浮
                start = big ;
                left = 2*start + 1 ;
                right = 2*start + 2 ;
            }
        }
    }

© 著作权归作者所有

绝世武神
粉丝 20
博文 33
码字总数 48343
作品 0
海淀
程序员
私信 提问
函数式编程 - Type Class 介绍

什么是 Type Class ? Type Class (类型类) 的概念来自 Haskell,表示一系列函数的集合,在概念上, Type Class 和面向对象领域的泛型接口比较类似。 由于 Haskell 是一门纯函数式编程语言,...

joymufeng
2018/10/07
52
0
Java PriorityQueue && PriorityBlockingQueue

Java PriorityQueue && PriorityBlockingQueue 我们知道队列是遵循先进先出(First-In-First-Out)模式的,但有些时候需要在队列中基于优先级处理对象。举个例子,比方说我们有一个每日交易时...

秋风醉了
2015/01/12
194
0
可视化的数据结构和算法

还记得之前发布过的那个关于可视化排序的文章吗?在网上又看到了一个旧金山大学David Galles做的各种可视化的数据结构和基本算法的主页,网址在这里,大家可以看看。我把这个页面的目录列在下...

戴威
2011/05/12
1K
5
《数据结构与算法系列》合集整理

《数据结构与算法系列》合集整理 整理来自博客园skywang12345,以下摘自作者介绍: “最近抽空整理了"数据结构和算法"的相关文章。在整理过程中,对于每种数据结构和算法分别给出"C"、"C++"...

kaixin_code
2018/12/01
152
0
在 Hibernate 中直接操作 JDBC 接口

简介: Hibernate 在处理多表关联及分组排序等复杂数据库查询操作时,其固有的 O-R 映射机制会产生大量冗余 SQL 操作,系统性能比传统的 JDBC 低很多。本文分析了 Hibernate 产生此类问题的原...

红薯
2010/04/16
776
2

没有更多内容

加载失败,请刷新页面

加载更多

OpenStack 简介和几种安装方式总结

OpenStack :是一个由NASA和Rackspace合作研发并发起的,以Apache许可证授权的自由软件和开放源代码项目。项目目标是提供实施简单、可大规模扩展、丰富、标准统一的云计算管理平台。OpenSta...

小海bug
昨天
5
0
DDD(五)

1、引言 之前学习了解了DDD中实体这一概念,那么接下来需要了解的就是值对象、唯一标识。值对象,值就是数字1、2、3,字符串“1”,“2”,“3”,值时对象的特征,对象是一个事物的具体描述...

MrYuZixian
昨天
6
0
数据库中间件MyCat

什么是MyCat? 查看官网的介绍是这样说的 一个彻底开源的,面向企业应用开发的大数据库集群 支持事务、ACID、可以替代MySQL的加强版数据库 一个可以视为MySQL集群的企业级数据库,用来替代昂贵...

沉浮_
昨天
6
0
解决Mac下VSCode打开zsh乱码

1.乱码问题 iTerm2终端使用Zsh,并且配置Zsh主题,该主题主题需要安装字体来支持箭头效果,在iTerm2中设置这个字体,但是VSCode里这个箭头还是显示乱码。 iTerm2展示如下: VSCode展示如下: 2...

HelloDeveloper
昨天
7
0
常用物流快递单号查询接口种类及对接方法

目前快递查询接口有两种方式可以对接,一是和顺丰、圆通、中通、天天、韵达、德邦这些快递公司一一对接接口,二是和快递鸟这样第三方集成接口一次性对接多家常用快递。第一种耗费时间长,但是...

程序的小猿
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部