排序是一个非常经典的问题，它以一定的顺序对一个数组（或一个列表）中的项进行重新排序（可以进行比较，例如整数，浮点数，字符串等）（增加，非递减，递减， 增加，词典等）。
有许多不同的排序算法，每个都有其自身的优点和局限性

引用于 https://visualgo.net/zh

1 冒泡排序

这是来自于网上搜索的一张动态图：

所谓冒泡排序，一句话描述就是最大的数向上冒泡

import java.util.Arrays;
  //java 冒泡排序
  public void bubbleSortFunction1(){
    //待排序数组
    int arr[]={3,44,38,5,50,48};
    //记录比较次数
    int count=0;
    //外层循环 取出每个数据
    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]) {
          //将最大的数据放到右侧
          //临时变量记录左侧大的数据
          int temp=arr[j];
          //将右侧小的数据赋值到左侧
          arr[j]=arr[j+1];
          //将临时变量保存的大的数据赋值到右侧
          arr[j+1]=temp;
        }
        count++;
      }
    }
    System.out.println(Arrays.toString(arr));//[3, 5, 38, 44, 48, 50]
    System.out.println("一共比较了："+count+"次");//一共比较了：15次
  }

2 选择排序

所谓选择排序，一句话描述就是找出最小的，放到最左侧

  public void selectSortFunction(){
    //待排序数组
    int arr[]={3,44,38,5,50,48};
    //记录比较次数
    int count=0;
    for (int i = 0; i < arr.length-1; i++) {
      int index=i;//标记第一个为待比较的数
      for (int j = i+1; j < arr.length; j++) { //然后从后面遍历与第一个数比较
        if (arr[j]<arr[index]) {  //如果小,就交换最小值
          index=j;//保存最小元素的下标
        }
        count++;
      }
      //找到最小值后，将最小的值放到第一的位置，进行下一遍循环
      int temp=arr[index];
      arr[index]=arr[i];
      arr[i]=temp;
    }
    System.out.println(Arrays.toString(arr));//[3, 5, 38, 44, 48, 50]
    System.out.println("一共比较了："+count+"次");//一共比较了：15次
  }

3、插入排序

  public void insertSortFunction(){
    //待排序数组
    int arr[]={3,44,38,5,50,48};
    //长度不减1，是因为要留多一个位置方便插入数
    for (int i = 0; i < arr.length; i++) {
      //记录待插入的数
      int insertValue=arr[i];
      //找到待插入数的前一个数的下标
      int preInsertIndex=i-1;


      //因为是向前插入 所以 preInsertIndex 必须大于等于0
      //只有待插入数据 比 前一个数据小时 才进行位置递减
      while (preInsertIndex>=0 && insertValue <arr[preInsertIndex]) {
        //将前一个数据向后移
        arr[preInsertIndex+1]=arr[preInsertIndex];
        //位置递减
        preInsertIndex--;
      }
      //赋值插入的位置
      arr[preInsertIndex+1]=insertValue;


    }
    System.out.println(Arrays.toString(arr));//[3, 5, 38, 44, 48, 50]
  
  }

4、希尔排序

希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序

希尔排序的基本步骤，在此选择增量gap=length/2，缩小增量继续以gap = gap/2的方式。

  public void shellSortFunction(){
    //待排序数组
    int arr[]={3,44,38,5,50,48};
    //记录比较次数
    int count=0;
    for (int gap=arr.length / 2; gap > 0; gap = gap / 2) {
      //将整个数组分为若干个子数组
      for (int i = gap; i < arr.length; i++) {
        //遍历各组的元素
        for (int j = i - gap; j>=0; j=j-gap) {
          //交换元素
          if (arr[j]>arr[j+gap]) {
            int temp=arr[j];
            arr[j]=arr[j+gap];
            arr[j+gap]=temp;
          }
          count++;
        }
      }
    }
    System.out.println(Arrays.toString(arr));//[3, 5, 38, 44, 48, 50]
    System.out.println("一共比较了："+count+"次");//一共比较了：18次
  }