算法总结

插入排序

直接插入排序

算法描述

1.从第一个元素开始，该元素可以认为已经被排序
2.取出下一个元素，在已经排序的元素序列中从后向前扫描
3.如果该元素（已排序）大于新元素，将该元素移到下一位置
4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5.将新元素插入到该位置后
6.重复步骤2~5

手撕代码–普通

/** * 通过交换进行插入排序，借鉴冒泡排序 */
public static void sort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        for (int j = i + 1; j > 0; j--) {
            if (a[j] < a[j - 1]) {
                int temp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = temp;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

手撕代码–二分查找优化

    private static void binaryInsertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int left = 0;
            int right = i-1;
            while (left<= right) {
                int mid = (left+right)/2;
                if (arr[mid] >tmp) {
                    right = mid -1;
                }else {
                    left = mid+1;
                }
            }
            for (int j = i-1; j >=left ; j--) {
                arr[j+1] = arr[j];
            }
            if (left!=i) {
                arr[left] = tmp;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

效率

希尔排序

算法描述

1、将数组按步长gap两等分
2、相同步长的相邻元素比较大小
3、步长为1时，排序完成

手撕代码

    public static void sort(int []arr){
        //增量gap，并逐步缩小增量
        for(int gap=arr.length/2;gap>0;gap/=2){
            //从第gap个元素，逐个对其所在组进行直接插入排序操作
            for(int i=gap;i<arr.length;i++){
                int j = i;
                while(j-gap>=0 && arr[j]<arr[j-gap]){
                    //插入排序采用交换法
                    swap(arr,j,j-gap);
                    j-=gap;
                }
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

效率

选择排序

选择排序

算法描述

1.从未排序序列中，找到关键字最小的元素
2.如果最小元素不是未排序序列的第一个元素，将其和未排序序列第一个元素互换
3.重复1、2步，直到排序结束。

手撕代码

    public static void sort(int[] a) {
        for (int i = 0; i < a.length; i++) {
            int min = i;
            //选出之后待排序中值最小的位置
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < a[min]) {
                    min = j;
                }
            }
            //最小值不等于当前值时进行交换
            if (min != i) {
                int temp = a[i];
                a[i] = a[min];
                a[min] = temp;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

效率

堆排序

算法描述

此处以大顶堆为例，堆排序的过程就是将待排序的序列构造成一个堆，选出堆中最大的移走，再把剩余的元素调整成堆，找出最大的再移走，重复直至有序。
从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆函数，二是反复调用建堆函数以选择出剩余未排元素中最大的数来实现排序的函数。

总结起来就是定义了以下几种操作:

• 最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点

• 创建最大堆（Build_Max_Heap）：将堆所有数据重新排序

• 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

对于堆节点的访问：

• 父节点i的左子节点在位置：(2*i+1);
• 父节点i的右子节点在位置：(2*i+2);
• 子节点i的父节点在位置：floor((i-1)/2);

手撕代码

public static void sort(int[] a) {

    for (int i = a.length - 1; i > 0; i--) {
        max_heapify(a, i);

        //堆顶元素(第一个元素)与Kn交换
        int temp = a[0];
        a[0] = a[i];
        a[i] = temp;
    }
}

/***
 *
 *  将数组堆化
 *  i = 第一个非叶子节点。
 *  从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
 *  叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
 *
 * @param a
 * @param n
 */
public static void max_heapify(int[] a, int n) {
    int child;
    for (int i = (n - 1) / 2; i >= 0; i--) {
        //左子节点位置
        child = 2 * i + 1;
        //右子节点存在且大于左子节点，child变成右子节点
        if (child != n && a[child] < a[child + 1]) {
            child++;
        }
        //交换父节点与左右子节点中的最大值
        if (a[i] < a[child]) {
            int temp = a[i];
            a[i] = a[child];
            a[child] = temp;
        }
    }
}
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
32
33
34
35
36
37
38
39

效率

交换排序

冒泡排序

算法描述

1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

手撕代码

public static void sort(int[] a) {
    //外层循环控制比较的次数
    for (int i = 0; i < a.length - 1; i++) {
      //内层循环控制到达位置
        for (int j = 0; j < a.length - i - 1; j++) {
            //前面的元素比后面大就交换
            if (a[j] > a[j + 1]) {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

效率

快速排序

算法描述

快速排序使用分治策略来把一个序列（list）分为两个子序列（sub-lists）。步骤为：

1.从数列中挑出一个元素，称为"基准"（pivot）。
2.重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3.递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

代码实现：
1.i = L; j = R; 将基准数挖出形成第一个坑a[i]。
2.j–，由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
3.i++，由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
4.再重复执行2，3二步，直到i==j，将基准数填入a[i]中

手撕代码

public static void sort(int[] a, int low, int high) {
    //已经排完
    if (low >= high) {
        return;
    }
    int left = low;
    int right = high;

    //保存基准值
    int pivot = a[left];
    while (left < right) {
        //从后向前找到比基准小的元素
        while (left < right && a[right] >= pivot)
            right--;
        a[left] = a[right];
        //从前往后找到比基准大的元素
        while (left < right && a[left] <= pivot)
            left++;
        a[right] = a[left];
    }
    // 放置基准值，准备分治递归快排
    a[left] = pivot;
    sort(a, low, left - 1);
    sort(a, left + 1, high);
}
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

效率

归并排序

归并排序

算法描述

递归法（假设序列共有n个元素）：

1.将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素；
2.将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素；
3.重复步骤2，直到所有元素排序完毕。

手撕代码

public class Merge {

    //归并所需的辅助数组
    private static int[] aux;

    public static void sort(int[] a) {
        //一次性分配空间
        aux = new int[a.length];
        sort(a, 0, a.length - 1);
    }

    public static void sort(int[] a, int low, int high) {
        if (low >= high) {
            return;
        }
        int mid = (low + high) / 2;
        //将左半边排序
        sort(a, low, mid);
        //将右半边排序
        sort(a, mid + 1, high);
        merge(a, low, mid, high);
    }

    /**
     * 该方法先将所有元素复制到aux[]中，然后在归并会a[]中。方法咋归并时(第二个for循环)
     * 进行了4个条件判断：
     * - 左半边用尽(取右半边的元素)
     * - 右半边用尽(取左半边的元素)
     * - 右半边的当前元素小于左半边的当前元素(取右半边的元素)
     * - 右半边的当前元素大于等于左半边的当前元素(取左半边的元素)
     * @param a
     * @param low
     * @param mid
     * @param high
     */
    public static void merge(int[] a, int low, int mid, int high) {
        //将a[low..mid]和a[mid+1..high]归并
        int i = low, j = mid + 1;
        for (int k = low; k <= high; k++) {
            aux[k] = a[k];
        }

        for (int k = low; k <= high; k++) {
            if (i > mid) {
                a[k] = aux[j++];
            } else if (j > high) {
                a[k] = aux[i++];
            } else if (aux[j] < aux[i]) {
                a[k] = aux[j++];
            } else {
                a[k] = aux[i++];
            }
        }
    }

}
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

效率