chenxin's blog
0%

算法-匹配与排序

发表于 更新于 分类于

KMP算法

如果让我们快速想出一种匹配算法，可能想到的就是挨个匹配字符，如果出现不匹配的字符再移动一位字符继续比较，这不是高效的做法，它每次都回到被匹配串的i+1的位置重新开始比较，导致很多重复比较，而KMP算法就是要利用模式串的字符信息避免这种重复的比较，让我们能遍历一趟被匹配字符串就可以完成匹配。

思路： 写KMP算法主要是写怎样生成next数组，不用按照书上的那种非常简洁的做法写，理解起来非常困难，回到原理，按原理的顺序写基本逻辑的代码

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
57
58
59
60
61
62

private static int[] generateNext(String s) {
    int[] next = new int[s.length()];
    //从第2位开始，因为第0位没有前缀；第1位只有一个前缀字符（0位字符），这种情况在第1位出现了不匹配，只能将第0位拿来对齐，所以干脆就直接赋值为0了
    for (int i = 2; i < s.length(); i++) {
        //第i个字符的前缀字符串中，能拼接出（i-1）个有效前缀子串，因为要排除掉整个前缀字符串的情况，这种情况直接赋值为0，重新开始匹配
        int j = i - 1;
        while (j > 0) {//遍历每一个前缀子串和与之对应的后缀子串
            int length = i - j;//子串的长度
            int m = 0;//前缀子串起始位置
            int n = j;//后缀子串起始位置
            boolean match = true;//是否完全匹配
            for (int k = 0; k < length; k++) {
                if (s.charAt(m) != s.charAt(n)) {
                    match = false;
                    break;
                }
                m++;
                n++;
            }
            if (match) {//前后缀子串完全匹配，那么第i位置字符对应的next直接就恰好是length这个值
                next[i] = length;
            }
            //我们计算的是最长的前缀串，所以需要继续遍历更长的前缀子串
            j--;
        }
    }
    return next;
}

private static int kmp(String str, String pattern) {
    int[] next = generateNext(pattern);
    for (int i = 0; i < next.length; i++) {
        System.out.print(next[i] + ",");
    }
    //j用来遍历模式串
    int j = 0;
    //i遍历主串
    for (int i = 0; i < str.length(); i++) {
        //如果出现不相等的情况，找出模式串的下一个位置
        while (j > 0 && str.charAt(i) != pattern.charAt(j)) {
            j = next[j];
        }
        //相等，比较下一个
        if (str.charAt(i) == pattern.charAt(j)) {
            j++;
        }
        //下一个到末尾，证明匹配完成
        if (j == pattern.length()) {
            return i - pattern.length() + 1;
        }
    }
    return -1;
}

public static void main(String[] args) {
    String str = "acbccddddddfeeffde";
    String pattern = "fee";
    int index = kmp(str, pattern);
    System.out.println("首次出现位置：" + index);
}

排序算法

公用交换位置的方法：

1
2
3
4
5
6
void swap(int[] arr,int i,int j){
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}

选择排序

两个遍历嵌套，第一层遍历是需要遍历的次数，第二层遍历是每次遍历时具体的比较方式，特点是固定被排序的位置，和剩余数组中最大的那个交换

1
2
3
4
5
6
7
8
9
public static void selectSort(int[] list) {
    for (int i = 0; i < list.length; i++) {
        for (int j = i + 1; j < list.length; j++) {
            if (list[j] < list[i])
                swap(list, i, j);
        }

    }
}

冒泡排序

思路： 两个遍历嵌套，第一层遍历是需要遍历的次数，第二层遍历是每次遍历时具体的比较方式，特点是挨个比较，每次都找出剩余数组中最大的那个
由于是挨个两两比较，没有跨空间访问的情况，所以实际使用时会比选择排序快

1
2
3
4
5
6
7
8
public static void bubbleSort(int[] list) {
    for (int i = 1; i < list.length; i++) {
        for (int j = 1; j <= list.length - i; j++) {
            if (list[j - 1] > list[j])
                swap(list, j - 1, j);
        }
    }
}

插入排序

