当前位置:首页 » 《资源分享》 » 正文

Java:选择排序

16 人参与  2024年09月30日 14:01  分类 : 《资源分享》  评论

点击全文阅读


目录

直接选择排序

 堆排序


基本思想

每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。

直接选择排序

思路1:

在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素若它不是这组元素中的最后一个(第一个)元素,则将它与这组元素中的最后一个(第一个)元素交换在剩余的array[i]--array[n-2](array[i+1]--array[n-1])集合中,重复上述步骤,直到集合剩余1个元素

 

    //选择排序    /**     * 时间复杂度:O(N^2) 和数据 是否有序无关     * 空间复杂度:O(1)     * 稳定性:不稳定     * @param array     */    public static void selectSort(int[] array){        for (int i = 0; i < array.length; i++) {            int minIndex = i;            for (int j = i+1; j < array.length; j++) {                if(array[j] < array[minIndex]){                    minIndex = j;                }            }            swap(array,i,minIndex);        }    }    private static void swap(int[] array, int i, int minIndex) {        int tmp = array[i];        array[i] = array[minIndex];        array[minIndex] = tmp;    }

 思路2:

定义left和right分别去找最大值和最小值对应的下标找到后进行交换一开始最大值和最小值下标均为left,为0

 

private static void swap(int[] array, int i, int minIndex) {    int tmp = array[i];    array[i] = array[minIndex];    array[minIndex] = tmp;}public static void selectSort1(int[] array){    int left = 0;    int right = array.length-1;    while(left < right){        int minIndex = left;        int maxIndex = left;        for (int i = left+1; i <= right; i++) {            if(array[i] < array[minIndex]){                minIndex = i;            }            if(array[i] > array[maxIndex]){                maxIndex = i;            }        }        swap(array, left, minIndex);        //确保最大值的位置,最大值正好是 left 下标        //此时把最大值换到了minIndex下标        if(maxIndex == 0){            maxIndex = minIndex;        }        swap(array, right, maxIndex);        left++;        right--;    }}

 堆排序

这里我们选择大根堆进行输出,首先通过向下调整来进行创建大根堆。

public static void createHeap(int[] array){    for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {        siftDown(array,parent,array.length);//向下调整,创建大根堆    }}public static void siftDown(int[] array, int parent, int length) {    int child = 2*parent+1;    while(child < length){        if(child + 1 < length && array[child] < array[child +1]){            child++;        }        if(array[child] > array[parent]){            swap(array, child, parent);            parent = child;            child = 2*parent+1;        }else{            break;        }    }

 然后再对大根堆进行输出,完整代码如下:

public static void heapSort(int[] array){    createHeap(array);    int end  = array.length-1;    while(end > 0){        swap(array, 0 ,end);        siftDown(array, 0,end);        end--;    }}public static void createHeap(int[] array){    for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {        siftDown(array,parent,array.length);//向下调整,创建大根堆    }}public static void siftDown(int[] array, int parent, int length) {    int child = 2*parent+1;    while(child < length){        if(child + 1 < length && array[child] < array[child +1]){            child++;        }        if(array[child] > array[parent]){            swap(array, child, parent);            parent = child;            child = 2*parent+1;        }else{            break;        }    }}


点击全文阅读


本文链接:http://zhangshiyu.com/post/166606.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 京圈佛子破戒后,我改嫁京圈纨绔(沈墨渊,白晶晶)
  • 前世被闺蜜害死,重生后我让她从太子妃变疯女苏婉儿,清歌完本_前世被闺蜜害死,重生后我让她从太子妃变疯女(苏婉儿,清歌)
  • 全书浏览七零军嫂太彪悍,带三宝上军区离婚(沈清落,陈桂花,陆有为)_七零军嫂太彪悍,带三宝上军区离婚(沈清落,陈桂花,陆有为)全书结局
  • 今天也没变成昨天(周扬陈默)全书免费_(周扬陈默)今天也没变成昨天后续(周扬陈默)
  • 重生后,秦总非要父以子贵(许沐晴,秦越泽)全书浏览_重生后,秦总非要父以子贵全书浏览
  • 他嫌弃我喝两块钱豆浆上不了台面,我结婚后他又哭又闹全书万照,白青青在线
  • 昭然若梦前尘烬列表_昭然若梦前尘烬(温昭然方池雲)
  • 导师借我股票账号,我倒欠五十万(孟潇潇,宁薇)_导师借我股票账号,我倒欠五十万孟潇潇,宁薇
  • 拒绝把外卖券给舍友,竹马送我到迪拜捡垃圾(周钰泽,蒋清清,思源)全书浏览_拒绝把外卖券给舍友,竹马送我到迪拜捡垃圾全书浏览
  • 我的人生,你已出局(程森凌古楚文)_我的人生,你已出局程森凌古楚文
  • 穿书成病娇女配,睁眼就签下离婚协议书(朱楼)_穿书成病娇女配,睁眼就签下离婚协议书
  • 老婆逼我给白月光捐肾,我死后她悔疯了(宋逸晨沈墨白)全书浏览_老婆逼我给白月光捐肾,我死后她悔疯了全书浏览

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1