冒泡排序和选择排序的简单使用

Myth丶恋晨 2022-05-25 09:54 151阅读 0赞

这里主要介绍一下冒泡排序和选择排序的简单使用，给初学者一些参考，可能和别人的有点不一样，这主要是我自己的一些思路，和别人是有一些出入的。

直接上代码，注释在代码中：

package com.Jevin.chapter01;
    
    /**
     * 这里介绍一下冒泡和选择排序：
     */
    public class Sort {
        public static void main(String[] args) {
            int[] arr={12,1,23,6,78,36,17,12};
            //int[] array=test01(arr);
            int[] array=test02(arr);
            for(int i=0;i<array.length;i++){
                System.out.print(array[i]+"\t");
            }
        }
    
        //冒泡排序：从小到大
        public static int[] test01(int[] arr){
            /**
             * 外层循环表示要排序的轮数，每一轮选出一个最大数，最后只剩一个数不许比较，所以是i<=arr.length-1
             * 那么这里为什么不写成i<arr.length呢，写成i<=arr.length-1更能体现它的数学思想，便于思考；
             */
            for(int i=1;i<=arr.length-1;i++){
                /**
                 * 内层循环表示每一轮要比较的次数,j这里承担了两个角色，第一，作为数的索引；第二，每一轮要比较的次数；
                 * 每一轮比较的次数应该是arr.length-i(即为，每一轮循环选出了一个最大数，下一轮这个最大数不需要再参与比较，
                 * 所以要减i);但是下面if(){}语句arr[j+1],j多取到了索引后一位，所以需要再减去1；
                 */
                for(int j=0;j<=arr.length-i-1;j++){
                    if(arr[j]>arr[j+1]){
                        int temp=arr[j];
                        arr[j]=arr[j+1];
                        arr[j+1]=temp;
                    }
                }
            }
            return arr;
        }
    
    
    
        //选择排序：从小到大
        public static int[] test02(int[] arr){
            /**
             * 外层循环表示要比较的轮数，同冒泡排序；
             */
            for(int i=1;i<=arr.length-1;i++){
                /**
                 * 这里设置了一个索引index,它表示一个指针，存储在此索引中的数默认是从小到大的；
                 */
                int index=i-1;
                /**
                 * 内层循环表示每一轮要比较的次数，假设index中存储的是最小数，那么将index后的每一个数
                 * 与之比较，如若小于它，则交换索引，这样保证index中始终存储的是相对最小数；
                 */
                for(int j=i;j<=arr.length-1;j++){
                    if(arr[index]>arr[j]){
                        index=j;
                    }
                }
                //将存储在index索引中的最小数重新放到它原来的位置上；
                int temp=arr[i-1];
                arr[i-1]=arr[index];
                arr[index]=temp;
            }
            return arr;
        }
    }

然后，是这两种排序的简单应用：

package com.Jevin.chapter01;
    
    import java.util.Arrays;
    
    /**
     * 这里要解决的问题是：
     *                     假设一组N个数，要确定其中的第k个最大数：
     */
    public class Cite {
        public static void main(String[] args){
    
            int[] arr=new int[]{9,4,14,25,98,47};
    
            //test01()使用冒泡排序法求出第三个最大数：
            /*int value01=test01(arr,3);
            System.out.println(value01);*/ //k=3，即第三个最大数，为25
    
            //test02()使用选择排序法求出第三个最大数：
            /*int value02=test02(arr,3);
            System.out.println(value02);*/
    
            //test03()思路二：
            int value03=test03(arr,3);
            System.out.println(value03);
    
            /**
             * 可以看到思路二的循环次数明显少于思路一的冒泡和选择排序，因此思路二在处理大量数据的效率上要优于思路一；
             */
        }
    
        /**
         * 思路一：将这N个数按照冒泡或者选择排序法从大到小排列，找到第k个数，即为所得；
         */
        //方法一：这里使用冒泡排序法：
        public static int test01(int[] arr,int k){
            for(int i=1;i<=arr.length-1;i++){
                for(int j=0;j<=arr.length-i-1;j++){
                    if(arr[j]<arr[j+1]){
                        int temp=arr[j];
                        arr[j]=arr[j+1];
                        arr[j+1]=temp;
                    }
                }
            }
            return arr[k-1];
        }
    
        //方法二：这里使用选择排序法：
        public static int test02(int[] arr,int k){
            for(int i=1;i<=arr.length-1;i++){
                int index=i-1;
                for(int j=i;j<=arr.length-1;j++){
                    if(arr[index]<arr[j]){
                        index=j;
                    }
                }
                int temp=arr[i-1];
                arr[i-1]=arr[index];
                arr[index]=temp;
            }
            return arr[k-1];
        }
    
    
        /**
         *思路二：1.将此数组arr中的前k个元素取出来组成一个新的数组brr，并从大到小排序;
         *        2.剩下的元素逐个录入，如果小于第k个元素，则忽略；如果大于，则将其放入到数组brr中的相应的位置，
         *        此时数组brr会多出一个元素k+1，舍掉，以此循环往复到最后一个元素即可得到最后的brr，且brr第k个元素即为arr的第k个最大者；
         */
    
        public static int test03(int[] arr,int k){
            int[] brr=Arrays.copyOfRange(arr,0,k);
            brr=arraySort(brr);
            //for(){}循环表示数组arr被截取后的元素逐个录入：
            for(int i=brr.length;i<arr.length;i++){
                if(brr[brr.length-1]>arr[i]){
                    //如果arr剩下的元素都小于crr的第k个元素，则crr中的最后一个元素即为arr中的第k个最大者：
                    continue;   //结束当前循环，进行下一次循环；注意这里千万不要用break或者是return,要不然结束直接跳出循环体了；
                }else{
                    //只要arr剩下的元素出现一个比crr中的元素中的大者，则crr加上这个元素重新排序，并踢出最小的那个：
                    brr=Arrays.copyOf(brr,brr.length+1);
                    brr[brr.length-1]=arr[i];
                    brr=arraySort(brr);
                    brr=Arrays.copyOfRange(brr,0,brr.length-1);
                    continue;
                }
            }
            return brr[brr.length-1];
        }
    
        //这里进行数组排序，方便其他方法的调用：
        public static int[] arraySort(int[] arr){
            for(int i=1;i<=arr.length-1;i++){
                for(int j=0;j<=arr.length-i-1;j++){
                    if(arr[j]<arr[j+1]){
                        int temp=arr[j];
                        arr[j]=arr[j+1];
                        arr[j+1]=temp;
                    }
                }
            }
            return arr;
        }
    }

好了，就这些了！