八大排序算法---冒泡排序、选择排序

冒泡排序

基本思想：从前往后依次比较相邻元素的值，值大的往后交换，最后排序的数组从小到大排列

时间复杂度O(n^2)

package buttlepaixu;
import java.util.Arrays;
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = new int[]{3,9,-1,10,20};
        //一共进行 arr.length-1次大的循环
        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];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}
           

优化：

在进行排序的过程中可能会出现一趟下来没有进行交换的情况，说明数组有序；因此，可以设置一个flag标志位来表明元素是否发生交换，从而减少不必要的比较

优化后的代码：

package buttlepaixu;
import java.util.Arrays;
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = new int[]{3,9,-1,10,20};
        int temp = 0;
        boolean flag = false;//记录是否发生过交换
        //一共进行 arr.length-1次大的循环,迭代多少轮
        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]){
                	flag = ture;
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
            if(!flag){//flag = false;表示一次交换都没有发生
            	break;
            }else{
				flag = fasle;//重置flag
			}
        }
        
        System.out.println(Arrays.toString(arr));
    }
}
           

选择排序

时间复杂度O(n^2)

基本思想：第一步：先从arr[0]~arr[n-1]中选出最小的数，然后与arr[0]进行交换。第二步：从arr[1]到arr[n-1]中找出最小的数和arr[1]进行交换。第三步：从arr[2]到arr[n-1]中找出最小的数与arr[2]进行交换。。。以此类推，经过arr.length-1躺排序结束。

原始数组：101，34，119，1，2

第一轮：1，34，119，101，2//｛101，34，119，1，2｝

第二轮：1，2，119，101，34//{34，119，101，2}

第三轮：1，2，34，101，119//｛119，101，34｝

第四轮：1，2，34，101，119//｛101，119｝

import java.util.Arrays;
public class SelectSort {
    public static void main(String[] args) {
        int[] arr = new int[]{101,34,119,1,-1,90,123};
        int temp = 0;
        for(int i = 0;i<arr.length-1;i++){
            int minIndex = i;
            int min = arr[i];
            for(int j = i+1;j<arr.length;j++){
                if(min>arr[j]){
                    min = arr[j];
                    minIndex = j;
                }
            }
            if(minIndex != i){
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
            System.out.println(Arrays.toString(arr));
        }

    }
}