冒泡排序和选择排序

排序总结

冒泡排序
- 原理
- 代码
选择排序
- 原理
- 代码
插入排序
- 原理
- 代码
希尔排序
- 原理
- 代码

冒泡排序

原理

冒泡排序的原理非常简单，对相邻的元素进行两两比较,顺序相反则交换,这样,每趟会将最小(或最大)的元素浮到数组最后面,最终达到整体有序。

代码

public static void main(String[] args) {
    int[] arr = {1,4,2,7,4};
    bubboSort(arr);
    //Stream.of(arr).forEach(System.out::println); //[I@682a0b20 || 求高人指定迷津，Stream如何打印数组对象
    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + "\t");
    }
}

//冒泡排序算法实现
public static void bubboSort(int[] arr){
    if(arr == null || arr.length == 0) return;
   for(int i =0 ; i<arr.length-1 ; i++){
            for(int j=0 ; j<arr.length-1-i ; j++) {  
                if(arr[j]>arr[j+1]) {
                    swap(arr,j,j+1);
            }   
        }
}

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

选择排序

原理

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

代码

public static void main(String[] args) {
       int[] arr = {1,4,2,7,4};
       chooseSort(arr);
       System.out.println(Arrays.toString(arr));
   }

public static void chooseSort(int[] arr){
   if(arr == null || arr.length == 1) return;
   for (int i = 0; i < arr.length - 1; i++) {
       //初始化index大小为i,如果i就是最小值，则可以自己安排体会
       int index = i;
       for (int j = i + 1;j < arr.length; j++){
           //找到最小值的索引
           if(arr[j] < arr[index]){
               index = j;
           }
       }
       swap(arr,i,index);
   }
}

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

插入排序

原理

插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序 。

代码

public static void main(String[] args) {
    int[] arr = {1,4,2,7,4};
    insertSort(arr);
    for(int i : arr){
        System.out.print(i+"\t");
    }
}

public static void insertSort(int[] arr){
    if(arr == null || arr.length == 0) return;
    for (int i = 0;i < arr.length ; i++){
        //每一步都从i向前走，走到起始的位置
        for (int j = i;j > 0 && arr[j] < arr[j-1];j--){
            swap(arr,j,j-1);
        }
    }
}

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

希尔排序

原理

1. 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
2. 希尔排序可以看成是至尊版的插入排序，把整个数组按步长进行一层一层的分组，每一层的分组用插入排序进行排序，当分组步长为1时，整个数组完成排序
3. 希尔排序和插入排序相比在数据量大的时候速度更快

代码

//希尔排序
public class HereSort {

    public static void main(String[] args) {
        int[] arr = {5, 1, 7, 3, 1, 6, 9, 4};
        rightShellSort(arr,4);
        for (int i : arr) {
            System.out.print(i + "\t");
        }
    }
    
    public static void rightShellSort(int[] arr,int n) {
        if (arr == null || arr.length == 0) return;
        //步长逐渐变化
        do {
            n = n >> 1;
            for (int i = n; i < arr.length; i+=n) {
                //每一步都从i向前走，走到起始的位置
                for (int j = i; j > 0 && arr[j] < arr[j - n]; j-=n) {
                    swap(arr, j, j - n);
                }
            }
        } while (n != 1);
    }

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