冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
1024555-20161126001352300-2027386210.png
两个注意点：
- 每次排序会选出来一个最大的或者最小的值排在数组的首部或者尾部，这些都可以自己来控制，但我们只需要比较arry.length-1次就可以排序好了。
- 对于每次的排序，我们需要两两比较，两个数要比较一次，三个数要比较两次.....
所以只要比较arry.length-1次就可以比较出来一趟中的最大或者最小的一个，而且排好序的数是不需要再次比较的
优化前：
package cn.lk.java.sort;
import java.util.Scanner;
public class DemoBubbleSort {
public static void bubbleSort(int[] unsorted) {
int tmp;
// for(int i =0; i < unsorted.length - 1 ; i++) {//从数组的最后开始比较，将排好序的浮到数组的前端
// boolean flag = false;
// for(int j = unsorted.length - 1; j > i ; j--) {
// if( unsorted[j] < unsorted[j - 1]) {
// tmp = unsorted[j];
// unsorted[j] = unsorted[j - 1];
// unsorted[j - 1] = tmp;
// flag = true;
// }
// }
// if(!flag) {
// break;
// }
// }
for(int i =0; i < unsorted.length - 1 ; i++) {//从数组的前面开始比较，排好序的放在数组的后面
for(int j = 0 ; j < unsorted.length - i - 1 ; j++) {
if( unsorted[j] > unsorted[j + 1]) {
tmp = unsorted[j];
unsorted[j] = unsorted[j + 1];
unsorted[j + 1] = tmp;
flag = true;
}
}
}
for(int i = 0; i < unsorted.length; i++) {
System.out.print(unsorted[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int[] unsorted = new int[num];
for(int i = 0; i < num; i++) {
unsorted[i] = sc.nextInt();
}
bubbleSort(unsorted);
sc.close();
}
}
接着我们能小小的优化一下
在冒泡排序的过程中，如果某一趟执行完毕，没有做任何一次交换操作，比如数组[5,4,1,2,3]，执行了两次冒泡，也就是两次外循环之后，分别将5和4调整到最终位置[1,2,3,4,5]。此时，再执行第三次循环后，一次交换都没有做，这就说明剩下的序列已经是有序的，排序操作也就可以完成了，来看下代码
package cn.lk.java.sort;
import java.util.Scanner;
public class DemoBubbleSort {
public static void bubbleSort(int[] unsorted) {
int tmp;
// for(int i =0; i < unsorted.length - 1 ; i++) {
// boolean flag = false;
// for(int j = unsorted.length - 1; j > i ; j--) {
// if( unsorted[j] < unsorted[j - 1]) {
// tmp = unsorted[j];
// unsorted[j] = unsorted[j - 1];
// unsorted[j - 1] = tmp;
// flag = true;
// }
// }
// if(!flag) {
// break;
// }
// }
for(int i =0; i < unsorted.length - 1 ; i++) {
boolean flag = false;
for(int j = 0 ; j < unsorted.length - i - 1 ; j++) {
if( unsorted[j] > unsorted[j + 1]) {
tmp = unsorted[j];
unsorted[j] = unsorted[j + 1];
unsorted[j + 1] = tmp;
flag = true;
}
}
if(!flag) {
break;
}
}
for(int i = 0; i < unsorted.length; i++) {
System.out.print(unsorted[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int[] unsorted = new int[num];
for(int i = 0; i < num; i++) {
unsorted[i] = sc.nextInt();
}
bubbleSort(unsorted);
sc.close();
}
}
再次优化思路：
其实我们每趟两两比较不需要比较到上次排好序的数字，因为可能在上一趟比较的过程中，剩下的几次虽然比较了，但是都没有交换顺序，就是说剩下的数字都是有序的所以这一趟就不需要比较了。
设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。
package cn.lk.java.sort;
import java.util.Scanner;
public class DemoBubbleSort1 {
public static void bubbleSort(int[] arry) {
int i = arry.length -1, tmp;
while(i > 0){
int pos = 0;
for(int j = 0; j < i; j++){
if(arry[j] > arry[j + 1]) {
tmp = arry[j];
arry[j] = arry [j + 1];
arry[j + 1] = tmp;
pos = j;
}
}
i = pos;
}
for(i = 0; i < arry.length; i++) {
System.out.print(arry[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int[] arry = new int[num];
for(int i = 0; i < num; i++) {
arry[i] = sc.nextInt();
}
bubbleSort(arry);
sc.close();
}
}
最终优化：
传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。
package cn.lk.java.sort;
import java.util.Scanner;
public class DemoBubbleSort1 {
public static void bubbleSort(int[] arry) {
int i = arry.length -1, tmp;
while(i > 0){
int pos = 0;
for(int j = 0; j < i; j++){
if(arry[j] > arry[j + 1]) {
tmp = arry[j];
arry[j] = arry [j + 1];
arry[j + 1] = tmp;
pos = j;
}
}
i = pos;
}
for(i = 0; i < arry.length; i++) {
System.out.print(arry[i] + " ");
}
System.out.println();
}
public static void bubbleSort1(int[] arry) {
int low = 0, high = arry.length - 1, tmp;
while(low < high){
for(int i = 0; i < high; i++){
if(arry[i] > arry[i + 1]) {
tmp = arry[i];
arry[i] = arry[i+1];
arry[i+1] = tmp;
}
}
high--;
for(int i = high; i > low; i--){
if(arry[i] < arry[i - 1]) {
tmp = arry[i];
arry[i] = arry[i-1];
arry[i-1] = tmp;
}
}
low++;
}
for(int i = 0; i < arry.length; i++) {
System.out.print(arry[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int[] arry = new int[num];
for(int i = 0; i < num; i++) {
arry[i] = sc.nextInt();
}
//bubbleSort(arry);
bubbleSort1(arry);
sc.close();
}
}
最最终极优化：
按照设置pos的优化思想，进行优化
package cn.lk.java.sort;
import java.util.Scanner;
public class DemoBubbleSort1 {
public static void bubbleSort(int[] arry) {
int i = arry.length -1, tmp;
while(i > 0){
int pos = 0;
for(int j = 0; j < i; j++){
if(arry[j] > arry[j + 1]) {
tmp = arry[j];
arry[j] = arry [j + 1];
arry[j + 1] = tmp;
pos = j;
}
}
i = pos;
}
for(i = 0; i < arry.length; i++) {
System.out.print(arry[i] + " ");
}
System.out.println();
}
public static void bubbleSort1(int[] arry) {
int low = 0, high = arry.length - 1, tmp;
while(low < high){
int pos = low;
for(int i = 0; i < high; i++){
if(arry[i] > arry[i + 1]) {
tmp = arry[i];
arry[i] = arry[i+1];
arry[i+1] = tmp;
pos = i;
}
}
high = pos;
int pos2 = high;
for(int i = high; i > low; i--){
if(arry[i] < arry[i - 1]) {
tmp = arry[i];
arry[i] = arry[i-1];
arry[i-1] = tmp;
pos2 = i;
}
}
low = pos2;
}
for(int i = 0; i < arry.length; i++) {
System.out.print(arry[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int[] arry = new int[num];
for(int i = 0; i < num; i++) {
arry[i] = sc.nextInt();
}
//bubbleSort(arry);
bubbleSort1(arry);
sc.close();
}
}
冒泡排序的
最差时间： O(n2)
平均时间复杂度： O(n2)
空间复杂度 O(1)
稳定性： 稳定
