一.冒泡排序
1）基本思想
从无序序列头部开始，进行两两比较，根据大小交换位置，直到最后将最大（小）的数据元素交换到了无序队列的队尾，从而成为有序序列的一部分；下一次继续这个过程，直到所有数据元素都排好序。
2）时间复杂度
平均时间复杂度为O(n^2)
public class BubbleSortTest {
/**
* 冒泡排序
*/
public static int[] bubbleSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
for (int j = 0; j < a.length - 1 - i; j++) {
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
return a;
}
/**
* 冒泡排序优化一： 设置标志位flag标记一趟排序是否发生交换，如果没有交换，则数组已排好序
*/
public static int[] bubbleSort1(int[] a) {
int flag = 0;
for (int i = 0; i < a.length - 1; i++) {
for (int j = 0; j < a.length - 1 - i; j++) {
if (a[j] > a[j + 1]) {
flag = 1;
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
if (flag == 0) {
break;
}
}
return a;
}
/**
* 输出数组
*/
public static void printArray(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
public static void main(String[] args) {
int[] a = {5, 12, 45, 6, 3, 2, 123};
a = bubbleSort2(a);
printArray(a);
}
}
