基础算法简介_基础算法是什么

算法

算法定义：

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

特性

输入: 算法具有0个或多个输入
输出: 算法至少有1个或多个输出
有穷性: 算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成
确定性：算法中的每一步都有确定的含义，不会出现二义性
可行性：算法的每一步都是可行的，也就是说每一步都能够执行有限的次数完

如果评价一个算法：

同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。
时间复杂度：
算法的时间复杂度是指执行算法所需要的计算工作量。一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做。
T(n)=Ο(f(n))
因此，问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。
空间复杂度：
算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。
正确性：
算法的正确性是评价一个算法优劣的最重要的标准。
可读性：
算法的可读性是指一个算法可供人们阅读的容易程度。
健壮性：
健壮性是指一个算法对不合理数据输入的反应能力和处理能力，也称为容错性。

关于时间复杂度：

时间复杂度：由于计算机的性能不同，无法准确统计出算法执行所需要的时间。
因此我们用算法执行的次数来代表算法的时间复杂度，O(公式)，一般忽略常数。

  常见的时间复杂度：
     // O(1)
     printf("%d",i); 
     // O(logn)
     for(int i=n; i>=0; i=i/2)
     {
        printf("%d",i);
     }
     // O(n)
     for(int i=0; i<n; i++)
     {
        printf("%d",i);
     }
     // O(nlogn)
     for(int j=0; j<n; j++)
     {
        for(int i=n; i>=0; i=i/2)
        {
           printf("%d",i);
        }
     }
     // O(n^2)
     for(int i=0; i<n; i++)
     {
        for(int j=0; j<n; j++)
        {
           printf("%d",i*j);
        }
     }
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

查找算法：

顺序查找：

对待查找的数据没有要求，时间复杂度: O(n)

二分查找:

对待查找的数据必须有序，时间复杂度: O(logn)

块查找：

是一种数据处理的思想，不是特定的算法，当数据量过多时，可以先把数据进行分块处理，然后再进行查找，例如英语词典。

哈希查找：

数据 经过哈希函数 计算出数据在哈希表中的位置，然后标记，方便之后的查找，它的时间复试度最快能达到：O(1)。
但是该算法有很大局限性，不适合浮点型、字符串型数据，需要额外的存储空间，空间复杂度高，是一种典型的用空间换取时间的算法。

哈希函数设计方法：
直接定址法：把数据直接当作数组的下标。
数字分析法：分析数据的特点来设计哈希，常用的方法就是找到最大值与最小值,最大值-最小值+1来确定哈希表的长度，数据-最小值访问哈希表。

以下是查找算法的代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define LEN 10
#define swap(a,b) {typeof(a) t=a; a=b; b=t;}
#define show_arr(arr,len) {for(int i=0; i<len; printf("%d ",arr[i++]));printf("\n");}

int order_search(int* arr,int len,int key)
{
	for(int i=0; i<len; i++)
	{
		if(arr[i] == key)
		{
			return i;
		}
	}
	return -1;
}

void sort(int* arr,int len)
{
	for(int i=0; i<len-1; i++)
	{
		for(int j=i+1; j<len; j++)
		{
			if(arr[i] > arr[j])
			{
				swap(arr[i],arr[j]);
			}
		}
	}
}

// 循环二分
int binary_search_for(int* arr,int len,int key)
{
	int l = 0 , r = len-1;
	while(l<=r)
	{
		int p = (l+r)/2;
		if(arr[p] == key) return p;

		if(key < arr[p])
			r = p-1;
		else
			l = p+1;
	}
	return -1;
}

bool hash_search(int* arr,int len,int key)
{
	int max = arr[0] , min = arr[len-1];
	for(int i=1; i<len-1; i++)
	{
		if(arr[i] > max) max = arr[i];
		if(arr[i] < min) min = arr[i];
	}

	// 创建哈希表
	int hash[max-min+1] = {};
	// 标记
	for(int i=0; i<len; i++)
	{
		hash[arr[i]-min]++;
	}
	// 查找
	return hash[key-min];
}

int _binary_search(int* arr,int l,int r,int key)
{
	if(l > r) return -1;

	int p = (l+r)/2;
	if(arr[p] == key)
		return p;
	if(key < arr[p])
		return _binary_search(arr,l,p-1,key);
	else
		return _binary_search(arr,p+1,r,key);
}

