常见的九种排序算法（C语言实现）_图的遍历和排序算法及实现 c语言

排序(Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。

算法分类

1. 比较排序
   通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(NlogN)，因此也称为非线性时间比较类排序。

   选择排序

   冒泡排序

   插入排序

   希尔排序

   堆排序

   归并排序

   快速排序

2. 非比较排序
   不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

   计数排序

   基数排序

   桶排序

   ---

   评价标准

   （1）时间复杂度：即从序列的初始状态到经过排序算法的变换移位等操作变到最终排序好的结果状态的过程所花费的时间度量。

   （2）空间复杂度：就是从序列的初始状态经过排序移位变换的过程一直到最终的状态所花费的空间开销。

   （3）使用场景：对于特定的场景使用更加高效稳定的排序算法。

   （4）稳定性：即是否会改变排序前后两个相等元素的相对位置，不管是在时间或空间上都要考虑的问题。

   
   

   排序算法比较

3. N：数据规模
4. k：桶的个数

各种排序算法源代码及图解

1.选择排序(Selection Sort)

选择排序是一种简单直观的排序算法，其原理是首先在未排序序列中找到最小元素,存放到排列序列的起始位置,然后在剩余未排序元素中继续寻找最小元素,然后放到已经排好序序列的末尾,以此类推,直到所有元素均排序完毕。

步骤:

1.将要排序的序列划分为未排序序列和已排序序列

2.遍历未排序的序列，找到最小的元素，定义为min，放到已排序序列的末尾

代码实现:

void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void SelectionSort(int* arr, int n)
{
	int begin = 0;
	while (begin < n)
	{
		int mini = begin;//定义最小值的位置
		//遍历未排序序列，找到其中最小值的位置
		for (int i = begin + 1; i < n; i++)
		{
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
		}
		swap(&arr[begin], &arr[mini]);
		begin++;
	}
}

int main()
{
	int arr[] = { 5,11,7,2,3,17,6,8,10 };
	int size = sizeof(arr) / sizeof(arr[0]);
	SelectionSort(arr, size);
	return 0;
}
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

当然也可以从头和尾同时开始，同时寻找最小值和最大值，分别存放到头和尾（这样能够稍微节省一点时间…）

void SelectionSort(int* arr, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int mini = begin;
		int maxi = begin;
		for (int i = begin; i <= end; i++)
		{
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
		}
		swap(&arr[begin], &arr[mini]);
		if (begin == maxi)maxi = mini;
		swap(&arr[maxi], &arr[end]);
		begin++;
		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

---

2.冒泡排序(Bubble Sort)

冒泡排序是一种简单的排序算法，其原理是通过重复走过要排序的数组，每一次比较两个相邻元素的大小，如果后一个元素比前一个元素小就交换过来，最终完成排序，这种算法的命名也是由最小的元素总是会慢慢从最后“浮”到前面来而得名(每次从无序区间取一个数去无序区间遍历)。

步骤：

1.从第一组的两个相邻元素开始比较，依次往后交换

2.每经历一次排序，最大元素就会被放到最后稳定下来，下一次排序时就不会去移动它的位置

3.直到所有元素都稳定下来，排序完成

代码实现：

void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void BubbleSort(int* arr, int n)
{
	//排序的趟数：n-1（n为元素个数）
	for (int i = 0; i < n - 1; i++)
	{
		//定义变量exchange，若exchange为0，则表明排序已完成，则直接跳出循环，避免重复遍历序列
		int exchange = 0;
		//每一趟的比较次数：n-i
		for (int j = 0; j < n - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				swap(&arr[j], &arr[j + 1]);
				exchange = 1;
			}
		}
		if (exchange == 0)break;
	}
}

int main()
{
	int arr[] = { 5,11,7,2,3,17,6,8,10 };
	int size = sizeof(arr) / sizeof(arr[0]);
	BubbleSort(arr, size);
	return 0;
}
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

---

3.插入排序(Insertion Sort)

插入排序是一种简单直观的排序算法，其原理是通过构建有序序列，对于为排序序列中的数据，在有序序列中从后往前遍历，找到合适的位置插入(每次从无序区间取一个数到有序区间去遍历,找到插入的位置)。

步骤:

1.从第一个元素开始，认为其已被排序

2.取出下一个元素，在已排序序列中从后往前遍历

3.如果该元素(已排序)大于取出的元素，则将该元素后移一位

4.重复3步骤

5.后移完成后，将取出的元素插入该位置

6.重复2-5步骤

代码实现:

void InsertSort(int* arr, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;//定义end指向已排序序列的尾部
		int tmp = arr[end + 1];//取出未排序序列中的元素
		while (end >= 0)
		{
			//遍历已排序序列
			if (arr[end] > tmp)
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
				break;
		}
		arr[end + 1] = tmp;//遍历结束后，end会指向已排序序列中小于取出元素的元素位置，因此取出元素的位置为end+1
	}
}

