算法--排序算法总结与实现笔记

Alt text

冒泡排序

  冒泡排序是最基础的排序算法,冒泡排序不断对比两个相邻的元素大小,将顺序错误的值交换。将大的值交换到数组的底部,过程像冒泡一样。排序算法时间复杂度是O(n^2)

1
2
3
4
比较相邻的元素。如果第一个比第二个大,就交换他们两个。
对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤,除了最后一个。
持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
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
# include<stdio.h>
/*冒泡排序*/
void bubble_sort(int *list)
{
int length= 10; //数组长度
int tempNum;
for(int index = 0;index < length;index++)
{
for(int i = 1;i < length- index;i++)
{
if(list[i-1] > list[i]){
tempNum = list[i-1];
list[i-1] = list[i];
list[i] = tempNum;
}
}
}
}
int main()
{
int list[10] = {12,43,56,54,23,10,3,65,84,2};
bubble_sort(list);
for(int i = 0;i < 10;i++)
{
printf("%d\t",list[i]);
}
return 0;
}

Alt text

选择排序

  选择排序是一种不稳定的排序。选择排序是将数组中最小(或最大)的值找出来,放到第一个位置上,然后在剩余的元素中找到最小(或最大)的值,放到第二个位置上。选择排序时间复杂度是O(n^2),最好时间复杂度也是O(n^2)。
  假如有数组[5,5,3],使用选择排序进行排序,最小值3会和第一个5互换位置,这就导致第一个5挪到第二5后面,所以选择排序是不稳定的排序。

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
# include<stdio.h>
/*选择排序*/
void selection_sort(int *list)
{
int length= 10; //数组长度
int tempNum;
for(int index = 0;index < length;index++)
{
for(int i = index;i < length;i++)
{
if(list[index] > list[i]){
tempNum = list[index];
list[index] = list[i];
list[i] = tempNum;
}
}
}
}
int main()
{
int list[10] = {12,43,56,54,23,10,3,65,84,2};
selection_sort(list);
for(int i = 0;i < 10;i++)
{
printf("%d\t",list[i]);
}
return 0;
}

Alt text

直接插入排序

  直接插入排序是将待排序的值,插入到前面已经排序好的值中,直到所有的值插入完。数组中的第一个值默认已经排序。直接插入排序的时间复杂度是O(n^2 )

1
2
3
4
5
6
从第一个元素开始,该元素可以认为已经被排序
取出下一个元素,在已经排序的元素序列中从后向前扫描
如果该元素(已排序)大于新元素,将该元素移到下一位置
重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2~5
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
# include<stdio.h>
/*插入排序*/
void insert_sort(int *list)
{
int length= 10; //数组长度
int key; //存放要插入的值
for(int index = 1;index < length;index++) //这里是从1开始遍历,因为默认0是已经排序完的
{
key = list[index];
for(int i = index-1;i >= 0;i--)
{
if(list[i] > key){
list[i+1] = list[i];
list[i] = key;
}
}
}
}
int main()
{
int list[10] = {12,43,56,54,23,10,3,65,84,2};
insert_sort(list);
for(int i = 0;i < 10;i++)
{
printf("%d\t",list[i]);
}
return 0;
}

Alt text

折半插入排序(二分插入排序)

  折半插入是对直接插入的优化。由于直接插入算法中,需要将排序的元素依次插入前面排好序的元素中。折半查找减少了比较的次数,但是没有减少移动次数,所以算法时间复杂度还是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
# include<stdio.h>
/*插入排序*/
void binary_insertion_sort(int *list)
{
int length= 10; //数组长度
int key; //存放要插入的值
for(int i = 1;i < length;i++) //这里是从1开始遍历,因为默认0是已经排序完的
{
key = list[i];
int left = 0;
int right = i - 1;
while(left <= right)
{
int mid = left + (right - left) / 2;
if(key < list[mid]){
right = mid - 1;
}else{
left = mid + 1;
}
}
/*因为要排序的元素前面的元素是有序的,所以必须将left后面的元素向后移动位置
这样才能空出来位置将要排序的元素插入进去。
*/
for(int j = i-1;j >= left;j--)
{
list[j+1] = list[j];
}
list[left] = key;
}
}
int main()
{
int list[10] = {12,43,56,54,23,10,3,65,84,2};
binary_insertion_sort(list);
for(int i = 0;i < 10;i++)
{
printf("%d\t",list[i]);
}
return 0;
}