// 递归二分
int binary_search(int* arr,int len,int key)
{
	return _binary_search(arr,0,len-1,key);	
}

int main()
{
	int arr[LEN] = {};
	for(int i=0; i<LEN; i++)
	{
		arr[i] = rand()%100;
	}
	printf("order search:%d\n",order_search(arr,LEN,15));
	sort(arr,LEN);
	show_arr(arr,LEN);
	printf("binary search:%d\n",binary_search_for(arr,LEN,100));
}

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

排序算法：

冒泡排序：

数据左右进行比较，把最大的数据交换到最后，特点是该算法对数据的有序性敏感，在排序过程中可以立即发现已经完成。
时间复杂度：O(n),O(n^2)
稳定

选择排序：

假定最开始的位置是最小值并记录下标min，然后与后面的数据进行比较，如果有比以min为下标的数据小的则min的更新，最后如果min的如果发生改变，则交换min与最开始位置的数据，虽然时间复杂度挺高的，但数据交换的次数比较小，因此实际运行速度并不慢(数据交换比数据比较耗时)。
时间复杂度：O(n^2)
不稳定

插入排序：

把数据看作两部分，一分部是有序，把剩余的数据逐个插入进行，适合对已经排序后的数据，新增数据并排序。
时间复杂度：O(n^2)
稳定

希尔排序：

是插入排序的增加版，由于插入排序时，数据移动的速度比较发慢，所以增加了增量的概念，以此来提高排序速度。
时间复杂度：O(nlogn)
不稳定

快速排序：

找到一个标杆，一面从左找比标杆大的数据，找到后把放在标杆的右边，另一个从右边找比标杆小的数据，找到后把放在标杆的左边，最终标杆左边的数据都比它小，右边的数据都比它大，这样就整体有序，然后按同样的方法排序标杆左边的数据和标杆右边的数据。
它的综合性能最高，因此叫快速排序，笔试时考的最多的排序。
时间复杂度：O(nlogn)
不稳定

归并排序：

先一组把数据拆分成单独的个体，然后按从小到大的顺序进行合并，由于需要使用额外的内存空间因此避免的数据交换的耗时，也是一种典型的用空间换取时间的算法，可递归实现也可以循环实现。
时间复杂度：O(nlogn)
稳定

堆排序：

把数据当作完全二叉树，然后树中调整为大根树，然后把根节点交换到最后，然后数量–，然后再调整为大根树，直到数量为1时结束，可递归实现也可以循环实现。
时间复杂度：O(nlogn)
不稳定

计数排序：

找出数据中的最大值和最小值，创建哈希表，把数据-最小值当作数组中的下标访问哈希表并标记数量，然后遍历哈希表，当表中的值大于时，把下标+最小值依次放入数组中，是一种典型的用空间换取时间的算法。
该排序算法理论上速度非常快，但有很大局限性，适合排序整型数据，而且数据的差值不宜过大，否则会非常浪费内存，数据越平均、重复数越多，性价比越高。
时间复杂度：O(n+k);
稳定

桶排序：

把数据根据值，存储到不同桶中，然后再调用其它排序函数，对桶中的数据进行排序，然后再拷贝到数组中，以到降低排序规模来提高排序的时间，是一种典型的用空间换取时间的算法。
时间复杂度：O(n+k);
稳定

基数排序：

是桶排序的具体实现，首先创建10个队列(队列)，然后逆序计算出数据的个十百… 然后压入到对应的队列中，然后再从队列中弹出存储的数组中，当下标为0队列中有len个数据时，排序结束。
时间复杂度：O(n+k);
稳定

以下是依次实现各个排序算法的代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#include "list_queue.h"

#define LEN 15
#define swap(a,b) {typeof(a) t=a; a=b; b=t;}

void show_arr(TYPE* arr,size_t len)
{
	for(int i=0; i<len; printf("%02d ",arr[i++]));
}

typedef void (*SortFP)(TYPE*,size_t);

// 冒泡排序
void bubble_sort(TYPE* arr,size_t len)
{
	bool flag = true;
	for(int i=len-1; i>0 && flag; i--)
	{
		flag = false;
		for(int j=0; j<i; j++)
		{
			if(arr[j] > arr[j+1])
			{
				swap(arr[j],arr[j+1]);
				flag = true;
			}
		}
	}
	show_arr(arr,len);
	printf(":%s\n",__func__);
}