** 思路： 假设前i-1个数组是有序的，新来第i位数字，从第i-1位开始向前比较，逆序交换，顺序就跳出**

1
2
3
4
5
6
7
8
9
public static void insertSort(int[] list) {
    for (int i = 1; i < list.length; i++) {
        for (int j = i; j >= 1; j--) {
            if (list[j] < list[j - 1])
                swap(list, j - 1, j);
            else break;
        }
    }
}

归并排序

思路： 将数组等分为左右两个等长的数组，每次都假设它们是排好序的，再将它们合并成为一个2倍长度的数组，依次从下向上递归

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
   private static int[] copy;
   public static void mergeSort(int[] list) {
       copy = new int[list.length];
       mergeSort(list, 0, list.length - 1);
   }

   public static void mergeSort(int[] list, int from, int to) {
       if (from >= to) return;
       int mid = (from + to) / 2;
       mergeSort(list, from, mid);
       mergeSort(list, mid + 1, to);
       merge(list, from, mid, to);
   }

//middle算作是左边数组的终点
   private static void merge(int[] list, int from, int mid, int to) {
       int p1 = from;
       int p2 = mid + 1;

       for (int i = from; i <= to; i++) {
           copy[i] = list[i];
       }
       for (int i = from; i <= to; i++) {
           if (p1 > mid) list[i] = copy[p2++];
           else if (p2 > to) list[i] = copy[p1++];
           else if (copy[p1] < copy[p2]) list[i] = copy[p1++];
           else list[i] = copy[p2++];
       }

   }

快速排序

思路：主要是切分，每次以第一个数字作为切分数，两个左右指针遍历，左指针找到一个比它大的，右指针找到一个比它小的就交换这两个位置，注意临界情况。找到该数的位置后，以该位置作为分割，左右数组再继续切分，递归完事

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

   public static int partition(int[] list, int from, int to) {
       int val = list[from];
       int p1 = from;
       int p2 = to + 1;
       while (true) {
           while (list[++p1] < val) {
               if (p1 == to) break;
           }
           while (list[--p2] > val) {
               if (p2 == from) break;
           }
           if (p1 >= p2) break;
           swap(list, p1, p2);
       }
       swap(list, p2, from);
       return p2;
   }

public static void quickSort(int[] list, int from, int to) {
       if (from >= to) return;//一定是大于等于！！
       int p = partition(list, from, to);
       quickSort(list, from, p - 1);
       quickSort(list, p + 1, to);
   }

堆排序

思路： 主要写下沉函数，左子结点是2xi+1，右子结点是2xi+2，选出这三个结点中最值结点与父结点交换，如果发现发生了下沉，需要对下沉的子结点继续下沉。优先堆，求数组的top k都用这个方法

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
public class HeapSort {

    public static void main(String[] args) {
        int[] a = new int[]{39, 8, 45, 3, 91, 28, 4, 60, 49, 7, 1, 24, 92};
        new HeapSort().heapSort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + ", ");
        }

    }

    void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    //下沉函数，i是被下沉的位置，len是下沉的边界
    void sink(int[] arr, int i, int len) {
        int left = 2 * i + 1;//左子节点
        int right = 2 * i + 2;//右子节点
        int largest = i;//三个节点中，值最小的那个位置
        if (left < len && arr[left] < arr[largest]) {
            largest = left;
        }
        if (right < len && arr[right] < arr[largest]) {
            largest = right;
        }
        if (largest != i) {//如果不是父结点，说明发生了下沉，需要对下沉的结点继续下沉
            swap(arr, i, largest);
            sink(arr, largest, len);
        }
    }

    //构建最小堆，只需要下沉前半部分结点
    void buildMinHeap(int[] arr) {
        for (int i = arr.length / 2; i >= 0; i--) {
            sink(arr, i, arr.length);
        }
    }


    void heapSort(int[] arr) {
        buildMinHeap(arr);
        //排序，构建完最小堆的数组，第0个位置就是最小的，把它与最后的位置交换，然后对0位置下沉，就会选出这个新的堆的最小数，重复这个步骤
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);
            sink(arr, 0, i);
        }
    }
}