文档章节

选择排序

datacube
 datacube
发布于 2016/08/05 18:49
字数 591
阅读 9
收藏 0
public class SelectSort {
    public static void main(String[] args) {
        int[] nums = {49,38,65,97,76,13,27,49};
//        simpleSelectSort(nums);
//        treeSelectSort(nums);
        heapSelectSort(nums);
        for (int num:nums) {
            System.out.print(num+"\t");
        }

    }
/**
简单排序处理流程
(1)从待排序序列中,找到关键字最小的元素;
(2)如果最小元素不是待排序序列的第一个元素,将其和第一个元素互换;
(3)从余下的 N - 1 个元素中,找出关键字最小的元素,重复(1)、(2)步,直到排序结束。
**/
    static void simpleSelectSort(int[] nums){//7,6,3,4,5
        for (int i = 0; i < nums.length; i++) {
            int minIndex = i;

            for (int j = i+1; j < nums.length; j++) {
                if (nums[minIndex]>nums[j]) {
                    minIndex = j;
                }
            }
            if (minIndex!=i) {
                int temp = nums[i];
                nums[i] = nums[minIndex];
                nums[minIndex] = temp;
            }
        }
    }

    static void treeSelectSort(int[] nums){//19 , 38 ,  65  ,97  , 76  ,13  , 27 , 49
        int len = nums.length;
        int treeSize = 2*len - 1;  //满二叉树的节点数
        int low = 0;
        int[] tree = new int[treeSize];//临时的树存储空间

        //由后向前填充此树,索引从0开始
        for (int i = len -1,j = 0;i >= 0;--i,j++){//填充叶子节点
            tree[treeSize - 1 - j] = nums[i];
        }
        for (int x:tree) {
            System.out.print(x+"\t");
        }
        System.out.println();
        for (int i = treeSize - 1; i > 0; i -=2){//填充非终端节点
//            System.out.println(i+"---"+((i - 1)/2));
            tree[(i-1)/2] = (tree[i - 1] < tree[i] ? tree[i - 1] : tree[i]);
        }
        for (int x:tree) {
            System.out.print(x+"\t");
        }
        System.out.println();
        //不断移走最小节点
        int minIndex;
        while (low < len){
            int min = tree[0]; //最小值
            nums[low++] = min;
            minIndex = treeSize - 1;
            while(tree[minIndex] != min){//不断移走最小节点
                minIndex--;
            }
            tree[minIndex] = Integer.MAX_VALUE;//设置一个最大值标志
            //找到其兄弟节点
            while (minIndex > 0){//如果其还有父节点     -->该步骤旨在重新生成一颗树
                if (minIndex % 2 == 0){//如果是右节点
                    tree[(minIndex - 1)/2] = (tree[minIndex - 1] < tree[minIndex] ? tree[minIndex - 1] : tree[minIndex]);
                    minIndex = (minIndex-1)/2;
                } else {//如果是左节点
                    tree[minIndex/2] = (tree[minIndex] < tree[minIndex + 1] ? tree[minIndex] : tree[minIndex + 1]);
                    minIndex = minIndex/2;
                }
            }
//            for (int x:tree) {
//                System.out.print(x+"\t");
//            }
//            System.out.println();
        }
    }

    static void heapSelectSort(int[] nums){
        int len = nums.length;
        //构建堆
        for (int i = (len -1)/2; i >= 0; i--) {
            heapAdjust(nums,i,len);
        }
        //输出堆顶元素并调整建新堆的过程
        int count = len-1;
        while(count > 0 ){
            //交换树根与最后一个值
            swap(nums,0,count);
            count -- ;
            heapAdjust(nums,0,count);
        }
    }

    static void heapAdjust(int[] nums, int i, int len) {
        int parent = nums[i];
        for (int j = (i+1)*2 - 1; j < len; j=(j+1)*2 - 1) {
            if (j < len -1 && nums[j] < nums[j+1]){
                ++j;
            }
            if (parent > nums[j]){
                break;
            }
            nums[i] = nums[j];
            i = j;
        }
        nums[i] = parent;
    }
    /**
     * 交换数组中两元素的值
     */
    private static void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

本文转载自:http://zhouyunan2010.iteye.com/blog/1217462

上一篇: mba数学-幂学-2016
下一篇: 堆和树的区别
datacube
粉丝 9
博文 607
码字总数 152394
作品 0
海淀
程序员
私信 提问

暂无文章

数组算法

/*数组的相关的算法操作:1、在数组中找最大值/最小值*/class Test11_FindMax{public static void main(String[] args){int[] array = {4,2,6,8,1};//在数组中找最大...

architect刘源源
48分钟前
2
0
okhttp3 以上版本在安卓9.0无法请求数据的解决方案

应用官方的说明:在 Android 6.0 中,我们取消了对 Apache HTTP 客户端的支持。 从 Android 9 开始,默认情况下该内容库已从 bootclasspath 中移除且不可用于应用。且Android P 限制了明文流量...

chenhongjiang
今天
11
0
简单示例:NodeJs连接mysql数据库

开篇引用网上的说法: 简单的说 Node.js 就是运行在服务端的 JavaScript。Node.js 是一个基于Chrome JavaScript 运行时建立的一个平台。Node.js是一个事件驱动I/O服务端JavaScript环境,基于...

李朝强
今天
8
0
大数据学习路线

年薪30W大数据学习路线图: 一、Hadoop入门,了解什么是Hadoop 1、Hadoop产生背景 2、Hadoop在大数据、云计算中的位置和关系 3、国内外Hadoop应用案例介绍 4、国内Hadoop的就业情况分析及课程...

陈小君
今天
3
0
解读 Kylin 3.0.0 | 更敏捷、更高效的 OLAP 引擎

在近期的 Apache Kylin Meetup 成都站上,我们邀请到 Kyligence 架构师 & Apache Kylin Committer 倪春恩对 Kylin 3.0.0 版本的一些重要功能及改进从使用到原理进行了介绍: Apache Kylin 在...

ApacheKylin
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部