1. 首页
  2. 文章中心
  3. 算法

冒泡快速等算法总结

166 阅读 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
#include <iostream>
using namespace std;
void show(int array[], int len)
{
	int i = 0;
	for(i=0; i<len; i++)
	{
		cout<<array[i]<<"  ";
	}
	cout<<endl;
}

void swap(int array[], int i, int j)
{
	int temp = array[i];
	array[i] = array[j];
	array[j] = temp;
}

void BubbleSort(int array[], int length)
{
	int i = 0;
	int j = 0;
	for(i = 0; i < length; i++)
	{
		for(j = length-1; j > i; j--)
		{
			if( array[j] < array[j-1] )
			{
				swap(array, j, j-1);			
			}
		show(array, length);
		}
	}

}

int main()
{
	int array[] ={8,3,6,1};
	int length = sizeof(array) / sizeof(*array); 
	cout<<"排序前"<<endl;
	show(array, length);
	cout<<endl;
	BubbleSort(array, length);
	cout<<endl;
	cout<<"排序后"<<endl;
	show(array, length);
	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
#include <iostream>
using namespace std;
void show(int array[], int len)
{
	int i = 0;
	for(i=0; i<len; i++)
	{
		cout<<array[i]<<"  ";
	}
	cout<<endl;
}

void swap(int array[], int i, int j)
{
	int temp = array[i];
	array[i] = array[j];
	array[j] = temp;
}

void BubbleSort(int array[], int length)
{
	int i = 0;
	int j = 0;
	bool if_finish = true;
	for(i=0; (i<length) && if_finish; i++)
	{
		if_finish = false;
		for(j=length-1; j>i; j--)
		{
			if( array[j] < array[j-1] )
			{
				swap(array, j, j-1);
				if_finish = 1;
			}
		}
	}
}

int main()
{
	int array[] ={8,3,6,1};
	int length = sizeof(array) / sizeof(*array); 
	show(array, length);
	BubbleSort(array, length);
	show(array, length);
	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
#include <iostream>
using namespace std;
void show(int array[], int len)
{
	int i = 0;
	for(i=0; i<len; i++)
	{
		cout<<array[i]<<"  ";
	}
	cout<<endl;
}

void swap(int array[], int i, int j)
{
	int temp = array[i];
	array[i] = array[j];
	array[j] = temp;
}

void SelectionSort(int array[], int length) 
{
	int i = 0;
	int j = 0;
	int sign = -1;

	for(i=0; i<length; i++)
	{
		sign = i; 
		for(j = i+1; j<length; j++)
		{
			if( array[j] < array[sign] ) 
			{
				sign = j;	
			}
			
		}
		if(i != sign)
		{
			show(array, length);
			swap(array, i, sign);
			show(array, length);
			cout<<endl;
		}
	}
}
int main()
{
	int array[] ={4, 1, 3, 2};
	int length = sizeof(array) / sizeof(*array); 
	cout<<"排序前"<<endl;
	show(array, length);
	cout<<endl;
	SelectionSort(array, length);
	cout<<endl;
	cout<<"排序后"<<endl;
	show(array, length);
	return 0;
}



插入排序：从第一个数X起，与其之后遇到的第一个比其大（小）的数Y，并将Y前面个个数都后移一位，并将Y移至X，之后到第二个数，以此往后。。。。

复制代码
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 <iostream>
using namespace std;
void show(int array[], int len)
{
	int i = 0;
	for(i=0; i<len; i++)
	{
		cout<<array[i]<<"  ";
	}
	cout<<endl;
}

void swap(int array[], int i, int j)
{
	int temp = array[i];
	array[i] = array[j];
	array[j] = temp;
}

void InertionSort(int array[], int length) 
{
	int i = 0;
	int j = 0;
	int sign = -1;
	int temp = -1;
	for(i=1; i<length; i++)
	{
		sign = i; 
		temp = array[sign];

		for(j = i-1; (j>=0) && (array[j]>temp); j--)
		{ 
			array[j+1] = array[j]; 
			sign = j; 
		}
		array[sign] = temp;
		show(array, length);
	}
}
int main()
{
	int array[] ={3, 1, 6, 5, 4, 2};
	int length = sizeof(array) / sizeof(*array); 
	cout<<"排序前"<<endl;
	show(array, length);
	cout<<endl;
	InertionSort(array, length);
	cout<<endl;
	cout<<"排序后"<<endl;
	show(array, length);
	return 0;
}



希尔排序：举例以效率比较高的3为例，n=length,n=n/3+1，第一个数与其后以3为倍数的个个数比较并排序，第二个数与其后以3为倍数的个个数比较并排序，以此为类...

复制代码
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
#include <iostream>
using namespace std;
void show(int array[], int len)
{
	int i = 0;
	for(i=0; i<len; i++)
	{
		cout<<array[i]<<"  ";
	}
	cout<<endl;
}

void swap(int array[], int i, int j)
{
	int temp = array[i];
	array[i] = array[j];
	array[j] = temp;
}
void ShellSort(int array[], int length)
{
	int i = 0;
	int j = 0;
	int k = -1;
	int temp = -1;
	int gap = length ;
	while( gap > 1)
	{
		gap = gap / 3 + 1;
		cout<<gap;
		for(i=gap; i<length; i+=gap)
		{
			k = i;
			temp = array[k];
			for(j=i-gap; (j>=0) && (array[j]>temp); j-=gap)
			{
				array[j+gap] = array[j];
				k = j;
			}
			array[k] = temp;
		}
		show(array, length);

		
	}

}

int main()
{
	int array[] ={7, 1, 6, 5, 4, 2};
	int length = sizeof(array) / sizeof(*array); 
	cout<<"排序前"<<endl;
	show(array, length);
	cout<<endl;
	ShellSort(array, length);
	cout<<endl;
	cout<<"排序后"<<endl;
	show(array, length);
	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
#include <iostream>
using namespace std;
void show(int array[], int len)
{
	int i = 0;
	for(i=0; i<len; i++)
	{
		cout<<array[i]<<"  ";
	}
	cout<<endl;
}

void swap(int array[], int i, int j)
{
	int temp = array[i];
	array[i] = array[j];
	array[j] = temp;
}
int partition(int array[], int low, int high)
{
	int pv = array[low];

	while( low < high )
	{
		while( (low < high) && (array[high] >= pv) )
		{
			high--; 
		}
		swap(array, low, high);
		while( (low < high) && (array[low] <= pv) )
		{
			low++;
		}
		swap(array, low, high);
	}
	return low;
}

void QSort(int array[], int low, int high)
{
	if( low < high )
	{
	
		int pivot = partition(array, low, high);
		QSort(array, low, pivot-1);
		QSort(array, pivot+1, high);
	}
}

int main()
{
	int array[] ={4, 1, 6, 5, 7, 2};
	int length = sizeof(array) / sizeof(*array); 
	cout<<"排序前"<<endl;
	show(array, length);
	cout<<endl;
	QSort(array,0,length-1);
	cout<<endl;
	cout<<"排序后"<<endl;
	show(array, length);
	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
#include <iostream>
using namespace std;
void show(int array[], int len)
{
	int i = 0;
	for(i=0; i<len; i++)
	{
		cout<<array[i]<<"  ";
	}
	cout<<endl;
}
void Merge(int src[], int des[], int low, int mid, int high)
{
	int i = low;
	int j = mid + 1;
	int k = low;

	while( (i <= mid) && (j <= high) ) 
	{
		if( src[i] < src[j] )
		{
			des[k++] = src[i++];
		}
		else
		{
			des[k++] = src[j++];
		}
	}

	while( i <= mid )  
	{
		des[k++] = src[i++];
	}
	while( j <= high ) 
	{
		des[k++] = src[j++];
	}
}

void MSort(int src[], int des[], int low, int high, int max)
{
	if( low == high ) 
	{
		des[low] = src[low]; 
	}
	else 
	{
		int mid = (low + high) / 2;
		int* space = (int*)malloc(sizeof(int) * max);
		if( space != NULL )
		{
			MSort(src, space, low, mid, max); 
			MSort(src, space, mid+1, high, max);
			Merge(space, des, low, mid, high); 
		}
		free(space);
	}
}

int main()
{
	int array[] ={4, 1, 6, 5, 7, 2};
	int length = sizeof(array) / sizeof(*array); 
	cout<<"排序前"<<endl;
	show(array, length);
	cout<<endl;
	MSort(array, array, 0, length-1, length);
	cout<<endl;
	cout<<"排序后"<<endl;
	show(array, length);
	return 0;
}



最后

以上就是有魅力缘分最近收集整理的关于冒泡快速等算法总结的全部内容，更多相关冒泡快速等算法总结内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(110)

相关文章

查找的类型
查找的类型
关于查找的有哪些常见算法？
关于查找的有哪些常见算法？
常见查找算法总结
常见查找算法总结
快速选择排序算法
快速选择排序算法
冒泡快速等算法总结
冒泡快速等算法总结
常见的查找算法
常见的查找算法
排序算法之快速排序
排序算法之快速排序
Python算法：三种高级排序的方法
Python算法：三种高级排序的方法

评论列表共有 0 条评论

立即
投稿
返回
顶部