几种简单排序算法

几种简单排序算法 一、介绍 1.1 选择排序分析

选择排序：每次循环找出最小值的索引，直接进行交换。

n表示数组长度 ， end 表示最后一次循环。
第1次循环： 在 0 ~ n-1 中找出最小值 ，放在索引为0的位置。
第2次循环： 在 1 ~ n-1 中找出最小值 ，放在索引为1的位置。
第3次循环： 在 2 ~ n-1 中找出最小值 ，放在索引为2的位置。
第4次循环： 在 3 ~ n-1 中找出最小值 ，放在索引为3的位置。
 ....
第n-1次循环： 在 n-2 ~ n-1 中找出最小值 ，放在索引为n-1的位置。

即 每次循环找出最小值直接交换两个元素的位置。

1.2 冒泡排序分析

冒泡排序：每次循环，两两比较，找出最大值，放在最后。

第1次循环：从 0 ~ n-1 范围中 找到最大值，放在n-1位置。
第2次循环：从 0 ~ n-2 范围中 找到最大值，放在n-2位置。
第3次循环：从 0 ~ n-3 范围中 找到最大值，放在n-3位置。
......
第n-1次循环：从 0 ~ 1 范围中 找到最大值，放在1位置。

即：两两比较，每次循环找出最大值，放在最后。

1.3 插入排序分析

第1次循环：从 0 ~ 1 范围中排序
第2次循环：从 0 ~ 2 范围中排序
第3次循环：从 0 ~ 3 范围中排序
......
第n-1次循环：从 0 ~ n-1 范围中排序

即：每次循环，将待排序的值和之前有序的元素进行比较，放在合适的位置。

二、代码实现

public class SortCode {

    public static void main(String[] args) {
        int[] arr = {9, 4, 1, 6, 2, 5, 4,1};
        pringArray(arr);
//        selectSort(arr);
//        bubbleSort1(arr);
//        bubbleSort2(arr);
//        insertionSort1(arr);
        insertionSort2(arr);
        pringArray(arr);

    }

    
    public static void pringArray(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println();

    }

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

    
    public static void selectSort(int[] arr){
        if (arr == null || arr.length < 2  ){
            return;
        }
        int num = 0 ;
        int N = arr.length;
        for (int i = 0; i < N; i++) {
            int minValueIndex = i;
            //注意：内层循环的初始值是当前值的下一位，即i+1，因为内层循环为当前值和后面的值比较，并记录最小值的位置
            for (int j = i+1; j < N; j++) {
                // 2,1,6,8,1,5
                // 0 1 2 3 4 5
                minValueIndex = arr[minValueIndex] > arr[j] ? j:minValueIndex;
                num ++;
            }
            swap(arr,minValueIndex,i);

        }
        System.out.println(num);

    }

    
    public static void  bubbleSort1(int[] arr){
        if (arr == null || arr.length < 2){
            return;
        }
        int num = 0 ;
        int N = arr.length;
        // 0 ~ n-1
        // 0 ~ n-2
        // 0 ~ n-3
        //外层循环控制次数
        for (int i = 0; i < N; i++) {
            //内层循环进行两两比较，从索引0位置开始两两比较  即：j和j+1进行比较，j++，此处 限制条件：j < N-1 和j < N-1-i 效果是一样的。
            for (int j = 0; j < N-1; j++) {
                if (arr[j] > arr[j+1]){
                    swap(arr,j+1,j);
                    num ++;
                }
            }
        }
        System.out.println(num);
    }

    
    public static void bubbleSort2(int[] arr){
        if (arr == null || arr.length < 2){
            return;
        }
        int num = 0 ;
        int N = arr.length;
        for (int end = N-1; end >= 0; end--) {
            for (int second = 1; second <= end ; second++) {
                if (arr[second-1] > arr[second]){
                    swap(arr,second-1,second);
                    num ++;
                }
            }
        }
        System.out.println(num);
    }

    
    public static void insertionSort1(int[] arr){
        if (arr == null || arr.length < 2){
            return;
        }
        int N = arr.length;
        int num = 0;
        for (int i = 0; i < N; i++) {
            int nextValueIndex = i ;
            while ((nextValueIndex -1)>=0 && (arr[nextValueIndex] < arr[nextValueIndex-1])){
                swap(arr,nextValueIndex,nextValueIndex-1);
                nextValueIndex--;
                num ++;
            }
        }
        System.out.println(num);

    }

    
    public static void insertionSort2(int[] arr){
        if (arr == null || arr.length < 2){
            return;
        }
        int N = arr.length;
        int num = 0 ;
        for (int end = 1; end < N; end++) {
            for (int pre = end -1 ; pre >= 0 &&(arr[pre] > arr[pre+1]); pre--) {
                swap(arr,pre,pre+1);
                num++;
            }
        }
        System.out.println(num);
    }
}