选择排序

问题引入

将下列身高排序

首先,选择排序的方法是,找出最大的,跟最后一个换.

再找出除最后一个外,最大的,跟倒数第二个换.

以此类推

重复以上步骤,直到

代码实现

#include <iostream>
#include <stdlib.h>


void swap(int *num1, int *num2)
{
	int tmp = *num1;
	*num1 = *num2;
	*num2 = tmp;
}

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

		if (max != (len - 1 - i)) 
			swap(&arr[max], &arr[len - 1 - i]);
	}
}

int main(void)
{

	int  Data[] = { 163, 161, 158, 165, 171, 170, 163, 159, 162 };

	int len = sizeof(Data) / sizeof(Data[0]);
	SelectSort(Data, len);

	for (int i = 0; i < len; i++) {
		std::cout << Data[i] << "  ";
	}
	std::cout << std::endl;
	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

冒泡排序

排序如下数据

使用冒泡排序,上数据中,除了第一个数据以外,其他的数据已经是有序的了,所以只需要第一个和第二个交换,然后和第三个交换,如此循环,直到和最后一个交换后,整个数据就有虚了.

当然,如上数据是一种特例,并不是每次都会这么幸运,像如下情况就更复杂一些,一趟并不能完全解决问题, 需要多趟才可以.

经过上述五步后,得到的结果:

此时,我们只保障了最后一个数是最大的, 并不能保障前面的数一定会有序,所以,我们继续按照上面五步对剩下的 5 个数继续进行一次排序,数组就变得有序了.

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

代码实现

#include <iostream>
#include <stdlib.h>


void swap(int* num1, int* num2)
{
	int tmp = *num1;
	*num1 = *num2;
	*num2 = tmp;
}

void BubbleSort(int arr[], int len)
{
	for (int i = 0; i < len - 1; i++)
	{
		bool sorted = true;
		for (int j = 0; j < len - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
				swap(&arr[j], &arr[j + 1]);
			sorted = false;
		}
		if (sorted) break;
	}
}

int main(void)
{

	int  Data[] = { 163, 161, 158, 165, 171, 170, 163, 159, 162 };

	int len = sizeof(Data) / sizeof(Data[0]);
	BubbleSort(Data, len);

	for (int i = 0; i < len; i++) {
		std::cout << Data[i] << "  ";
	}
	std::cout << std::endl;
	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