本帖最后由 PaulY 于 2019-1-15 23:14 编辑
冒泡排序
基本思想：
每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换
优点：
每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。
前提：顺序存储结构
具体实现过程：
相较于快排，归并类排序等来说的话，冒泡排序理解难度很低，通过for循环嵌套可以很容易的实现，内层循环负责完成每一次排序内容的互换调整，通过数组下标index累加完成遍历，通过temp作暂时存储完成与对应元素和index+1的对应元素大小的互换，循环时注意数组边界，外层循环负责整个排序算法的次数，在循环结束时完成排序算法。
还是用上次的数组{ 56, 92, 24, 37, 48, 86, 13, 39, 50, 90} 共10个元素。 基本步骤：
定义temp作为数据交换的媒介，mark做标记保存数组是否发生交换，index跟index+1则对应当前元素下标和后继元素下标，index存放数值较小的元素，index+1存放数值较大的元素。
整组元素出态如上图，蓝色箭头表示遍历方向，
index = 0时，对应数组元素数值56，index + 1 对应数组元素数值92，56 < 92，无需发生交换，循环+1
index = 1，对应数组元素数值92，index + 1 对应数组元素数值24，24 < 92，满足交换条件，通过temp交换二者数据，然后循环继续+1
index = 2，对应数组元素数值92，index + 1 对应数组元素数值37，37 < 92，满足交换条件，通过temp交换二者数据，然后循环继续+1
index = 3，对应数组元素数值48，index + 1 对应数组元素数值92，48 < 92，满足交换条件，通过temp交换二者数据，然后循环继续+1
index = 4，对应数组元素数值86，index + 1 对应数组元素数值92，86 < 92，满足交换条件，通过temp交换二者数据，然后循环继续+1
index = 5，对应数组元素数值13，index + 1 对应数组元素数值92，13 < 92，满足交换条件，通过temp交换二者数据，然后循环继续+1
后续几个元素交换过程同上。
最后最大值92换至数组尾端，此时，一趟排序完成。
下图为整个排序的输出情况：
代码如下：
[Java] 纯文本查看 复制代码 public BubbleSort(int[] array){
System.out.println("=====================冒泡排序=====================");
int temp = 0;
int mark = 1, arrayLenghtcount = array.length, count = 1;
for (int index = 0; index < array.length - 1; index++) {
if(mark == 0 || arrayLenghtcount == 1){
break;
}
mark = 0; //标记位置，置0时未发生交换，置1则发生交换
for (int index2 = 1; index2 < arrayLenghtcount; index2++) {
if(array[index2 - 1] > array[index2]){
mark = 1;
temp = array[index2 - 1];
array[index2 - 1] = array[index2];
array[index2] = temp;
}
}
System.out.println();
System.out.print("第" + count + "次冒泡排序结果：");
for (int outNumber = 0; outNumber < array.length; outNumber++) {
System.out.print(array[outNumber] + " ");
}
count++;
System.out.println();
arrayLenghtcount--; //每次排序会确定一位关键字，此排序采取增序完成排列，每次-1减少循环次数
}
}
算法优化部分： 由于每次必定会确定当前排序元素中的最大值（或者最小值），所以每次循环时，可以加一句循环自减功能来达到减少遍历的长度，同时，在内循环的交换语句内可以设置标记mark，用来保存每次遍历是否发生交换，如果任意一次没有发生任何交换，则整个数组此时已趋于有序，可直接跳出循环。
时间复杂度：
平均时间复杂度为O(n2)。 空间复杂度：
由于在交换过程中只需要一个缓冲元素temp，所以为1。
稳定性：
算法稳定。
| 
收藏
淘帖
踩
