选择排序、插入排序、冒泡排序

选择排序

遍历查找数组中最小数
将它与原本处于最小值位置的数字交换

实现

//选择排序

public class SelectionSort {

    private SelectionSort(){

    }

    public static void sort(int[] arr ){

        int n =  arr.length;//数组长度

        for (int i = 0;i<n;i++){
            int min = i;//存储每次比较那个最小的数下标（一开始只有一个数默认它为最小）

            //往后循环 拿到它所得到最小的那个数的下标
            for (int j = i+1;j<n;j++){
                if (arr[min] > arr[j]){
                    min = j;//储存最小的那个数的下标
                }
            }
            swap(arr, min, i);//然后与它从小到大排序的那位数交换

        }
    }

    private static void swap(int arr[],int i,int j){
        int temp = arr[i];//每次遍历最小的那个数
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {10,9,8,7,6,5,4,3,2,1};
        SelectionSort.sort(arr);
        for( int i = 0 ; i < arr.length ; i ++ ){
            System.out.print(arr[i]);
            System.out.print(" ");
        }
        System.out.println();
    }
}

效果:

插入排序

分为左右两个排序数组
左边默认为排好序
右边第一个元素与左边数组最后一位比较
若小于则交换 继续与最后一位的前一位进行对比 以此类推

实现:

//插入排序实现
public class InsertSort {

    private InsertSort(){

    }

    public static void insert(int[] arr){
        int n = arr.length;

        //这里i=1因为不用考虑第一个元素
        // 默认就是有序的
        //分为左右有序列和无序列，一开始存储的元素
        // 与有序列进行比较
        for (int i = 1;i<n;i++){
            for (int j = i;j>0;j--){
                //如果j比它前一个元素还小
                if(arr[j] < arr[j-1]){
                    //则互换位置
                    swap(arr, j, j-1);
                }
            }
        }
    }


    private static void swap(int arr[],int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {10,9,8,5,6,7,4,3,2,1};
        InsertSort.insert(arr);
        for( int i = 0 ; i < arr.length ; i ++ ){
            System.out.print(arr[i]);
            System.out.print(" ");
        }
        System.out.println();
    }
}

选择排序与插入排序之间的区别:
选择排序是选取一个最小数，然后不断与后面的元素进行比较，存储最后比较到的最小的数并插入（temp值一直在变化）
插入排序是分成有序列与无序列，新加入有序列的元素与已在有序列中的元素互相比较（相当与往前一个个地比较）

冒泡排序

冒泡排序就是不断地进行两两互换

public class BubbleSort {

    private BubbleSort(){

    }

    public static void bubble(int arr[]){
        int n = arr.length;
        boolean swapped = false;//判断它是否互换过

        do {
            swapped = false;
            for (int i = 1;i<n;i++){
                if(arr[i] < arr[i-1]){
                    swap(arr, i-1, i);
                    swapped = true;
                }
            }

            // 优化, 每一趟Bubble Sort都将最大的元素放在了最后的位置
            // 所以下一次排序, 最后的元素可以不再考虑
            n --;
        }while (swapped);
    }

    private static void swap(int arr[],int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {10,9,8,7,6,5,4,3,2,1};
        BubbleSort.bubble(arr);
        for( int i = 0 ; i < arr.length ; i ++ ){
            System.out.print(arr[i]);
            System.out.print(" ");
        }
        System.out.println();
    }
}