1.排序算法介绍

• 排序是算法中很重要的一个环节，很多查询的基础就是排序，关于排序的算法非常多,而且各有优缺点.记下来介绍几种最为简单容易理解的排序算法:

  • 选择排序

  • 冒泡排序

  • 插入排序

2.选择排序

• 选择排序的主要思想是寻找未排序中最小的元素加入到已有序列,直到未排序序列为空。有一无序数组,如下,现按照选择排序的规则进行升序排序:

  

• 现将该数组分为两个部分,第一部分为有序部分,第二部分为无序部分,在初始时,有序部分的元素数量为0,全部为无序部分:

  

• 首先在无序部分中寻找最小元素所在的位置,然后将其与第一位的元素交换:

  

• 其余的按照上述方法继续执行:

  

   

• 直到进行到所有无序部分的元素都被排序:

  

   

• 选择排序的特点是查询次数较多,元素位置变换较少,比较适合易于查询而移动较复杂的数据

• 代码

  //排序
  public class SortTest {
      public static void main(String[] args) {
          int[] ary = { 3, 6, 2, 4, 1 };
          selectSort(ary); // 选择排序
      }
      // 选择排序
      private static void selectSort(int[] ary) {
          int smallerIndex; // 保存较小的数的位置
          for (int i = 0; i < ary.length - 1; i++) { // 外层循环 n-1趟排序 每一趟排序 ，找到一个最小值，放到有序区域
              smaller = i; // 初始默认i为较小的数的位置
              for (int j = i + 1; j < ary.length; j++) { // 无序区域的循环 目的是找最小值的位置(下标)
                  if (ary[smallerIndex] > ary[j]) { // 找比smaller更小的数
                      smallerIndex = j; // 把更小的数的位置赋值给了smaller
                  }
              }
              if (smaller != i) { // 如果最小值的下标已经不是i了，证明最小值是其它的数，交换 ;
                  // 交换 i smaller
                  int temp = ary[smallerIndex];
                  ary[smallerIndex] = ary[i];
                  ary[i] = temp;
              }
          }
  ​
          // 排序好的数组进行遍历
          for (int i : ary) {
              System.out.println(i);
          }
      }
  }

3.冒泡排序

• 冒泡排序主要的思想是进行相邻的两个元素之间比较并且交换，有利于利用原有元素在集合中的位置优势，冒泡排序的原则是大的下沉小的上浮（跟最终的排序要求保持一致）

• 仍然对之前的数据按照冒泡进行排序：

  

• 第一轮的排序，首先比较前两个元素,如果顺序与升序相反则交换,否则什么也不做：

  

• 然后,依次比较第二位与第三位,第三位与第四位,…..

  

• 第一轮的排序：

  

   

• 代码

  // 冒泡
  private static void bubbleSort(int[] ary) {
      // 外层循环 n-1趟排序 ，每一趟排序，都有一个最大或者最小数沉底
      for (int i = 0; i < ary.length - 1; i++) {
          // 每趟是n-1-i(除去每次排序沉底的数)次比较
          for (int j = 0; j < ary.length - i - 1; j++) {
              // 两个两个比较并交换
              if (ary[j] > ary[j + 1]) {
                  // 交换 红墨水和黑墨水互换
                  int temp = ary[j]; // 当前的数据赋值给temp临时变量
                  ary[j] = ary[j + 1]; // 后一个数赋值给当前
                  ary[j + 1] = temp; // temp临时变量里的值赋值给后一个数
              }
          }
      }
  ​
      for (int i : ary) {
          System.out.println(i);
      }
  }

4.插入排序

• 插入排序与选择排序类似，需要将数组分为有序与无序两部分。但插入不会去到无序部分选择，而是随意选取一个无序部分元素到有序部分中寻找它所在的位置进行插入保持有序部分仍然有序，如果要对数据进行排序：

  

• 首先认为第一个元素部分为有序部分：

  

• 选取无序部分的第一个元素,到有序部分中寻找位置并插入：

  

• 其后依次进行

  

• 插入排序：

  

• 代码

  // 插入排序
  private static void insertSort(int[] data) {
      int current;
      for (int i = 1; i < data.length; i++) {
          current = data[i];
          for (int j = i - 1; j >= 0; j--) {
              if (current < data[j]) {
                  data[j + 1] = data[j];
              } else {
                  data[j + 1] = current;
                  break;
              }
              if (j == 0) {
                  data[j] = current;
              }
          }
      }
  ​
      for (int i : data) {
          System.out.print(i + "/t");
      }
  }

• 正如之前的章节介绍的，Java中已经实现了数组排序的方法（Arrays.sort()），该方法不仅可以对数字类型数据进行排序，还可以通过提供比较器的方式对对象数组进行排序