// 选择排序
void select_sort(TYPE* arr,size_t len)
{
	for(int i=0; i<len-1; i++)
	{
		int min = i;
		for(int j=i+1; j<len; j++)
		{
			if(arr[j] < arr[min]) min = j;
		}
		if(i != min) swap(arr[i],arr[min]);
	}
	show_arr(arr,len);
	printf(":%s\n",__func__);
}

// 插入排序
void insert_sort(TYPE* arr,size_t len)
{
	for(int i=1,j=0; i<len; i++)
	{
		int val = arr[i];
		for(j=i; j>0 && arr[j-1] > val; j--)
		{
			arr[j] = arr[j-1];
		}
		if(j != i) arr[j] = val;
	}
	show_arr(arr,len);
	printf(":%s\n",__func__);
}

// 希尔排序
void shell_sort(TYPE* arr,size_t len)
{
	for(int k=len/2; k>0; k/=2)
	{
		for(int i=k,j=0; i<len; i++)
		{
			int val = arr[i];
			for(j=i; j-k>=0 && arr[j-k] > val; j-=k)
			{
				arr[j] = arr[j-k];
			}
			if(j != i) arr[j] = val;
		}
	}
	show_arr(arr,len);
	printf(":%s\n",__func__);
}

void _quick_sort(TYPE* arr,int left,int right)
{
	if(left >= right) return;
	int l=left,r=right;
	TYPE pv = arr[l];
	while(l<r)
	{
		while(l<r && arr[r] >= pv) r--;
		arr[l] = arr[r];
		while(l<r && arr[l] <= pv) l++;
		arr[r] = arr[l];
	}

	arr[l] = pv;
	_quick_sort(arr,left,l-1);
	_quick_sort(arr,l+1,right);
}

void quick_sort(TYPE* arr,size_t len)
{
	_quick_sort(arr,0,len-1);
	show_arr(arr,len);
	printf(":%s\n",__func__);
}


// 合并
void merge(TYPE* arr,TYPE* tmp,int l ,int p , int r)
{
	if(arr[p] < arr[p+1]) return;

	int k = l , i = l , j = p+1;
	while(i<=p && j<=r)
	{
		if(arr[i] < arr[j])
			tmp[k++] = arr[i++];
		else
			tmp[k++] = arr[j++];
	}
	while(i<=p) tmp[k++] = arr[i++];
	while(j<=r) tmp[k++] = arr[j++];
	//while(l<=r) arr[l] = tmp[l++]; 
	memcpy(arr+l,tmp+l,sizeof(TYPE)*(r-l+1));
}

// 拆分
void _merge_sort(TYPE* arr,TYPE* tmp,int l,int r)
{
	if(l >= r) return;
	int p = (l+r)/2;
	_merge_sort(arr,tmp,l,p);
	_merge_sort(arr,tmp,p+1,r);
	merge(arr,tmp,l,p,r);
}

// 归并
void merge_sort(TYPE* arr,size_t len)
{
	TYPE* tmp = malloc(sizeof(TYPE)*len);
	_merge_sort(arr,tmp,0,len-1);
	free(tmp);
	show_arr(arr,len);
	printf(":%s\n",__func__);
}

void merge_for_sort(TYPE* arr,size_t len)
{
	TYPE* tmp = malloc(sizeof(TYPE)*len);
	TYPE* src = arr , *des = tmp;

	for(int s=1; s<len; s*=2)
	{
		for(int l=0; l<len; l+=s*2)
		{
			int r = (l+s*2<len)?l+s*2:len;
			int p = (l+s<len)?l+s:len; 
			int k = l , i = l , j = p;
			while(i<p && j<r)
			{
				if(src[i] < src[j])
					des[k++] = src[i++];
				else
					des[k++] = src[j++];
			}
			while(i<p) des[k++] = src[i++];
			while(j<r) des[k++] = src[j++];
		}
		swap(des,src);
	}
	if(src != arr) memcpy(arr,src,sizeof(TYPE)*len);
	free(tmp);

	show_arr(arr,len);
	printf(":%s\n",__func__);
}

void create_heap(TYPE* arr,int root,size_t len)
{
	if(root >= len) return;
	int left = root*2+1 , right = root*2+2;
	create_heap(arr,left,len);
	create_heap(arr,right,len);
	if(right < len && arr[left] < arr[right])
		swap(arr[left],arr[right]);
	if(left < len && arr[root] < arr[left])
		swap(arr[root],arr[left]);
}

