复杂度

常用大O表示法展示算法的时间复杂度和空间复杂度。大O时间复杂度表示代码执行时间随数据规模变化的趋势。下面是常用的时间复杂度
表示代码执行时间是常数级别
一般是循环
一般是嵌套循环
一般是循环步长不为1

排序

冒泡排序(Bubble Sort)

相邻两个元素比较，大值就是冒泡，向右方移动的原地排序算法。时间复杂度最好，只遍历外层循环。最坏的情况

// 冒泡排序，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;  // 没有数据交换，提前退出
  }
}

插入排序(Insertion Sort)

数组分为已排序区域和未排序区域。初始阶段，已排序区域就是第一个元素。未排序区域的元素在已排序区域合适位置插入，将已排序区域中插入点之后的元素移动。

// 插入排序，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; // 插入数据
  }
}

选择排序(Selection Sort)

数据分为已排序区域和未排序区域，从未排序区域中找到最小值插入到已排序区域的尾端。属于不稳定排序

归并排序(Merge Sort)

分治思想，将数据分为两份，将每份数据排序后合并后就是有序数据。一般使用递归实现。分治是解决问题的处理思想，递归是编程技巧。时间复杂度

@Test
public void testMergeSort() {
    int[] src = {5, 3, 4, 7, 2, 8, 1, 9};
    mergeSort(src, 0, src.length - 1);
    System.out.println(Arrays.toString(src));
}

private void mergeSort(int[] src, int left, int right) {
    if (left < right) {
        int middle = (right + left) / 2;
        mergeSort(src, left, middle);
        mergeSort(src, middle + 1, right);
        merge(src, left, middle, right);
    }
}

private void merge(int[] src, int left, int middle, int right) {
    int[] tempArr = new int[src.length];
    int srcIndex = left;

    int rightIndex = middle + 1;
    int leftIndex = left;

    while (leftIndex <= middle && rightIndex <= right) {
        if (src[leftIndex] <= src[rightIndex]) {
            tempArr[srcIndex++] = src[leftIndex++];
        } else {
            tempArr[srcIndex++] = src[rightIndex++];
        }
    }

    while (leftIndex <= middle) {
        tempArr[srcIndex++] = src[leftIndex++];
    }

    while (rightIndex <= right) {
        tempArr[srcIndex++] = src[rightIndex++];
    }

    while (left <= right) {
        src[left] = tempArr[left++];
    }
}

快速排序(Quick Sort)

分治思想，从排序数据中选取分区点(pivot)，然后遍历数据，大于pivot的放在右边，小于pivot放在左边。然后在左边的数据中选取分区点排序。将所有小序列排序完成。最后再合并数据。平均时间复杂度是，最坏情况是，但通过随机算法可以避免最坏情况。由于递归调用，快排的空间复杂度是 。下面算法选取维基百科快速排序。

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。
步骤为：

1. 挑选基准值：从数列中挑出一个元素，称为“基准”（pivot），
2. 分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成，
3. 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。

桶排序(Bucket Sort)

排序数据分到几个有序的桶中，在桶中快速排序。适合外部排序，数据量大无法一次性读入内存。

计数排序(Counting Sort)

数据分到有序桶中，每个桶中的数据都是一致的。例如，满分100分，10000个学生。将桶分为101个，分数相同的学生放入相应的桶中，桶中计数学生个数。

基数排序(Radix Sort)

例如整数排序，整理数据为相同的位，然后比较每一位来排序。