冒泡排序

排序流程

通过重复地遍历排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复的地进行直到没有再需要交换，也就是或该数列已经排序完成。这个算法的名字由来是因为越小(大)的元素会经由交换慢慢的像泡泡一样“浮”到数列的顶端，故而得名。

代码实现

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
#include<iostream>
using namespace std;

void print(int* arr, int len)
{
	for (int i = 0; i < len; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
}

void swap(int& a, int& b)
{
	int temp = 0;
	temp = a;
	a = b;
	b = temp;
}

void PopSort1(int* arr,int len)
{
	
	for (int i = 0; i < len - 1; i++)
	{
		bool sorted = 0;//判断循环是否进行元素的交换了
		for (int j = 0; j < len - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])//稳定的排序算法，相同值的数，不会进行交换
			{
				sorted = 1;
				swap(arr[j], arr[j + 1]);
			}
		}
		if (!sorted)//本次循环没进行交换，说明排序已经完成，剩下还没进行的循环就不用进行了。
		{
			break;
		}
	
	}
	print(arr, len);
}

void PopSort2(int* arr, int len)
{
	int end = len - 1;
	while (end)
	{
		for (int i = 0; i < end; i++)//<end,保证每次都能取到第i+1个
		{
			if (arr[i] > arr[i + 1])
			{
				swap(arr[i], arr[i + 1]);
			}
		}
		end--;
	}
	print(arr, len);
}

int main(void)
{
	int arr[] = { 1,4,5,266,5,1,78,9 };
	int len = sizeof(arr) / sizeof(arr[0]);
	PopSort1(arr, len);
	//PopSort2(arr, len);

	return 0;
}