冒泡排序
思路
依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。
原始数据：
第一轮交换
本轮共进行 4 次交换，也就是 （数据的个数-1） 次
第一次交换:
由于3比6小，所以本轮没有交换。
第二次交换：
由于6比4大，所以将 6 和 4 交换位置
第三次交换:
由于6比1大，所以将 6 和 1 交换位置
第四次交换:
由于6比2大， 所以将 6 和 2 交换位置
第二轮交换
由于最后一个数已经是最大值，所以不需要比较第4个数字和第5个数字
本轮共进行 3 次交换，也就是 （数据的个数-2）
第一次交换：
由于3比4小，所以没有发生交换
第二次交换:
由于4比1大，所以互相交换位置 
第三次交换:
交换4和2的位置 
第三轮交换
第四，第五个数已经排好序了
本轮共进行2次交换,也就是（数据的个数-3）
第一次交换：
交换 1 和 3 的位置
第二次交换：
交换 2 和 3 的位置
第四轮交换
第3个，第4个，第5个数据已经排好序了.
本轮共进行1次交换，也就是（数据个数-1）次
第一次交换：
无需交换
交换结果
到这里原始数据已经排好序了，共进行了 4 轮交换，也就是（数据的个数-1）轮
编码
第一轮排序代码:
public class bubbleSort {
public static void main(String[] args) {
int[] value = {3,6,4,1,2};
new bubbleSort().sort(value);
System.out.println("第一次排序");
for (int i : value) {
System.out.print(i + ",");
}
}
public void sort(int[] value) {
for (int i = 0; i < value.length - 1; i++) {
int temp;
if (value[i] > value[i+1]){
temp = value[i];
value[i] = value[i+1];
value[i+1] = temp;
}
}
}
}
第二轮排序代码:
这里我们只需要把循环体中的 停止的条件变为 （value.length - 2）即可
public class bubbleSort {
public static void main(String[] args) {
int[] value = {3,4,1,2,6};
new bubbleSort().sort(value);
System.out.println("第二次排序");
for (int i : value) {
System.out.print(i + ",");
}
}
public void sort(int[] value) {
for (int i = 0; i < value.length - 2; i++) {
int temp;
if (value[i] > value[i+1]){
temp = value[i];
value[i] = value[i+1];
value[i+1] = temp;
}
}
}
}
第三轮排序代码:
这里我们只需要把循环体中的 停止的条件变为 （value.length - 3）即可
public class bubbleSort {
public static void main(String[] args) {
int[] value = {3,1,2,4,6};
new bubbleSort().sort(value);
System.out.println("第三次排序");
for (int i : value) {
System.out.print(i + ",");
}
}
public void sort(int[] value) {
for (int i = 0; i < value.length - 3; i++) {
int temp;
if (value[i] > value[i+1]){
temp = value[i];
value[i] = value[i+1];
value[i+1] = temp;
}
}
}
}
第四轮交换代码：
这里我们只需要把循环体中的 停止的条件变为 （value.length - 4）即可
public class bubbleSort {
public static void main(String[] args) {
int[] value = {1,2,3,4,6};
new bubbleSort().sort(value);
System.out.println("第四次排序");
for (int i : value) {
System.out.print(i + ",");
}
}
public void sort(int[] value) {
for (int i = 0; i < value.length - 4; i++) {
int temp;
if (value[i] > value[i+1]){
temp = value[i];
value[i] = value[i+1];
value[i+1] = temp;
}
}
}
}
到这里，我们已经发现了规律
我们只需要用一个外层循环去控制轮次即可
public class bubbleSort {
public static void main(String[] args) {
int[] value = {3,6,4,1,2};
new bubbleSort().sort(value);
System.out.println("最终结果");
for (int i : value) {
System.out.print(i + ",");
}
}
public void sort(int[] value) {
//外层循环控制进行轮次
for (int j =1; j < value.length; j++){
//内层循环控制交换次数
for (int i = 0; i < value.length - j; i++) {
int temp;
if (value[i] > value[i+1]){
temp = value[i];
value[i] = value[i+1];
value[i+1] = temp;
}
}
System.out.println("第" + j + "次排序");
for (int i : value) {
System.out.print(i + ",");
}
System.out.println();
}
}
}
思考
如果一开始提供的数据就已经是排好序的数据，我们就不需要进行排序
public class bubbleSort {
public static void main(String[] args) {
int[] value = {1,2,3,4,5,6,7,8};
new bubbleSort().sort(value);
System.out.println("最终结果");
for (int i : value) {
System.out.print(i + ",");
}
}
public void sort(int[] value) {
for (int j =1; j < value.length; j++){
for (int i = 0; i < value.length - j; i++) {
int temp;
if (value[i] > value[i+1]){
temp = value[i];
value[i] = value[i+1];
value[i+1] = temp;
}
}
System.out.println("第" + j + "次排序");
for (int i : value) {
System.out.print(i + ",");
}
System.out.println();
}
}
}
我们可以加一个变量统计在一轮交换中的交换次数, 。 (提示：在每一轮结束后，不要忘记初始化count)
public class bubbleSort {
public static void main(String[] args) {
int[] value = {1,2,3,4,5,6,7,8};
new bubbleSort().sort(value);
System.out.println("最终结果");
for (int i : value) {
System.out.print(i + ",");
}
}
public void sort(int[] value) {
for (int j =1; j < value.length; j++){
//统计
int count = 0;
for (int i = 0; i < value.length - j; i++) {
int temp;
if (value[i] > value[i+1]){
count = count + 1;
temp = value[i];
value[i] = value[i+1];
value[i+1] = temp;
}
}
System.out.println("第" + j + "次排序");
for (int i : value) {
System.out.print(i + ",");
}
System.out.println();
if (count == 0){
return;
}
count = 0;
}
}
}
我们把数据换为
int[] value = {2,3,1,3,5,6,7,8};
这里由于第2次有交换，而第3次没有交换，所以两次交换结果一致
