目录：
1.常见算法复杂度
2.冒泡排序
3.选择排序
1.常见算法复杂度
image.png
相关概念
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
- 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
- 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
- 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
2.冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法。适用于少量数据排序，数据越少性能越优
2.1算法描述
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 针对所有的元素重复以上的步骤，除了最后一个；
- 重复步骤1~3，直到排序完成。
2.2代码实现
/**
* 冒泡排序 只使用于少量数据
*
* @param array {3,2,5,8,1}
* 1次循环 2 3 5 1 8
* 2次循环 2 3 1 5 8
* 3次循环 2 1 3 5 8
* 4次循环 2 3 5 1 8
* 5次循环 1 2 3 5 8
*/
public void bubbleSort(int[] array) {
// n*(n-1)/2 n
for (int i = array.length - 1; i > 0; i--) {
boolean flag = true;
for (int j = 0; j < i; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
flag = false;
}
}
if (flag) {
break;
}
}
}
3.选择排序（Select Sort）
选择排序（Select Sort） 是直观的排序，首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 双重循环时间复杂度为 O(n^2)
3.1算法描述
- 在一个长度为 N 的无序数组中，第一次遍历 n-1 个数找到最小的和第一个数交换。
- 第二次从下一个数开始遍历 n-2 个数，找到最小的数和第二个数交换。
- 重复以上操作直到第 n-1 次遍历最小的数和第 n-1 个数交换，排序完成。
3.2代码实现
/**
* 选择排序 使用于少量数据
*
* @param array {3,2,5,8,1}
* 1次循环 1 2 5 8 3
* 2次循环 1 2 5 8 3
* 3次循环 1 2 3 8 5
* 4次循环 1 2 3 5 8
* 5次循环 1 2 3 5 8
*/
public void selectSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
int index = i;
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[index]) {
index = j;
}
}
//{1,2,3,5,8}
//如果已经是最小的，就不需要交换
if (index != i) {
int temp = array[index];
array[index] = array[i];
array[i] = temp;
}
}
}
