维基百科-快速排序
维基百科-归并排序
cnblog-排序算法

桶排序

利用了空间换时间的概念,开辟了一个单位大小的数组 然后排序时让数据直接在这个数组的指定位置加一表示这个数据的数量，而数据本身的大小则被替换成数组下标的index，因此利用这个特性能够实现o1复杂度的排序。

算法描述

桶排序是一种直接的排序算法，利用数组下标本身有序的特点，使用空间换时间的概念而进行的排序。

  • 首先找到数列中最大值(max)和最小值(min)
  • 然后创建一个大小为max - min + 1的数组
  • 遍历源数列，取出原数列中的元素，创建偏移函数使之从 0 开始计数

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public static void bucketSort(int[] arr) {
    int max = 0;
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < arr.length; i++) {
        if (min > arr[i]) {
            min = arr[i];
        }
        if (max < arr[i]) {
            max = arr[i];
        }
    }

    int[] results = new int[max - min + 1];
    for (int i = 0; i < arr.length; i++) {
        results[adjustIndex(min, arr[i])]++;
    }

    int i = 0, index = 0;
    while (i < results.length) {
        if (results[i] != 0) {
            arr[index++] = min + i;
            results[i]--;
        } else {
            i++;
        }
    }
}

private static int adjustIndex(int min, int value) {
    return value - min;
}

冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字的由来是因为越小的元素会经由交换慢慢”浮”到数列的顶端。

算法描述

  • 每一轮最大（小）的元素则会浮到最后一个元素
  • 执行 n -1 轮
  • 每一轮中比较相邻的元素。如果第一个比第二个大（小），则进行交换，第i轮时（i从0开始）则进行比较前n - 1 - i 个元素。
  • 重复执行 1 ~ 3直到结束

代码实现

1
2
3
4
5
6
7
8
9
10
11
public void bubbleSort(int[] arr){
   for (int i = 1; i < arr.length; i++) {
        for (int j = 0; j < arr.length - i; j++) {
            if (arr[j + 1] < arr[j]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }	
}

动图展示