C++算法题

每天进步一点点

• *（一）从各类排序算法开始（左小右大）*
• 一、冒泡排序
• 二、选择排序
• 三、插入排序

一点点添加，不同的排序实现方法，之后会逐渐进行不同代码的补充，欢迎大家一起讨论。

冒泡排序是逐步对两个相邻位置进行数值上的比较。
如果比较结果满足要求，则位置不动；否则交换顺序。
经过第一遍遍历，最大值会跑到最后一个值，第二遍在前(length-1)的数组长度上继续遍历。

#include 
using namespace std;

void bubble_sort(int arr[], int length) {
	for (int i = 0; i < length; i++) {
		for (int j = 0; j < length - i - 1; j++) {
			if (arr[j] > arr[j+1]) {
				int tmp = arr[j+1];
				arr[j+1] = arr[j];
				arr[j] = tmp;
			}
		}
	}
	for (int i = 0; i < length; i++) {
		cout << arr[i] << "  ";
	}
	cout << endl;
}

int main() {
	int arr[] = { 32, 6, 2, 4, 3, 7, 100 };
	int len = 7;
	bubble_sort(arr, len);
	return 0;
}

时间计算复杂度O（n2）

选择排序是在固定长度序列中找最小值放到首位。
每次放到首位的就不要再去管它，只管后面未排好序的序列。
核心在于找最小值的部分。

#include 
using namespace std;

void selection_sort(int arr[], int length) {
	for (int i = 0; i < length; i++) {
		for (int j = i + 1; j < length; j++) {
			if (arr[i] > arr[j]) {
				int tmp = arr[j];
				arr[j] = arr[i];
				arr[i] = tmp;
			}	
		}
	}
	for (int i = 0; i < length; i++) {
		cout << arr[i] << "  ";
	}
	cout << endl;
}

int main() {
	int arr[] = { 32, 6, 2, 4, 3, 7, 100 };
	int len = 7;
	selection_sort(arr, len);
	return 0;
}

时间计算复杂度O（n2）