Code

排序和字符串匹配

摘要

排序

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

直接插入排序

  • 与摸扑克牌时整理手中牌的方法相同，每次将一个新的元素插入已排序的元素中。这种方法在待排序序列基本有序的情况下效率很高。复杂度O(n^2)。是稳定的排序法。
  • 代码（java，以整型数据升序排序为例）
1
2
3
4
5
6
7
8
public static void insertSort(int []arr){
	for ( int i = 1 ; i < arr.length ; i++ ){
		int j, key = arr[i];
		for ( j = i - 1 ; j >= 0 && key < arr[j] ; j-- )   // only "key < arr[j]" but not " <= " is stable
			arr[j+1] = arr[j];
		arr[j+1] = key;
	}
}

希尔排序

  • 希尔排序是对直接插入排序的改进，比较是希尔排序最主要的操作，而不是交换。先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成），对每个子序列进行直接插入排序，然后缩减增量再进行排序，直到整个序列中的元素基本有序（增量足够小），再对全体元素进行一次直接插入排序。此时元素基本有序，效率很高。“增量”的选择是希尔排序的重要部分，只要最终步长为1任何步长序列都可以工作（当步长为1时，算法变为插入排序，这就保证了数据一定会被排序）。已知的最好增量序列是由Sedgewick提出的(1, 5, 19, 41, 109,…)，该序列的项来自9 \times 4^i - 9 \times 2^i + 1和2^{i+2} \times (2^{i+2} - 3) + 1这两个算式。用这样增量序列的希尔排序比插入排序和堆排序都要快，在小数组中速度甚至超过快速排序，但是在涉及大量数据时希尔排序还是比快速排序慢。另一个在大数组中表现优异的步长序列是斐波那契数列除去0和1将剩余的数以黄金分区比的两倍的幂进行运算得到的数列。希尔排序不是稳定的排序。
  • 代码（java，以整型数据升序排序为例）
1
2
3
4
5
6
7
8
9
10
11
public static void swap(int []arr, int l, int r){
	int temp = arr[l];
	arr[l] = arr[r];
	arr[r] = temp;
}
public static void shellSort(int []arr)  { 
    for (int gap = arr.length / 2; gap > 0; gap /= 2)  
        for (int i = gap; i < arr.length; i++)  
            for (int j = i - gap; j >= 0 && arr[j] > arr[j + gap]; j -= gap)  
                swap(arr,j, j + gap);  
}

选择排序

  • 每次从待排序的元素中选取最大（最小）的元素放到已排序序列的末尾。复杂度O(n^2)。是不稳定排序。
  • 代码（java，以整型数据升序排序为例）
1
2
3
4
5
6
7
8
9
10
public static void selectSort(int []arr){
	for ( int i = 0 ; i < arr.length - 1 ; i++ ){
		int min = i;
		for ( int j = i + 1 ; j < arr.length ; j++ )
			if ( arr[j] < arr[min] )
				min = j;
		if ( min != i )
			swap(arr, i, min);
	}
}

冒泡排序

  • 每次交换相邻的两个元素，若前者大于后者就交换，当第一次对全部元素完成该步骤后，最后一个元素即为最大值，对越来越少的元素重复上述步骤，直到全部数据比较完成。复杂度O(n^^2)。是稳定排序。
  • 代码（Golang，以整型数据升序排序为例）
1
2
3
4
5
6
7
8
9
func bubbleSort(arr []int, n int) {
	for i := 0; i < n-1; i++ {
		for j := 0 ; j < n-1-i; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}
}

归并排序

  • 分治思想，将待排序元素分成两份，之后对每份分别排序，排序完成后再合并成一个序列。排序过程可以递归完成，直到待排序的某个序列为单个元素即可返回。复杂度O(NlogN)。是稳定排序。
  • 代码（java，以整型数据升序排序为例）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void mergeSort(int []arr, int l, int r){
	if ( l < r ){
		int mid = ( l + r ) >> 1;
		mergeSort(arr, l, mid);
		mergeSort(arr, mid+1 , r);
		int l1 = mid - l + 1, l2 = r - mid;
		int i, j;
		int [] L = new int[l1+1], R = new int[l2+1];
		for ( i = 0; i < l1 ; i++ )
			L[i] = arr[l+i];
		for ( j = 0; j < l2 ; j++)
			R[j] = arr[mid+j+1];
		L[l1] = R[l2] = INF;
			i = j = 0;
		for ( int k = l ; k <= r ; k++){
			if ( L[i] <= R[j] )
				arr[k] = L[i++];
			else 
				arr[k] = R[j++];
		}
	}
}

堆排序

  • 利用二叉堆（分为最大堆/大根堆和最小堆/小根堆）管理数据，数据存储形式可以视为完全二叉树，除了最后一层的每一层都是填满的。用数组存储这个堆时，给定某个节点的下标i，其父节点Parent(i)，左孩子Left(i)和右孩子Right(i)分别为i/2，2×i和2×i+1。以最大堆为例，堆中的最大元素存放在根节点当中，在以某个节点为根的子树中，各节点的值均不小于该子树根节点的值，也就是除了根以外的每个节点都满足Parent(i).value >= i.value。堆排序中通常使用最大堆，最小堆一般在构造优先队列时使用。其时间复杂度O(NlogN)，是不稳定排序。
1
2
3
4
5
6
7
8
9
public static int Parent( int i ){
	return i >> 1;
}
public static int Left( int i ){
	return 2 * i;
}
public static int Right( int i ){
	return 2 * i + 1;
}
  • 堆的维护（最大堆为例），维护时自顶向下，将根节点与两个子女比较，如果满足最大堆性质则无需调整， 否则将两个子女中的较大者和根交换，此时原本以被交换的子女为根的子树可能被破坏了最大堆性质，要对该子树维护，递归即可。该操作最坏情况下的复杂度与该操作作用的节点深度有关，对于深度h的节点，复杂度O(h)。
    下例中的heapsize为当前堆中元素数目，i为需要维护的节点。
