1、冒泡排序2、选择排序 1、冒泡排序
一个数组如何编程有序数组呢？
需要排序算法
冒泡排序是最基础，最经典的排序算法，为什么叫作冒泡呢？
冒泡：水里有很多气泡，这些气泡都会慢慢升起，冒出水面，越大的气泡升起的速度就越快，因此：
对于一个数组，每一次循环让最大的元素冒泡到最后面
核心规则：
指向数组中两个相邻的元素（最开始是数组的头两个元素），并且比较他们的大小如果前者比后者大，则交换他们的位置如果后者比前者大，则不交换然后依次后移，每次循环将最大元素移动至最后一个位置
举例：
假设有一个数组为 5, 1, 8, 6, 9, 2，我们希望将其变成从小到大的排列
步骤如下：
首先比较 5 和 1 两个元素
因为 1 比 5 小，所以交换它们的位置
数组变为：1，5，8，6，9，2
继续比较 5 和 8 两个元素
因为 8 比 5 大，所以不交换它们的位置
数组仍为：1，5，8，6，9，2
接下来比较 8 和 6 两个元素
因为 6 比 8 小，所以交换它们的位置
数组变为：1，5，6，8，9，2
接下来比较 8 和 9 两个元素
因为 9 比 8 大，所以不交换它们的位置
数组仍为：1，5，6，8，9，2
接下来比较 9 和 2 两个元素
因为 2 比 9 小，所以交换它们的位置
数组变为：1，5，6，8，2，9
这时候第一次循环遍历已经结束，得到了最大的元素为：9
现在开始第二次的循环遍历，再次回到第一个和第二个元素
同理可得，第二轮遍历之后的数组可以得到：1，5，6，2，8，9
完成第二轮遍历之后，已经找到了数组中第二大的元素 8
以此类推，我们在第四次的循环遍历之后，就可以得到从小到大（升序）排列的数组了：1，2，5，6，8，9
代码如下：
// 冒泡排序public static void bubbleSort(int[] array) { // 每次循环，都能冒泡出剩余元素中最大的元素，所以我们循环 array.length 次`在这里插入代码片` for (int i = 0; i < array.length; i++) { // 2、每次遍历，只需要遍历 0 到 array.length - i - 1中的元素，因为在array.length - i - 1后面的元素都已经是最大的了 for (int j = 0; j < array.length - i - 1; j++) { // 3、通过判断大小条件进行元素的交换 if (array[j] > array[j+1]) { int temp = array[j+1]; array[j+1] = array[j]; array[j] = temp; } } }}
注意点：
每次冒泡都可以得到数组中最大的元素，所以如果要将整个数组都排好序，需要冒泡数组的个数次
即代码块中的 array.length
第一次遍历需要到数组结束为止，这时候已经可以得到了数组中最大的元素是9，并且将它放在数组末尾。第二次只需要遍历到倒数第二个元素即可
即代码块中的 array.length - i - 1
交换数组中的两个元素：
用临时变量 temp 存储第一个变量值将第二个变量赋值给第一个变量将临时变量赋值给第二个变量总结一下，我们可以得出比较的次数为：
N + (N - 1) + ..、+ 2 + 1 = (N^2 + N) / 2
最坏的情况下每次比较都需要交换，交换的次数为：(N^2 + N) / 2
所以整体的步数介于：(N^2 + N) / 2 ~ (N^2 + N) 之间
因此，用大O记法，最终的结果为：O(N^2)
2、选择排序什么是选择排序呢？
选择，顾名思义，就是每次在剩余数组中，选择最大或者最小的一个，放在数组的一端
核心规则：
利用两个变量，一个存储当前最大值，一个存储当前最大值所在的索引依次比较后面的元素，如果发现比当前最大值大，则更新最大值，并且更新最大值所在的索引直到遍历结束，将最大值放在数组的最右边，也就是交换最右边元素和当前最大值元素重复上面的步骤
举例：
第一次遍历：
第一次就可以查到最大元素为 9，并且记录最大元素索引位置为 0。等到扫描到最后一个元素 3 时，将最后一个元素 3 和第 0 个元素 9 交换。到这一步的时候，我们就已经选择到了最大的元素 9。
第二次遍历：
图片摘取自优课达学习官网
第二次遍历的时候，我们一次找到的最大值索引为：
// 最大值，索引 3，0 3，0 4，2 7，3 7，3
扫描结束后，替换倒数第二个元素 5，和索引值为 3 的元素 7
…依此类推，最终代码如下：
public static void SelectSort(int[] array) { // 遍历N次，每次选择数组剩余元素中最大的元素 for (int i = 0; i < array.length; i++) { // 暂时把第一个元素当做最大元素，并且记录最大元素的索引 int index = 0; int max = array[0]; // 注意 j 从 索引1 开始，到 array.length - i 截止 for (int j = 1; j < array.length - i; j++) { // 如果元素大于当前最大值，则替换 max，maxIndex if (array[j] > max) { max = array[j]; index = j; } }}// 交换最大值元素 和 数组末尾元素 array[index] = array[array.length - i - 1]; array[array.length - i - 1] = max;}
时间复杂度：
时间复杂度和冒泡排序一样，执行次数如下：
N + (N - 1) + ..、+ 2 + 1
最终结果为：O(N^2)
冒泡排序 vs 选择排序
虽然两个时间复杂度都为 O(N^2)，但很明显能感受到选择排序要更快一点，为什么呢？
冒泡需要频繁的交换相邻两个元素，而选择排序每次遍历只需要交换一次，所以选择排序真实情况速度比冒泡排序快一倍
希望本文能够得到您的认可~~~如果觉得本文有用的话来个 点赞 + 关注，或者分享给身边的朋友们，也希望各位大家能够给小橘子一些建议，我们一起加油！