一文带你读懂排序算法（一）：冒泡 & 快速选择排序 & 简单插入排序算法

后台技术汇

发布于 2022-05-28 12:09:21

1890

发布于 2022-05-28 12:09:21

文章被收录于专栏：后台技术汇

排序是确保数据规则有序的有效手段。日常开发里，我们常用到的是“冒泡”、“插入排序”、“选择排序”三种。

大部分情况下，后台处理大规模数据量的排序问题，都能借助数据库（Mysql或Oracle）的排序字段声明（order by ${field} desc/asc），让数据库引擎帮忙处理数据。但是总是有一些特殊情况，比如数据聚合等操作，没法借助第三方工具来帮助实现这个排序过程，这时，基础排序算法就派上用场了。

而且，了解最基础的排序算法，也是对面试笔试有着莫大帮助的哦，尤其是应届生，排序算法一般都是开发岗位的必考题。

冒泡法

冒泡算法思想：

对于给定的n记录，从第一个开始依次对相邻的两个记录进行比较，若a[j-1] > a[j]，那么两者进行交换，，进行了一轮比较后，n个记录的最大将位于第n位；接着，对前（n-1）个记录进行第二轮比较；重复该过程进行到只剩下一个为止。

代码示例

public class BubbleSort {
  public static void main(String[] args) {
    sort();
  }

  public static void sort(){
    int[] arr = {88,66,999,45,22,1,35,68,88,44,11,99,85,253,44,56};
    int temp = 0;
    for(int i=0; i<arr.length; i++){
      for(int j = 1; j<arr.length -i; j++){
        //数组最大值被交换到下标最大位置
        if (arr[j-1]>arr[j]){
          temp = arr[j-1];
          arr[j-1] = arr[j];
          arr[j] = temp;
        }
      }
    }
    for (int a=0; a<arr.length; a++){
      System.out.println("序列的第"+a+"元素是："+arr[a]);
    }
  }
}

简单选择排序法

简单选择排序法的思想：

对于给定的一组记录，经过第一轮比较得到最小的记录，然后将该记录与第一个记录位置交换；然后（除去第一个）对其他记录进行第二轮比较，最小与第二个记录位置交换，重复过程至剩下一个。

代码示例

public class SelectionSort {
  public static void main(String[] args) {
    int[] a = {9,8,7,6,5,4,3,2,1,0};
    selectionSort(a);
  }

  public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n; i++) {
      int k = i;
      //find out the smallest one.
      for (int j = i + 1; j < n; j++) {
        if (arr[j] < arr[k]) {
          k = j;
        }
      }
      //把最小值元素跟头部元素交换
      if (k > i) {
        int temp = arr[i];
        arr[i] = arr[k];
        arr[k] = temp;
      }
    }

    for (int a=0; a<arr.length; a++){
      System.out.println("序列的第"+a+"元素是："+arr[a]);
    }
  }
}

直接插入排序法

插入排序算法思想：

从第二个记录开始，与第一个组成子序列，比较选出最小者，插入到最前方（索引为0），此时两个元素为有序序列；然后加入第三个元素组成新的序列，根据大小将其插入到有序序列中；依次插入所有元素后，直至停止。

代码示例

public class StrightInsertion {
  public static void main(String[] args) {
    int[] arr = {12, 15, 13, 46, 55, 1, 5, 3};
    strightinsertion(arr);
  }
  public static void strightinsertion(int [] arr){
    int tmp ;
    for (int i=1; i<arr.length; i++){
      for(int j=i; j>0; j--){
        if (arr[j]<arr[j-1]){
          tmp = arr[j-1];
          arr[j-1] = arr[j];
          arr[j] = tmp;
        }
      }
    }
    for (int a=0; a<arr.length; a++){
      System.out.println("序列的第"+a+"元素是："+arr[a]);
    }
  }
}

时间复杂度与空间复杂度

排序算法	最好时间	平均时间	最坏时间	辅助存储	稳定性	备注
冒泡	Ο(n)	Ο(n²)	Ο(n²)	Ο(1)	稳定	n小时较好
简单选择	Ο(n²)	Ο(n²)	Ο(n²)	Ο(1)	不稳定	n小时较好
直接插入	Ο(n)	Ο(n²)	Ο(n²)	Ο(1)	稳定	大部分有序较好