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

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次  }