算法--数组冒泡排序和选择排序原理分析

悠悠 2022-06-14 19:58 169阅读 0赞

# **1.冒泡排序原理分析** #

## **1.1冒泡排序** ##

> 从前往后后依次比较相邻两个元素大小，大的元素往后挪，比较完第一遍后，最大的元素排到了数组的最后一位（假设是从小到大排序）

--------------------

## **1.2原理分析：** ##

> **冒泡排序逻辑：若为从小到大排序**
> 
>  *  第一个数与第二个数比较 - - 若第二个数大，则不交换位置，反之，交换位置
>  *  根据上一步的结果：进行第二个数与第三个数比较 - - 若第三个数大，则不交换位置，反之，交换位置
>  *  依次类推，完成与最后一个数的比较后，最大的数就被排到了末位。
>  *  接着再排依照同样的方法，将第二大的数排在倒数第二位（注意：排好了的数，就不需要再与他们比较大小了）

--------------------

#### **图解原理** ####

![这里写图片描述][SouthEast]

--------------------

## **1.3代码实现** ##

package 数组两种排序;
    
    import java.util.Arrays;
    
    //冒泡排序
    public class Test1 {
        public static void main(String[] args) {
            int[] arr={
       2,5,1,9,12,6,7};
            bubbleSort(arr);
            System.out.println("从小到大排序"+Arrays.toString(arr));
    
            bubbleSort2(arr);
            System.out.println("从大到小排序"+Arrays.toString(arr));
        }
    
        //1.冒泡排序--从小到大排序
        public static int[] bubbleSort(int[] arr){
            for (int i = 0; i < arr.length-1; i++) {
                //对于已经排好的元素就不用再做比较了，所以第二个for循环，值遍历到arr.length-i-1
                for (int j = 0; j < arr.length-i-1; j++) {
                    //相邻两数比较，前面的数大，则交换，否则不交换，这样循环完后，最大值被排到了最后一位
                    if(arr[j]>arr[j+1]){
                        int temp=arr[j+1];
                        arr[j+1]=arr[j];
                        arr[j]=temp;
                    }
                }
            }
            return arr;
        }
    
        //2.冒泡排序--从大到小排序    只是将if判断中大于号>，改为了小于号<
        public static int[] bubbleSort2(int[] arr){
            for (int i = 0; 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+1];
                        arr[j+1]=arr[j];
                        arr[j]=temp;
                    }
                }
            }
            return arr;
        }
    
    
    }

--------------------

# **2.选择排序原理分析** #

## **2.1选择排序：** ##

> 在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止(假设为从小到大排序)

--------------------

## **2.2原理分析** ##

> **选择排序逻辑：若为从小到大排序**
> 
>  *  第一次：对数组中所有数值进行比较，获得最小值下标，然后将最小值与第一个数交换
>  *  第二次：对数组中剩余（除第一个数）数值进行比较，获得最小值下标，然后将最小值与第二个数交换
>  *  依次类推，直至确定倒数第二个位置的数值

--------------------

#### **图解原理** ####

![这里写图片描述][SouthEast 1]

--------------------

## **2.3代码实现** ##

package 数组两种排序;
    
    import java.util.Arrays;
    
    public class Test2 {
        
        public static void main(String[] args) {
            int[] arr = { 2, 5, 1, 9, 12, 6, 7 };
            chooseSort(arr);
            System.out.println("从小到大排序" + Arrays.toString(arr));
    
            chooseSort2(arr);
            System.out.println("从大到小排序" + Arrays.toString(arr));
        }
    
        // 1.选择排序--从小到大排序
        public static int[] chooseSort(int[] arr) {
            //遍历数组，获取指定的arr[i]去与
            for (int i = 0; i < arr.length - 1; i++) {
                int index = i;//存储最小值的下标
                for (int j = i + 1; j < arr.length; j++) {
                    //若arr[index]大，则改变索引，使arr[index]变为那个小的值，最后可以得到最小值的索引
                    if (arr[index] > arr[j]) {
                        index = j;
                    }
                }
    
                //若index和初始值i相同就没必要交换了
                if(index!=i){
                    //将最小值与arr[i]交换
                    int temp2 = arr[i];
                    arr[i] = arr[index];
                    arr[index] = temp2;
                }
    
            }
            return arr;
        }
    
        // 2.选择排序--从大到小排序   只是将if判断中大于号>，改为了小于号<
        public static int[] chooseSort2(int[] arr) {
            for (int i = 0; i < arr.length - 1; i++) {
                int index = i;
                for (int j = i + 1; j < arr.length; j++) {
                    if (arr[index] < arr[j]) {
                        index = j;
                    }
                }
    
                if(index!=i){
                    //将最小值与arr[i]交换
                    int temp2 = arr[i];
                    arr[i] = arr[index];
                    arr[index] = temp2;
                }
            }
            return arr;
        }
    }

--------------------

# **3.两种排序方式的比较** #

## **3.1冒泡排序** ##

交换次数多，耗时耗资源

## **3.2选择排序** ##

交换次数少，节省时间和资源

[SouthEast]: /images/20220615/43268d1a461c43d490c024f45ef1f7c3.png
[SouthEast 1]: /images/20220615/61bbf87f17e54c0d94e0ce3aa49a9098.png