手把手教你搞懂冒泡排序和選擇排序

更新時(shí)間：2021年07月15日 16:24:31 作者：小胖java攻城獅

這篇文章主要介紹了java數(shù)組算法例題代碼詳解(冒泡排序,選擇排序),本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下

冒泡排序

原理：

從頭（左邊）開始比較每一對(duì)相鄰的元素，如果第1個(gè)比第2個(gè)大，就交換它們的位置，執(zhí)行完一輪后，最末尾（最右邊）就是最大的元素。

舉例：

假設(shè)存在數(shù)組nums={6，8，2，9，4}，對(duì)nums數(shù)組進(jìn)行排序

在這里插入圖片描述

從左往右開始，拿出兩個(gè)元素進(jìn)行對(duì)比，出現(xiàn)兩種情況：

1.左邊元素 <= 右邊元素，不變

2.左邊元素 > 右邊元素，交換他們的位置（這里可以寫成>=嗎？不行，因?yàn)闀?huì)造成排序不穩(wěn)定）

在這里插入圖片描述

接下來就是新的一輪排序，邏輯跟上圖的流程是一樣的，不同的是會(huì)將最大的元素排除在外，不用進(jìn)行比較。

手撕代碼：

/*
沒有使用過優(yōu)化策略的冒泡排序
 */
public class BubbleSort1 {
    //測(cè)試數(shù)據(jù)
    public static int[] nums = {4,1,7,11,9,55};
    //main方法
    public static void main(String[] args){
        //這個(gè)for循環(huán)每循環(huán)完一次，end--，說明就把最大的元素給選出來了
        for (int end = nums.length - 1; end > 0; end--){
            for (int begin = 1; begin <= end; begin++){
                if(nums[begin] < nums[begin - 1]){    //每當(dāng)發(fā)現(xiàn)左邊的元素大于右邊的元素
                    //交換元素
                    int temp = nums[begin];
                    nums[begin] = nums[begin - 1];
                    nums[begin - 1] = temp;
                }
            }
        }
        //打印驗(yàn)證結(jié)果
        for(int num : nums){
            System.out.print(num+"_");
        }
    }
}

時(shí)間復(fù)雜度為O（n^2），也就是n的平方，不過這是平均時(shí)間復(fù)雜度

存在最好時(shí)間復(fù)雜度O（n），那就是數(shù)組本來就有序，也就是說只掃描一遍就行了。

優(yōu)化策略：

由于存在部分有序的情況，例如nums數(shù)組為{8，5，2，10，11，12}，也就是說10，11，12都沒有比較的必要了

優(yōu)化代碼：

/*
使用過優(yōu)化策略的冒泡排序
 */
public class BubbleSort1 {
    public static int[] nums = {4,1,7,11,9,55};
    public static void main(String[] args){
        for (int end = nums.length - 1; end > 0; end--){
            int sortIndex = 1;  //記錄最后一次交換位置
            for (int begin = 1; begin <= end; begin++){
                if(nums[begin] < nums[begin - 1]){
                    int temp = nums[begin - 1];
                    nums[begin - 1] = nums[begin];
                    nums[begin] = temp;
                    sortIndex = begin;
                }
                end = sortIndex;
            }
        }
        for(int num : nums){
            System.out.print(num+"_");
        }
    }
}

選擇排序

原理：

從數(shù)組中找到最大的元素，然后與末尾（最右邊）的元素交換位置，執(zhí)行完一輪后，末尾（最右邊）的那個(gè)元素就是最大的元素。

舉例：

假設(shè)存在數(shù)組nums={5，8，1，9，3}，對(duì)nums數(shù)組進(jìn)行排序，準(zhǔn)備一個(gè)maxIdex代表當(dāng)前最大元素的下標(biāo)

在這里插入圖片描述

接下來就是新的一輪排序，邏輯跟上圖的流程是一樣的，不同的是會(huì)將最大的元素排除在外，不用進(jìn)行比較。

手撕代碼：

/**
 * 選擇排序
 */
public class SelectionSort {
    //測(cè)試數(shù)據(jù)
    private static int[] nums = {6,3,2,8,9};
    //main方法
    public static void main(String[] args){
        //這個(gè)for循環(huán)每循環(huán)完一次，end--，說明就把最大的元素給選出來了
        for(int end = nums.length - 1; end > 0; end--){
            int maxIndex = 0;   //假設(shè)下標(biāo)0是數(shù)組中最大元素
            for(int begin = 1; begin <= end; begin++){  //從左往右開始比較
                if(nums[maxIndex] < nums[begin]){   //發(fā)現(xiàn)存在一個(gè)元素大于假設(shè)最大元素
                    maxIndex = begin;   //更改最大元素索引
                }
            }
            //最右邊一個(gè)元素和最大值元素交換位置
            int temp = nums[maxIndex];
            nums[maxIndex] = nums[end];
            nums[end] = temp;
        }
        //打印結(jié)果
        for(int num : nums){
            System.out.print(num+"_");
        }
    }
}