1
2
3
4
5
6
7
8
9
10
11
public static void MaxHeapify(int []arr, int i, int heapsize){
	int l = Left(i), r = Right(i), largest = i;
	if ( l <= heapsize && arr[l] > arr[i] )
		largest = l;
	if ( r <= heapsize && arr[r] > arr[largest] )
		largest = r;
	if ( largest != i ){
		swap(arr, i, largest);
		MaxHeapify(arr, largest,heapsize);
	}
}
  • 建堆（最大堆为例），对于一个序列，可以自下而上通过不断维护非叶节点构造。根据Parent(i) = i/2，可以知道长度为n的序列中前n/2个元素为非叶节点。容易理解自下向上的维护可以保证整棵树的性质成立。
1
2
3
4
public static void BuildHeap(int []arr){
	for ( int i = (arr.length-1) / 2 ; i >= 1 ; i--)
		MaxHeapify(arr, i,arr.length-1);
}
  • 排序（最大堆为例），先对待排序序列建堆，之后每次取出根节点元素（该元素为堆中剩余元素最大值），并用堆中最后一个元素代替它，再维护根节点。即每取出一个元素，堆中元素数量减一，但性质得以保持。
1
2
3
4
5
6
7
8
public static void HeapSort(int[] arr){
	BuildHeap(arr);
	int heapsize = arr.length - 1;
	for ( int i = heapsize ; i >= 2 ; i--){
		swap(arr, 1, i);
		MaxHeapify(arr, 1,--heapsize);
	}
}

快速排序

  • 快速排序同样基于分治思想，对于开始的待排序序列，选取一个“标准元素”，每个元素都和这个标准元素比较，大的放在一边，小的放在另一边。之后将这个标准元素两边（一边都比它大，一边都比它小）分别作为待排序序列重复上述操作，直到每个待排序序列为一个元素，递归结束后即为有序序列。时间复杂度O(NlogN)，为不稳定排序。快速排序用途最为广泛并且容易编写。
  • 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int Partition(int []arr, int l, int r) {
	int cmp = arr[r];
	int i = l - 1;
	for ( int j = l ; j < r ; j++ )
		if ( arr[j] < cmp )
			swap(arr, ++i, j);
		swap(arr, i+1, r);
	return i+1;
}
public static void QuickSort(int []arr, int l, int r){
	if ( l < r ){
		int mid = Partition(arr, l, r);
		QuickSort(arr, l, mid-1);
		QuickSort(arr, mid+1, r);
	}
}

线性时间排序

上面的排序方法均采用比较操作，这类排序算法被称作比较排序。线性时间排序均采用非比较操作。应用不多，不介绍。

  • 计数排序
  • 基数排序，有链表实现的代码。
  • 桶排序

字符串匹配

字符串匹配算法较多，暴力实现最容易编写并且效率不低，同样时间复杂度的算法还有Sunday，Robin-Karp和Bitap。相比下BF无需预处理，更容易编写。他们的时间复杂度都为O(N*M)，N为源文本长度，M为要匹配的字符串长度。

Brute Force

暴力搜索，将源文本的每个字符元作为匹配字符串的起点比较，若出现匹配则返回，否则将下一字符元作为起点。

  • 代码（C语言。java调用indexOf或者contains方法即可）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int BruteForce( const char *source, const char *tofind )  
{  
    if ( source == '\0' || tofind == '\0' )  
        return -1;
    if ( strlen( source ) < strlen( tofind ) )
        return -1;  
    char *s = source, *p = source, *q = tofind;
    while ( *p != '\0' )  
    {  
        if ( *p == *q ){  
            p++;  
            q++;  
        }
        else{  
            p = ++s;  
            q = tofind;  
        }  
        if ( *q == '\0' )  
            return ( p - source ) - ( q - tofind ); 
    }  
    return -1;  
}

比Brute Force更快捷，并且实现起来也同样简单的是KMP算法，它需要O(M)的时间用于预处理要匹配的字符串，匹配的时间复杂度只有O(N)。同样复杂度的还有Boyer Moore算法，其效率稍高，但实现复杂。KMP可以满足多数情况的需求。

KMP

  • KMP先对要匹配的字符串预处理，当发现某个位置作为开头与源文本匹配不成功时，不会像朴素算法一样将源文本紧邻的下一个字符元作为字符串开头匹配，而是将要匹配的字符串目前匹配到的位置跳到下一个可能匹配成功的地方。
  • 这里有一篇非常清楚、简明的文章，字符串匹配的KMP算法，很容易明白KMP的原理。
  • 代码实现
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
void GetNext( char * toFind ) {
    int k = -1, j = 0;
    next[0] = -1;
    while ( j < strlen( toFind ) - 1 ){
        if ( k == -1 || toFind[k] == toFind[j] )
            next[++j] = ++k;
        else
            k = next[k];
	}
}

int KMP( char * source, char * toFind ){
    int i = 0, j = 0;
    GetNext( toFind );
    while ( i < strlen( source ) ){
        if ( j == -1 || source[i] == toFind[j] ){
            i++;
            j++;
        }
        else
            j = next[j];
        if ( j == strlen( toFind ) )
            return i - strlen( toFind ) + 1;
    }
    return -1;
}

原创作品，允许转载，转载时无需告知，但请务必以超链接形式标明文章原始出处(https://forec.github.io/2015/09/07/Algorithms-Must/) 、作者信息（Forec）和本声明。

分享到