首页 / 算法 / 【算法拾遗（java描写叙述）】--- 选择排序（直接选择排序、堆排序）

【算法拾遗（java描写叙述）】--- 选择排序（直接选择排序、堆排序）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【算法拾遗（java描写叙述）】--- 选择排序（直接选择排序、堆排序），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3539字，纯文字阅读大概需要6分钟。

内容图文

选择排序的基本思想

每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，知道所有记录排序完毕。主要有两种选择排序方法：直接选择排序（或称简单选择排序）和堆排序。

直接选择排序

基本思想

第i趟排序開始时，当前有序区和无序区分别为R[1 …… i-1]和R[i …… n](1 <= i <= n-1),该趟排序则是从当前无序区中选出关键字最小的记录R[k],将它与无序区的第一个记录R[i]交换，使R[1 …… i]和R[i+1 …… n]分别变为新的有序区和新的无序区。

由于每趟排序均使有序区中添加了一个记录，且有序区中的记录关键字均不大于无序区中记录的关键字，即第i趟排序之后R[1 …… i].keys <= R[i+1 …… n].keys,所以进行n-1趟排序之后有R[1 …… n-1].keys <= R[n].key,即经过n-1趟排序之后，整个文件R[1 …… n]递增有序。注意，第一趟排序開始时。无序区为R[1 …… n]，有序区为空。

技术分享

java程序

                
                    /*************************
 * 
 * 直接选择排序(简单选择排序)
 *
 *************************/
                    public
                    
                        class
                        SelectSort {
                    private
                    void
                    selectSort(int[] datas) {
        if (datas == null || datas.length < 2)
            return;
        int minValue;// 无序区最小值变量for (int i = 0; i < datas.length - 1; i++) {
            minValue = datas[i];// 将最小值变量初始化为无序区第一个位置上的值for (int j = i + 1; j < datas.length; j++) {
                if (datas[j] < minValue) {
                    minValue = datas[j];
                    // 交换两数值int temp = datas[i];
                    datas[i] = minValue;
                    datas[j] = temp;
                }
            }
        }

    }

    publicstaticvoidmain(String[] args) {
        int[] datas = newint[] { 8, 5, 2, 6, 9, 3, 1, 4, 0, 7 };
        System.out.println("********排序前********");
        for (int i = 0; i < datas.length; i++) {
            System.out.print(datas[i] + ",");
        }
        SelectSort selectSort = new SelectSort();
        selectSort.selectSort(datas);
        System.out.println("\n********排序后********");
        for (int i = 0; i < datas.length; i++) {
            System.out.print(datas[i] + ",");
        }
    }

}

性能分析

  1. 平均时间复杂度为O（n2）
  2. 直接选择排序属于就地排序
  3. 直接选择排序是不稳定的

堆排序

基本思想

堆排序是利用全然二叉树进行排序的方法

堆首先是一棵全然二叉树。

然后满足一下条件之中的一个：

(1) Ki <= K2i 而且Ki <= K2i+1

(2) Ki >= K2i 而且Ki >= K2i+1

堆有大根堆（或根结点关键字值最大的堆）和小根堆（根结点关键字最小）之分。

大根堆排序算法的基本操作：初始化操作是将R[1 …… n]构造为初始堆；每一趟排序的基本操作是将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换。然后将新的无序区调整为堆（亦称为重建堆）。

显然仅仅须要做n-1趟排序。选出较大的n-1个关键字就可以使文件递增有序。用小根堆排序全然与此类同，仅仅只是其排序结果是递减有序的。

技术分享

java程序

                
                    public
                    
                        class
                        HeapSort {
                    /**
     * 建立大根堆
     * 
     * @param datas
     *            待排数组
     * @param s
     *            父节点
     * @param length
     *            无序项的个数
     */
                    private
                    void
                    creatHeap(int[] datas, int s, int length) {
        int temp = datas[s];
        for (int j = 2 * s; j <= length; j *= 2) {
            if (j < length && datas[j] < datas[j + 1])
                ++j;// j是关键字中较大的记录的下标if (temp >= datas[j])
                break;
            datas[s] = datas[j];// 将最大值赋予父节点
            s = j;
        }
        datas[s] = temp;// 将原父节点的值赋予拥有最大值的子节点。完毕终于的交换
    }

    /**
     * 堆排序
     * 
     * @param datas
     *            待排序的数组
     * @param index
     *            待排序数组中待排项的个数
     */privatevoidheapSort(int[] datas, int index) {
        if (datas == null || index < 2)
            return;
        for (int i = index / 2; i > 0; i--) {
            creatHeap(datas, i, index);
        }
        for (int i = index; i > 1; i--) {
            int temp = datas[i];
            datas[i] = datas[1];
            datas[1] = temp;
            // 对其余数值进行重建堆操作
            creatHeap(datas, 1, i - 1);
        }
    }

    publicstaticvoidmain(String[] args) {
        int[] datas = newint[10];
        datas[1] = 6;
        datas[2] = 5;
        datas[3] = 3;
        datas[4] = 1;
        datas[5] = 8;
        datas[6] = 7;
        datas[7] = 2;
        datas[8] = 4;
        datas[9] = 9;
        int index = 9;
        System.out.println("********排序前********");
        for (int i = 1; i < index + 1; i++) {
            System.out.print(datas[i] + ",");
        }

        HeapSort heapSort = new HeapSort();
        heapSort.heapSort(datas, index);

        System.out.println("\n********排序后********");
        for (int i = 1; i < index + 1; i++) {
            System.out.print(datas[i] + ",");
        }
    }

}

性能分析

堆排序的时间主要是由建立初始堆和重复重建堆这两部分的时间开销构成，它们均是通过调用HeapSort实现的。

  1. 堆排序的最坏时间复杂度为O（nlgn）。堆排序的平均时间性能较接近于最坏性能
  2. 由于建初始堆所需的比較次数较多，所以堆排序不适宜于记录数比較少的文件
  3. 堆排序是就低排序，辅助空间为O（1）
  4. 堆排序的时间复杂度为O（nlgn），是一种不稳定的排序方法

參考资料：《数据结构与算法分析——java语言描写叙述》、《大话数据结构》

原文：http://www.cnblogs.com/mfmdaoyou/p/7089153.html

内容总结

以上是互联网集市为您收集整理的【算法拾遗（java描写叙述）】--- 选择排序（直接选择排序、堆排序）全部内容，希望文章能够帮你解决【算法拾遗（java描写叙述）】--- 选择排序（直接选择排序、堆排序）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1188754.html

来源：【匿名】