欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java常用的经典排序算法:冒泡排序与选择排序

程序员文章站 2022-08-31 17:09:35
一、冒泡排序 冒泡排序(Bubble Sort)是一种交换排序,它的基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。 进一步理解为(假设由小到大排序):对于给定的n个记录,从第一个记录开始依次对相邻的两个记录进行比较,当前面的记录大于后面的记录时,交换位置,进行一轮比较 ......

 一、冒泡排序                            

冒泡排序(bubble sort)是一种交换排序,它的基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。

  进一步理解为(假设由小到大排序):对于给定的n个记录,从第一个记录开始依次对相邻的两个记录进行比较,当前面的记录大于后面的记录时,交换位置,进行一轮比较和换位后,n个记录的最大记录将位于第n位;然后对(n-1)个记录进行第二轮比较;重复该过程直到进行比较的记录只剩下一个为止。

以数组int[] arr = {3,9,5,7,1}为例,冒泡排序的具体步骤如下:

初始状态:[3,9,5,7,1]

第一趟排序过程如下:

第一次arr[0]=3与arr[1]=9比较交换后: [3,9,5,7,1]

第二次arr[1]=9与arr[2]=5比较交换后: [3,5,9,7,1]

第三次arr[2]=9与arr[3]=7比较交换后: [3,5,7,9,1]

第四次arr[3]=9与arr[4]=1比较交换后:[3,5,7,1,9]

第一趟排序最值9出现在最后一位

第一趟排序后9出现在第n位:[3,5,7,1,9]

第二趟排序后7出现在n-1位:[3,5,1,7,9]

第三趟排序后5出现在n-2位:[3,1,5,7,9]

第四趟排序后3出现在n-3位,完成排序:[1,3,5,7,9]

程序示例如下(假设由小到大排序):

package com.bhyj;

public class arraysort {

    /**
     * 冒泡排序
     */
    public static void bubblesort(int[] arr) {
        /**
         * 外循环控制排序趟数 
         * 总共需要arr.length-1趟
         */
        for (int i = 0; i < arr.length - 1; i++) {
            /**
             * 内循环控制每一趟的比较次数 
             * 第1趟比较次数为arr.length-1 
             * 第2趟比较次数为arr.length-1-1
             * 第3趟比较次数为arr.length-1-2 
             * 第i趟比较次数为arr.length-1-(i-1)
             * 由于i从0开始,所以第i趟比较次数为arr.length-1-i
             * 
             */
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(string[] args) {
        int[] arr = { 3, 9, 5, 7, 1 };
        // 排序前
        system.out.print("排序前:");
        printarray(arr);
        // 排序
        arraysort.bubblesort(arr);
        system.out.println("");
        // 排序后
        system.out.print("排序后:");
        printarray(arr);

    }

    /**
     * 打印数组
     */
    public static void printarray(int[] arr) {
        system.out.print("[");
        for (int i = 0; i < arr.length; i++) {
            system.out.print(arr[i]);
            if(i < arr.length-1){
                system.out.print(",");
            }
        }
        system.out.print("]");
    }

}

输出结果为:

排序前:[3,9,5,7,1]
排序后:[1,3,5,7,9]

冒泡排序时间复杂度:o(n2)

 二、选择排序   

  选择排序(selection sort)的基本思想为(假设由小到大排序):对于给定的一组记录,经过第一轮比较后得到最小的记录,然后将该记录与第一个记录的位置进行交换;接着对不包括第一个记录以外的其他记录进行第二轮比较,得到的最小的记录与第二个记录进行位置交换;重复该过程,直到进行比较的记录只有一个为止。

以数组int[] arr = {3,9,5,7,1}为例,选择排序的具体步骤如下:

初始状态:[3,9,5,7,1]

第一趟排序过程如下:

第一次arr[0]=3与arr[1]=9比较交换后: [3,9,5,7,1]

第二次arr[0]=3与arr[2]=5比较交换后: [3,9,5,7,1]

第三次arr[0]=3与arr[3]=7比较交换后: [3,9,5,7,1]

第四次arr[0]=3与arr[4]=1比较交换后: [1,9,5,7,3]

第一趟排序最值1出现在第一位

第一趟排序后1出现在第1位:[1,9,5,7,3]

第二趟排序后3出现在第2位:[1,3,9,7,5]

第三趟排序后5出现在第3位:[1,3,5,9,7]

第四趟排序后7出现在第4位,9排在最后一位,完成排序:[1,3,5,7,9]

程序示例如下(假设由小到大排序):

package com.bhyj;

public class arraysort {

    /**
     * 选择排序
     */
    public static void selectsort(int[] arr) {
        /**
         * 外循环控制排序趟数 
         * 总共需要arr.length-1趟
         */
        for (int i = 0; i < arr.length - 1; i++) {
            /**
             * 内循环控制每一趟的比较次数 
             */
            for (int j = i+1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }

    public static void main(string[] args) {
        int[] arr = { 3, 9, 5, 7, 1 };
        // 排序前
        system.out.print("排序前:");
        printarray(arr);
        // 排序
        arraysort.selectsort(arr);
        system.out.println("");
        // 排序后
        system.out.print("排序后:");
        printarray(arr);

    }

    /**
     * 打印数组
     */
    public static void printarray(int[] arr) {
        system.out.print("[");
        for (int i = 0; i < arr.length; i++) {
            system.out.print(arr[i]);
            if(i < arr.length-1){
                system.out.print(",");
            }
        }
        system.out.print("]");
    }
}

输出结果为:

排序前:[3,9,5,7,1]
排序后:[1,3,5,7,9]

选择排序时间复杂度:o(n2)

                                                                                                                                                                                                                                                                 

关注微信公众号【java典籍】,收看更多java技术干货

 ▼微信扫一扫下图↓↓↓二维码关注

 Java常用的经典排序算法:冒泡排序与选择排序