排序与KMP

136 阅读 0 评论 90 点赞

我是靠谱客的博主娇气信封，这篇文章主要介绍排序与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
27
28
int shell_sort(int *data, int length) {
	if (!data || lenth <= 1) {
		return 0
	}
	int gap = 0;
	int i = 0, j = 0;
	int temp;

	for (gap = length / 2;gap >= 1; gap /= 2) {

		for (i = gap;i < length;i ++) {

			temp = data[i];
			for (j = i-gap;j >= 0 && temp < data[j];j = j - gap) {

				data[j+gap] = data[j];
				
			}
			data[j+gap] = temp;
		}

	}

	return 0;
}

复制代码

1
2
3
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

希尔排序
最好的情况是有序的，不需要换位置，时间复杂度是O(N)
最坏的情况的是逆序的，所有的下标都要换位置，时间复杂度是O(N^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
31
32
33
34
35
36
37
38
39
40
41
42
43
void merge(int *data, int *temp, int start, int middle, int end) {
	
	int i = start, j = middle+1, k = start;

	while (i <= middle && j <= end) {
		if (data[i] > data[j]) {
			temp[k++] = data[j++];
		} else {
			temp[k++] = data[i++];
		}
	}

	while (i <= middle) {
		temp[k++] = data[i++];
	}

	while (j <= end) {
		temp[k++] = data[j++];
	}

	for (i = start;i <= end;i ++) {
		data[i] = temp[i];
	}
}


int merge_sort(int *data, int *temp, int start, int end) {
	if (!data) {
		return 0;
	}
	
	int middle;
	if (start < end) {
		middle = start + (end - start) / 2;

		merge_sort(data, temp, start, middle);
		merge_sort(data, temp, middle+1, end);

		merge(data, temp, start, middle, end);
	}

}

快速排序

复制代码

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
void sort(int *data, int left, int right) {

	if (!data|| left >= right) return ;

	int i = left;
	int j = right;
	int key = data[left];

	while (i < j) {

		while (i < j && key <= data[j]) {
			j --;
		}
		data[i] = data[j];

		while (i < j && key >= data[i]) {
			i ++;
		}
		data[j] = data[i];
	}

	data[i] = key;

	sort(data, left, i - 1);
	sort(data, i + 1, right);

}

int quick_sort(int *data, int length) {

	sort(data, 0, length-1);

}

KMP算法

题目：
写一个在一个字符串(n)中寻找一个子串(m)第一个位置的函数。
10+G的日志中，如何快速地查找关键字？

用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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
void make_next(const char *pattern, int *next) {
	int q, k;
	int m = strlen(pattern);

	next[0] = 0;
	for (q = 1,k = 0;q < m; q ++) {

		while (k > 0 && pattern[q] != pattern[k])
			k = next[k-1];

		if (pattern[q] == pattern[k]) {
			k ++;
		}

		next[q] = k;

	}
}

int kmp(const char *text, const char *pattern, int *next) {

	int n = strlen(text);
	int m = strlen(pattern);

	make_next(pattern, next);
	
	int i, q;
	for (i = 0, q = 0;i < n;i ++) {

		while (q > 0 && pattern[q] != text[i]) {
			q = next[q-1];
		}

		if (pattern[q] == text[i]) {
			q ++;
		}

		if (q == m) {
			//printf("Pattern occurs with shift: %dn", (i-m+1));
			break;
		}
	}

	return i-q+1;
}

题目：
微软面试题2010年：
在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数
大于后面的数，那么它们就称为一个逆序数对。一个排列中逆序的总数就称为这个排列的
逆序数。如{2，4，3，1}中，2和1，4和3，4和1，3和1是逆序数对，因此整个数组的逆序数
对个数为4，现在给定一数组，要求统计出该数组的逆序数对个数

复制代码

void Merge(int *arr, int LeftStart, int middle, int RightEnd, int *temp,int &count){
	
	int LeftEnd = middle;
	int start = LeftStart;
	int RightStart = middle + 1;
	
	int i = 0;

while (LeftStart <= LeftEnd && RightStart <= RightEnd){

if (arr[LeftStart] > arr[RightStart]){ 
			//如果leftStart为下标的数已经大于RightStart下标的数了，那么肯定LeftStart后面的数都大于RightStart
			/*
			for (int k = LeftStart; k <= LeftEnd; k++){
				cout << arr[k] << " "<<arr[RightStart] << endl;
			}
			*/
			count += LeftEnd - LeftStart + 1;
			temp[i++] = arr[RightStart++];
		}
		else {
			temp[i++] = arr[LeftStart++];
		}

}

while (LeftStart <= LeftEnd){
		temp[i++] = arr[LeftStart++];
	}

while (RightStart <= RightEnd){
		temp[i++] = arr[RightStart++];
	}

for (int j = 0; j < i; j++){
		arr[start + j] = temp[j];
	}

}

void MergeSort(int *arr, int left, int right, int *temp,int &count){
	if (left == right){
		return;
	}
	int middle = left + ((right - left) >> 1);  //相当于（left+right）/2 ,不过它有避免了数据溢出
	MergeSort(arr, left, middle, temp,count);
	MergeSort(arr, middle + 1, right, temp, count);
	Merge(arr, left, middle, right, temp, count);
}

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
void Merge(int *arr, int LeftStart, int middle, int RightEnd, int *temp,int &count){
	
	int LeftEnd = middle;
	int start = LeftStart;
	int RightStart = middle + 1;
	
	int i = 0;

	while (LeftStart <= LeftEnd && RightStart <= RightEnd){

		if (arr[LeftStart] > arr[RightStart]){ 
			//如果leftStart为下标的数已经大于RightStart下标的数了，那么肯定LeftStart后面的数都大于RightStart
			/*
			for (int k = LeftStart; k <= LeftEnd; k++){
				cout << arr[k] << " "<<arr[RightStart] << endl;
			}
			*/
			count += LeftEnd - LeftStart + 1;
			temp[i++] = arr[RightStart++];
		}
		else {
			temp[i++] = arr[LeftStart++];
		}

		
	}

	while (LeftStart <= LeftEnd){
		temp[i++] = arr[LeftStart++];
	}

	while (RightStart <= RightEnd){
		temp[i++] = arr[RightStart++];
	}

	for (int j = 0; j < i; j++){
		arr[start + j] = temp[j];
	}

}

void MergeSort(int *arr, int left, int right, int *temp,int &count){
	if (left == right){
		return;
	}
	int middle = left + ((right - left) >> 1);  //相当于（left+right）/2 ,不过它有避免了数据溢出
	MergeSort(arr, left, middle, temp,count);
	MergeSort(arr, middle + 1, right, temp, count);
	Merge(arr, left, middle, right, temp, count);
}