int main()
{
	int arr[] = { 5,11,7,2,3,17,6,8,10 };
	int size = sizeof(arr) / sizeof(arr[0]);
	InsertionSort(arr, size);
	return 0;
}
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

---

4.希尔排序(Shell Sort)

希尔排序是插入排序的改进算法，与上述排序不同的是，其平均时间复杂度为O(N^1.3)，大大提高了效率，其原理是在插入排序的基础上，对要排序的序列进行预排序，也称之为分组插排，分组越多，序列越接近有序。

它将整个序列划分为若干组，对每一组单独使用插入排序，之后减小间隔重复多次后，就能够让序列更加接近于有序。

代码实现:

void ShellSort(int* arr,int n)
{
	//定义gap变量，表示间隔，将序列划分为若干组(gap为1时即为插入排序)
	int gap = n;
	while (gap > 1)
	{
		//或者让 gap = gap / 2
		gap = gap / 3 + 1;//每个组排好序后，减小间隔
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
					break;
			}
			arr[end + gap] = tmp;
		}
	}
}

int main()
{
	int arr[] = { 5,11,7,2,3,17,6,8,10 };
	int size = sizeof(arr) / sizeof(arr[0]);
	ShellSort(arr, size);
	return 0;
}
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

---

5.堆排序(Heap Sort)

堆排序时利用堆这种数据结构所设计的一种排序算法，堆积是一种近似于完全二叉树的结构，分为大堆和小堆，其性质满足所有的子节点的键值或索引小于(大于)父节点。

步骤:

1.建立大堆，此时该堆初始为无序区

2.取出堆顶元素，放到无序区的最后面，此时得到新的无序区和有序区，在新的无序区中重新向下调整，然后每次把取出的堆顶元素放到无序区的最后面

每次调整后，将最大元素(即堆顶元素)放到end位置，再在[0,end-1]序列中向下调整，之后再将最大元素放到end-1的位置…

代码实现:

void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

