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

原地排序

原地排序算法，就是指空间复杂度是O(1)的排序算法。

稳定性

如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变那这个算法就是稳定的排序算法，反之就是不稳定的排序算法。

冒泡排序

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

最好情况下时间复杂度：O(n)

最坏情况下时间复杂度:O(n²)

平均时间复杂度：O(n²)

算法代码：

// 冒泡排序，a表示数组，n表示数组大小
public void bubbleSort(int[] a, int n) {
  if (n <= 1) return;
 
  for (int i = 0; i < n; ++i) {
    // 提前退出冒泡循环的标志位
    boolean flag = false;
    for (int j = 0; j < n - i - 1; ++j) {
      if (a[j] > a[j+1]) { // 交换
        int tmp = a[j];
        a[j] = a[j+1];
        a[j+1] = tmp;
        flag = true;  // 表示有数据交换      
      }
    }
    if (!flag) break;  // 没有数据交换，提前退出
  }
}

插入排序

插入排序的思路是，首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

最好情况下时间复杂度：O(n)

最坏情况下时间复杂度:O(n²)

平均时间复杂度：O(n²)

算法代码

// 插入排序，a表示数组，n表示数组大小
public void insertionSort(int[] a, int n) {
  if (n <= 1) return;

  for (int i = 1; i < n; ++i) {
    int value = a[i];
    int j = i - 1;
    // 查找插入的位置
    for (; j >= 0; --j) {
      if (a[j] > value) {
        a[j+1] = a[j];  // 数据移动
      } else {
        break;
      }
    }
    a[j+1] = value; // 插入数据
  }
}

选择排序

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为 O(n2)。

选择排序是一种不稳定的排序算法。

算法代码

public int[] selectionSort(int[] sourceArray) throws Exception {
      int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

       // 总共要经过 N-1 轮比较
       for (int i = 0; i < arr.length - 1; i++) {
           int min = i;
           // 每轮需要比较的次数 N-i
           for (int j = i + 1; j < arr.length; j++) {
               if (arr[j] < arr[min]) {
                   // 记录目前能找到的最小值元素的下标
                   min = j;
               }
           }

           // 将找到的最小值和i位置所在的值进行交换
           if (i != min) {
               int tmp = arr[i];
               arr[i] = arr[min];
               arr[min] = tmp;
           }

       }
       return arr;
   }