美文网首页
数组 选择排序 冒泡

数组 选择排序 冒泡

作者: 张轻舟 | 来源:发表于2018-06-24 16:55 被阅读11次

    数组的排序

    像查找一样,排序也是计算机中常用的操作。这里介绍两种方法。

    选择排序

    假设要按升序排列一个数组。选择排序法先找到数列中最小的数,然后将它放在数列中的最前面。接下来再剩下的数中选择最小数,将它放在第一个的后面,以此类推,直到数列中仅剩一个数为止。

    看一张示例图,会讲解得更清楚:


    示例图

    下面显示了选择排序的程序:

    public static int[] SelectionSort(int[] arrays){
            //i表示交换的次数,从上面的图中就可以发现交换9次
            for (int i = 0; i < arrays.length - 1; i++) {
                int temp = 0;//用来保存最小的那个数
                int index = i; // 用来保存最小值的索引
    
                // 寻找第i个小的数值
                //这一次循环之后,index将获得最小值的索引
                for (int j = i + 1; j < arrays.length; j++) {
                    if (arrays[index] > arrays[j]) {
                        index = j;
                    }
                }
    
                // 交换位置,将找到的第i个小的数值放在第i个位置上
    
            //将最小值赋值给temp
                temp = arrays[index];
                arrays[index] = arrays[i];
                arrays[i] = temp;
    
    
        }
            return arrays;  
            }
    

    用下面的语句跟踪该方法

    int[] list = {3,5,23,45,1,66};
    
            int[] list2 = SelectionSort(list);
    
            System.out.println(Arrays.toString(list2));
    
    输出结果:
    [1, 3, 5, 23, 45, 66]
    

    冒泡排序

    在每次遍历数组中,对相邻的两个元素进行比较。如果这一对元素是降序,则交换他们的值;否则,保持值不变。

    看一个示例图,有时候图解比文字更清楚:


    示例图

    下面展示了运用冒泡排序算法对数列{2,9,5,4,8,1,6}进行排序:

    public static double[] bubbleSort(double[] arrays){
            int temp;
            //这里i表示交换的几次,比如上面图中52换到第一位一共进行了三次交换
            for(int i = 0;i<arrays.length-1;i++){
            //从后向前依次的比较相邻两个数的大小,遍历一次后,把数组中第i小的数放在第j个位置上
            //这里j表示交换后它所处的位置,比如,第一次j=3,是因为52跟59交换之后到了3这个位置
            //把最后一个数跟前面的数进行比较,一直到i的位置停止
    
                for(int  j = arrays.length-1;j>i;j--){
                //对相邻的两个数进行比较并交换位置
                    if (arrays[j - 1] > arrays[j]) {
                        temp = arrays[j - 1];
                        arrays[j - 1] = arrays[j];
                        arrays[j] = temp;
                    }
    
                }
            }
    
            return arrays;
    
        }
    用下面语句跟踪上述算法:
    
    double[] myList = {5.0, 4.4, 1.9, 2.9, 3.4, 2.9, 3.5};
    double []list = bubbleSort(myList);
    System.out.println("My list after sort is: " + Arrays.toString(list));
    

    输出结果:

    My list after sort is: [1.9, 2.9, 2.9, 3.4, 3.5, 4.4, 5.0]

    相关文章

      网友评论

          本文标题:数组 选择排序 冒泡

          本文链接:https://www.haomeiwen.com/subject/fhhsyftx.html