//向下调整算法(建大堆)
void AdjustDown(int* arr, int n, int root)
{
	int parent = root;
	int child = parent * 2 + 1;//完全二叉树的性质: 左子节点索引 = 父节点索引 * 2 + 1
	while (child < n)
	{
		//假设较大的子节点为左子节点，否则交换
		if (child + 1 < n && arr[child + 1] > arr[child])
		{
			child += 1;
		}
		if (arr[child] > arr[parent])
		{
			swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}

void HeapSort(int* arr,int n)
{
	//建堆(排升序建大堆，排降序建小堆)
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)//(n - 1 - 1) / 2 即为最后一个节点的父节点
	{
		AdjustDown(arr, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		swap(&arr[0], &arr[end]);
		//在[0,end-1]序列中向下调整
		AdjustDown(arr, end, 0);
		end--;
	}
}

int main()
{
	int arr[] = { 5,11,7,2,3,17,6,8,10 };
	int size = sizeof(arr) / sizeof(arr[0]);
	HeapSort(arr, size);
	return 0;
}
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

---

6.归并排序(Merge Sort)

归并排序是建立在归并算法上的一个高效排序算法，其原理是将**两个有序的子序列合并为新的完整有序序列**。

步骤:

1.将序列划分为两个长度为n/2的子序列

2.对两个子序列分别进行归并排序

3.最后将排序好的两个有序子序列合并为完整有序的序列

3 3 5 6和1 2 7 9分别为两个有序子序列，对这两个有序子序列进行合并，这就是归并排序的核心。

代码实现(递归):

void _MergeSort(int* arr, int left, int right, int* tmp)
{
	//左右指针分别指向序列的头和尾
	if (left >= right)return;//递归结束条件:左右指针相遇
	int mid = (left + right) >> 1;//相当于/2，位运算会快一点

	//将序列分为左右两个子序列，分别对其进行归并排序
	_MergeSort(arr, left, mid, tmp);
	_MergeSort(arr, mid + 1, right, tmp);

	//合并两个有序的子序列
	//用两个头指针和两个尾指针分别指向两个子序列的头和尾
	int begin1 = left;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = right;

	//index指向tmp的首元素，tmp中每增添一个元素，index++
	int index = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			tmp[index++] = arr[begin1++];
		}
		else
		{
			tmp[index++] = arr[begin2++];
		}
	}

	//当其中一个子序列中所有元素存放完时，将另一个子序列中剩下的有序元素存放到tmp中
	while (begin1 <= end1)
	{
		tmp[index++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[index++] = arr[begin2++];
	}

	for (int i = left; i <= right; i++)
	{
		arr[i] = tmp[i];
	}
}

void MergeSort(int* arr, int n)
{
	//动态开辟长度为n的数组用来合并有序子序列
	int* tmp = (int*)malloc(sizeof(int) * n);

	_MergeSort(arr, 0, n - 1, tmp);//对整个序列进行归并排序

	free(tmp);//释放tmp
}

int main()
{
	int arr[] = { 5,11,7,2,3,17,6,8,10 };
	int size = sizeof(arr) / sizeof(arr[0]);
	MergeSort(arr, size);
	return 0;
}
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

---

7.快速排序

快速排序顾名思义，其特点就是“快”，其基本思想是在序列中选出一个基准(pivot,通常选用序列最左边或最右边的元素作为基准值)，将序列中所有小于(包括等于)该基准值的元素放到基准值的左边，将序列中所有大于(包括等于)该基准值的元素放到基准值的右边，对基准值左右的子序列重复此步骤，直到子序列中的元素只有一个或没有时，排序结束。

步骤:

1.选取基准(pivot)

2.找到序列中所有小于(包括等于)和所有大于(包括等于)基准值的元素，将其放到基准值的左边和右边

3.对形成的两个新的子序列[left,pivot-1],[pivot+1,right]分别进行排序

对于取基准值有常见的三种方法:

1.通常取序列最左边或最右边的元素，有时也会取中间元素

2.随机值法

3.三数取中法，将返回值取到的值与序列最左边或最右边的元素交换

对于排序有常见的三种方法:

1.挖坑法

2.Hoare法(左右指针法)

3.前后指针法

代码实现(递归):

void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

/*快速排序对数据是敏感的
如果序列是非常杂乱无章的状态，快速排序的效率是O(NlogN)
但如果序列为有序，那么效率会退化为O(N^2)
这个时候就要用到三数取中，对算法进行优化*/

//三数取中法
//对序列首，中，尾三个元素取中间大小的元素作为基准
int GetMidIndex(int* arr, int left, int right)
{
	int mid = (left + right) >> 1;
	if (arr[left] < arr[mid])
	{
		if (arr[mid] < arr[right])
		{
			return mid;
		}
		else if (arr[left] > arr[right])
		{
			return left;
		}
		else
			return right;
	}
	else
	{
		if (arr[mid] > arr[right])
		{
			return mid;
		}
		else if (arr[left] < arr[right])
		{
			return left;
		}
		else
			return right;
	}
}

//挖坑法
int PartSort1(int* arr, int left, int right)
{
	//三数取中，将返回值与基准值交换
	int middle = GetMidIndex(arr, left, right);
	swap(&arr[middle], &arr[left]);

	int begin = left;
	int end = right;

	int pivot = begin;//pivot就是"坑"
	int key = arr[begin];//取基准值
	while (begin < end)
	{
		//尾指针向左移动，寻找小于key的元素
		while (begin < end && arr[end] >= key)
		{
			end--;
		}
		arr[pivot] = arr[end];//找到之后，把该元素放到"坑"里
		pivot = end;//此时尾指针指向的位置作为新的坑
		
		//头指针向右移动，寻找大于key的元素
		while (begin < end && arr[begin] <= key)
		{
			begin++;
		}
		arr[pivot] = arr[begin];//找到之后，把该元素放到"坑"里
		pivot = begin;//此时头指针指向的位置作为新的坑
	}
	
	//序列遍历完成后，将key放到最后的"坑"里
	pivot = begin;
	arr[pivot] = key;
	return pivot;//返回"坑"的位置，以便于下一次对左右子序列的排序
}

//Hoare法(左右指针法)
int PartSort2(int* arr, int left, int right)
{
	//三数取中，将返回值与基准值交换
	int middle = GetMidIndex(arr, left, right);
	swap(&arr[middle], &arr[left]);

	int begin = left;
	int end = right;
	int key = begin;//选取基准

	/*
	  左右指针同时移动
	  当右指针遇到小于key的元素，左指针遇到大于key的元素就停下
	  然后交换两个元素
	*/ 
	while (begin < end)
	{
		while (begin < end && arr[end]>=arr[key])
		{
			end--;
		}
		while (begin < end && arr[begin] <= arr[key])
		{
			begin++;
		}
		swap(&arr[begin], &arr[end]);
	}

	swap(&arr[begin], &arr[key]);
	return begin;
}

//前后指针法
int PartSort3(int* arr, int left, int right)
{
	//三数取中，将返回值与基准值交换
	int middle = GetMidIndex(arr, left, right);
	swap(&arr[middle], &arr[left]);

	int cur = left + 1;
	int prev = left;
	int key = left;//选取基准

	while (cur <= right)//当cur遍历完就停下
	{
		/*
		  cur寻找小于key的元素，
		  当cur找到了小于key的元素就++prev，交换cur和prev指向的元素
		  但为了避免自己与自己交换，加了判断条件prev!=cur
		  当cur找到了大于key的元素，++prev就不会被执行
		*/
		if (arr[cur] < arr[key] && ++prev != cur)
		{
			swap(&arr[prev], &arr[cur]);
		}
		cur++;
	}
	//遍历完成后，prev的左边都是小于key的元素，prev的右边都是大于key的元素
	swap(&arr[key], &arr[prev]);
	return prev;
}

void QuickSort(int* arr, int left , int right)
{
	if (left >= right)return;//递归结束条件

	int pivot = PartSort1(arr, left, right);
	//int pivot = PartSort2(arr, left, right);
	//int pivot = PartSort3(arr, left, right);

	//对形成的两个新的子序列[left, pivot - 1], [pivot + 1, right]分别进行排序
	QuickSort(arr, left, pivot - 1);
	QuickSort(arr, pivot + 1, right);

	/*
	若序列中元素个数小于等于10个，对该序列进行插排，能够提高算法的效率
	if (pivot - 1 - left > 10)
	{
		QuickSort(arr, left, pivot - 1);
	}
	else
	{
		InsertionSort(arr + left, pivot - left);
	}
	if (right - pivot - 1 > 10)
	{
		QuickSort(arr, pivot + 1, right);
	}
	else
	{
		InsertionSort(arr + pivot + 1, right - pivot);
	}
	*/
}

int main()
{
	int arr[] = { 5,11,7,2,3,17,6,8,10 };
	int size = sizeof(arr) / sizeof(arr[0]);
	QuickSort(arr, 0, size-1);
	return 0;
}
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

---

8.计数排序(Count Sort)

计数排序作为一种非比较排序，属于桶排序的一种，以线性时间运行，效率能够达到O(N+k),但缺点是只能对整数进行排序，其原理是将相同的数据放到一个"桶"里，最后将排序好的"桶"中的所有元素依次"倒"出来。

步骤:

1.遍历整个序列，将元素大小i作为新开辟数组中的下标，对数组数组中该位置的值进行+1的操作

2.遍历完后，将开辟数组中的元素依次输出

代码实现:

void CountSort(int* arr, int n)
{
	/*
	  找到序列中最大元素和最小元素，其差值+1即为序列中元素种类的个数
	  选取相对差值而不是绝对差值，能够避免数组开辟过大，导致内存空间浪费，同时也能解决负数的问题
	*/
	int max = arr[0];
	int min = arr[0];
	for (int i = 0; i < n; i++)
	{
		if (arr[i] > max)max = arr[i];
		if (arr[i] < min)min = arr[i];
	}
	int range = max - min + 1;

	int* count = (int*)calloc(range, sizeof(int));//作为计数
	int* result = (int*)calloc(n, sizeof(int));//用来存放答案
	if (count != NULL && result != NULL)
	{
		
		//遍历序列
		for (int i = 0; i < n; i++)
		{
			//下标为该元素减去min的相对差值
			count[arr[i] - min]++;
		}
		
		/*(不稳定)
			int j = 0;
			for (int i = 0; i < range; i++)
			{
				while (count[i]-- > 0)
				{
					result[j++] = i + min;
				}
			}
		*/
		
		//为了使排序稳定，需要将序列从后往前输出
		for (int i = 1; i < range; i++)
		{
			count[i] += count[i - 1];
		}
		/*
		  例如arr为  1  1  2  3  4  2  2  3  2  1  3  4
		  则count[0]   count[1]   count[2]   count[3]
		      3          4          3          2
		  此时需要把每一项的前项进行累加，以便于从后往前输出时得到该元素个数
		  累加后
			count[0]   count[1]   count[2]   count[3]
			  3          7          10         12
		  累加后，count中每一个值对应了该下标在result数组中最后一个的位置
		  如arr中最后一个1对应result第3个位置，最后一个2对应第7个位置
		  最后一个3对应第10个位置，最后一个4对应第12个位置
		  这样就能实现将arr从后往前输出到result中，达到排序前后相同元素的相对位置不变的目的
		*/
		for (int i = n - 1; i >= 0; i--)
		{
			result[--count[arr[i]-min]] = arr[i];
		}
		
		//将result中的数据拷贝到arr中
		for (int i = 0; i < n; i++)
		{
			arr[i] = result[i];
		}
	}
	
	free(count);
	free(result);
}

int main()
{
	int arr[] = { 5,11,7,2,3,17,6,8,10 };
	int size = sizeof(arr) / sizeof(arr[0]);
	CountSort(arr, size);
	return 0;
}
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

---

9.基数排序(Radix Sort)

基数排序也是一种非比较排序，同样属于桶排序的一种，与计数排序大致思路相同，不同点是，它通过分割序列中每个元素的同一权重位，用该权重位上的数实现对元素的排序。

步骤:

1.分割所有元素的同一权重位，对其进行计数排序

2.排序后继续分割、排序，直到不能分割为止

代码实现:

void RadixSort(int* arr, int n)
{
	//找出序列中的最大值，用来判断最高权重位，就能确定循环次数
	//找出序列中的最小值，先将序列中所有的元素加上该值得绝对值，最后还原，就能解决负数问题
	int max = arr[0];
	int min = arr[0];
	int division = 1;//作为分割每个元素的同一权重位的标准
	for (int i = 0; i < n; i++)
	{
		if (arr[i] > max)max = arr[i];
		if (arr[i] < min)min = arr[i];
	}

	for (int i = 0; i < n; i++)
	{
		arr[i] += abs(min);
	}

	int* result = (int*)calloc(n, sizeof(int));
	if (result != NULL)
	{
		while (max / division > 0)
		{
			//与计数排序相同
			int count[10] = { 0 };
			for (int i = 0; i < n; i++)
			{
				// / division % 10就能的到每个元素的同一权重位
				count[arr[i] / division % 10]++;
			}
			for (int i = 1; i < 10; i++)
			{
				count[i] += count[i - 1];
			}
			for (int i = n - 1; i >= 0; i--)
			{
				result[--count[arr[i] / division % 10]] = arr[i];
			}
			for (int i = 0; i < n; i++)
			{
				arr[i] = result[i];
			}
			division *= 10;
		}
	}

	free(result);

	//还原数据
	for (int i = 0; i < n; i++)
	{
		arr[i] -= abs(min);
	}
}

int main()
{
	int arr[] = { 5,11,7,2,3,17,6,8,10 };
	int size = sizeof(arr) / sizeof(arr[0]);
	RadixSort(arr, size);
	return 0;
}
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