希尔排序

希尔排序也是插入排序的一种,也称为缩小增量排序,是一种不稳定排序。
以下面的数据为例 {12,43,56,54,23,10,3,65,84,2},整个数据数量为10,,设置步长为5。则数据可以排列为:
12 43 56 54 23
10 3 65 84 2
然后对每一列排序,变为:
10 3 56 54 2
12 43 65 84 23
然后将步长改变为2,将上面的数据重新排列为:
10 3
56 54
2 12
43 65
84 23
然后对上面的数据按列排序,最后,将步长改为1,再按照列排序。即完成排序过程。

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
# include<stdio.h>
/*希尔排序*/
void binary_insertion_sort(int *list)
{
int length = 10;
int dist = length / 2; //步长
int key;
int j;
while(dist > 0)
{
for(int i=dist;i < length;i++)//从第二排,第一个元素开始遍历,知道最后一个
{
key = list[i];
j = i; //i是该元素原来的位置,j是对比过后,改变的地址
while(j >= dist && key < list[j-dist])//找到前面的同列中是不是有小的,遍历一遍
{
list[j] = list[j-dist];
j -= dist;
}
list[j] = key;
}
dist /= 2; //增量减半
}
}
int main()
{
int list[10] = {12,43,56,54,23,10,3,65,84,2};
binary_insertion_sort(list);
for(int i = 0;i < 10;i++)
{
printf("%d\t",list[i]);
}
return 0;
}

Alt text

归并排序

  归并排序是将两个已经排序好的数组合并,使用分治思想。我这里只实现了对数组的合并,可以使用递归对数组排序,使用2路归并算法。算法时间内复杂度为O(nlgn)。

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
# include<stdio.h>
/*归并排序*/
void merge_sort(int *list,int *list1,int *list2)
{
int length_list1 = 5;
int length_list2 = 5;
int j = 0;
int key = 0;
for(int i=0;i<length_list1;i++)
{
while(list2[j] < list1[i] && j < length_list2)
{
list[key] = list2[j];
key++;
j++;
}
list[key] = list1[i];
key++;
}
if(j < (length_list2-1))
{
for(int k=j+1;k<length_list2;k++)
{
list[k] = list2[k];
}
}
}
int main()
{
int list1[5] = {2,15,18,34,87};
int list2[5] = {4,21,43,54,65};
int list[10];
merge_sort(list,list1,list2);
for(int i = 0;i < 10;i++)
{
printf("%d\t",list[i]);
}
return 0;
}

Alt text

快速排序

  快速排序是随意选择一个元素作为基准数字,比基准数字大的在右边,比基准数字小的在左边。这样来快速排序。

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
# include<stdio.h>
/*快速排序*/
/* 这里是排序 */
int quick_sort(int *list,int i,int j)
{
int base = list[i];
while(i < j)
{
while(i < j && list[j] >= base)
{
j -= 1;
}
while(i < j && list[j] < base)
{
list[i] = list[j];
i += 1;
list[j] = list[i];
}
list[i] = base;
/* 测试输出每一次的变化
for(int k = 0;k < 10;k++)
{
printf("%d\t",list[k]);
}
printf("\n");
*/
}
return i;
}
/* 这里是一个递归*/
void recursion(int *list,int i,int j)
{
int base = 0;
if(i < j)
{
base = quick_sort(list,i,j);
recursion(list,i,base);
recursion(list,base+1,j);
}
}
int main()
{
int list[10] = {2,15,18,34,87,4,21,43,54,65};
int i = 0;
int length = 10;
recursion(list,i,length-1);
for(int i = 0;i < 10;i++)
{
printf("%d\t",list[i]);
}
return 0;
}

Alt text

Alt text