void heap_sort(TYPE* arr,size_t len)
{
	create_heap(arr,0,len);	
	for(int i=len-1; i>0; i--)
	{
		swap(arr[0],arr[i]);
		create_heap(arr,0,i);
	}

	show_arr(arr,len);
	printf(":%s\n",__func__);
}

void heap_for_sort(TYPE* arr,size_t len)
{
	for(int i=len-1; i>0; i--)
	{
		int p = (i+1)/2-1;
		if(arr[i] > arr[p]) swap(arr[i],arr[p]);
	}
	show_arr(arr,len);
	printf("\n");

	for(int i=len-1; i>0; i--)
	{
		swap(arr[0],arr[i]);
		for(int j=0; j<i; j++)
		{
			if(j*2+2<i && arr[j*2+1]<arr[j*2+2])
			{
				swap(arr[j*2+1],arr[j*2+2])
			}
			if(j*2+1<i && arr[j]<arr[j*2+1])
			{
				swap(arr[j],arr[j*2+1])
			}
		}
	}
	show_arr(arr,len);
	printf(":%s\n",__func__);
}

void count_sort(TYPE* arr,size_t len)
{
	TYPE min = arr[0] , max = arr[len-1];
	for(int i=0; i<len; i++)
	{
		if(arr[i] < min) min = arr[i];
		if(arr[i] > max) max = arr[i];
	}
	TYPE* tmp = calloc(sizeof(TYPE),max-min+1);
	for(int i=0; i<len; i++)
	{
		tmp[arr[i]-min]++;
	}
	for(int i=0,j=0; i<=max-min; i++)
	{
		while(tmp[i]--)
		{
			arr[j++] = i+min;
		}
	}
	free(tmp);
	show_arr(arr,len);
	printf(":%s\n",__func__);
}

void _bucket_sort(TYPE* arr,size_t len,int cnt,TYPE range)
{
	TYPE* bucket[cnt],*bucketed[cnt];
	for(int i=0; i<cnt; i++)
	{
		bucket[i] = malloc(sizeof(TYPE)*len);
		bucketed[i] = bucket[i];
	}

	for(int i=0; i<len; i++)
	{
		for(int j=0; j<cnt; j++)
		{
			if(range*j<=arr[i] && arr[i]<range*(j+1))
			{
				*(bucketed[j]) = arr[i];
				bucketed[j]++;
			}
		}
	}
	for(int i=0; i<cnt; i++)
	{
		int size = bucketed[i]-bucket[i];
		if(size > 1) count_sort(bucket[i],size);
		memcpy(arr,bucket[i],sizeof(TYPE)*size);
		arr += size;
		free(bucket[i]);
	}
}

void bucket_sort(TYPE* arr,size_t len)
{
	_bucket_sort(arr,len,4,25);	
	show_arr(arr,len);
	printf(":%s\n",__func__);
}

void radix_sort(TYPE* arr,size_t len)
{
	ListQueue* queue[10] = {};
	for(int i=0; i<10; i++)
	{
		queue[i] = create_list_queue();
	}

	for(int i=1; i<=10&&size_list_queue(queue[0])<len; i++)
	{
		int mod = pow(10,i);
		int div = mod / 10;

		for(int j=0; j<len; j++)
		{
			int index = arr[j]%mod/div;
			push_list_queue(queue[index],arr[j]);
		}
		int k = 0;
		for(int j=0; j<10; j++)
		{
			while(!empty_list_queue(queue[j]))
			{
				arr[k++] = head_list_queue(queue[j]);
				pop_list_queue(queue[j]);
			}
		}
	}
	for(int i=0; i<10; i++)
	{
		destory_list_queue(queue[i]);
	}

	show_arr(arr,len);
	printf(":%s\n",__func__);
}

int main()
{
	TYPE arr[LEN] = {};
	SortFP sort[] = {bubble_sort,select_sort,insert_sort,shell_sort,quick_sort,merge_sort,merge_for_sort,heap_sort,heap_for_sort,count_sort,bucket_sort,radix_sort};
	for(int i=0; i<sizeof(sort)/sizeof(sort[0]); i++)
	{
		for(int j=0; j<LEN; j++)
		{
			arr[j] = rand()%100;
			printf("---");
		}
		printf("\n");
		show_arr(arr,LEN);
		printf(":排序前\n");
		sort[i](arr,LEN);
	}
}
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354