排序算法

• 冒泡排序
• 插入排序
• 快速排序
• 选择排序
• 希尔排序

1冒泡排序

1.1 原理

每轮循环 多次两两比较选出一个最大的排在最后面

1.2 原码

/**
* Description TODO 冒泡排序
* Author Cloudr
* Date 2020/4/1 22:43
**/
public class BubbleSort {
    private static void bubbleSorts(int[] a) {

        int i, j, temp;

        for (i = 0; i < a.length - 1; i++) {       //每轮都是把最大的数排到最后 注意是 a.length-1 因为下文有一个j+1
            for (j = 0; j < a.length - 1 - i; j++) { //每次需要排的个数减少i个
                if (a[j] > a[j + 1]) {
                    temp = a[j + 1];
                    a[j + 1] = a[j];
                    a[j] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {1, 253, 56, 745, 342, 41, 654, 321432, 131, 324};
        bubbleSorts(a);
        for (int i : a) {
            System.out.println(i);
        }
    }
}

1.3 复杂度

* 时间复杂度

---

2直接插入排序

2.1 原理

直接插入排序是将未排序的数据插入至已排好序序列的合适位置。

具体流程如下：

1、首先比较数组的前两个数据，并排序；

2、比较第三个元素与前两个排好序的数据，并将第三个元素放入适当的位置；

3、比较第四个元素与前三个排好序的数据，并将第四个元素放入适当的位置；

……

4、直至把最后一个元素放入适当的位置。

2.2 代码

public class insertSort {
    private static void insertSort(int[] a) {
        int Temp;
        for (int i = 1; i < a.length; i++) { //注意是从i=1开始的
            Temp = a[i];                    //必须要用Temp 否则移动过程中会改变a[i]的值
            int j;
            for (j = i - 1; j >= 0; j--) {  //从已经排好的序列中的末尾（即最大的开始比较），即是从0~i-1与a[j]比较 
                if (a[j] > Temp)
                    a[j + 1] = a[j];
                else {
                    a[j + 1] = Temp; //因为之前j--了一次
                    break;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 4, 623, 1, 132, 634, 2, 3, 4};
        insertSort(a);
        for (int i : a) {
            System.out.println(i);
        }
    }
}

---

3快速排序

• https://www.bilibili.com/video/BV1at411T75o/

  3.1原理简述

• 找一个基准数，将大于这个基准数的数放在右边，小于它的放在其左边
• 

  3.2源代码

  public class QuickSort {
  
      private static void quickSort(int[] a, int left, int right) {
  //        将a分成一边大的，一边小的，重复执行这个过程
          if (left < right) {
              int index = getIndex(a, left, right);
              quickSort(a, left, index - 1);
              quickSort(a, index + 1, right);
          }
      }
  
      private static int getIndex(int[] a, int left, int right) {
  
          int standard = a[left]; // 基准数据
          while (left < right) {
              while (left < right && a[right] >= standard) { //必须要 >= 不然 =等于那个得不到处理 left也指不到这边
                  right--;                                   // 当队尾的元素大于等于基准数据时,向前挪动high指针
              }
              a[left] = a[right];                            //将小于基准数据的值放到左边（小的一边）
              while (left < right && a[left] <= standard) {
                  left++;
              }
              a[right] = a[left];                           //将大于基准数据的值放到右边（大的一边）
          }
          a[left] = standard;                               //此时left==right 同时这个位置也是standard的位置
          return left;
      }
  
      public static void main(String[] args) {
          int[] a = {1, 2, 4, 2, 21, 563, 1, 6246, 13, 4331};
          quickSort(a, 0, a.length - 1);
          for (int i : a) {
              System.out.println(i);
          }
      }
  }

---

4选择排序

4.1原理简述：

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

• 

4.2源代码

public class SelectSort {
    private static void select(int[] a) {
        for (int i = 0; i < a.length; ++i) {
            int index = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[index] > a[j]) {
                    index = j; // 找到当前循环中最小的数的索引
                }
            }
            int temp = a[index];
            a[index] = a[i];
            a[i] = temp;
        }
    }

    public static void main(String[] args) {

        int[] a = {2, 1, 63, 2, 12, 7, 3, 12, 78, 6, 43};
        select(a);
        for (int i : a) {
            System.out.println(i);
        }

    }
}

---

5希尔排序

• 希尔排序

  5.1原理简述

希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

5.2源代码

public class ShellSort {
    private static void shell(int[] a) {
        int gap = a.length / 2;  //增量，每隔gap为一组
        while (gap >= 1) {
            for (int i = gap; i < a.length; i++) { //依次遍历每一组 i=gap是因为后面的j-gap才有意义
                int j = i;
                while (j - gap >= 0 && a[j] < a[j - gap]) { //遍历每一组 如何发现后面的小于前面的则交换
                    int temp = a[j];                        //这里不采用每次给j+gap是因为 会有gap个a[j]遍历不到 换种方法也会比较麻烦
                    a[j] = a[j - gap];
                a[j - gap] = temp;

                    j = j - gap;
                }
            }
            gap = gap / 2;
        }
}

    public static void main(String[] args) {
        int[] a = {3, 2, 5, 7, 43, 12, 15, 33, 15, 2, 12, 14, 3};
        shell(a);
        for (int i : a) {
            System.out.println(i);
        }
    }
}

图片来源于网络，如有侵权请联系我删除，谢谢。

参考：https://www.sohu.com/a/299382768_478315

           https://www.cnblogs.com/guoyaohua/p/8600214.html