java算法系列之排序
手写冒泡
冒泡算是最基础的一个排序算法，简单的可以理解为，每一趟都拿i与i+1进行比较，两个for循环，时间复杂度为 O(n^2),同时本例与选择排序进行了比较，选择排序又叫直接排序，之所以直接，就是简单粗暴，不像冒泡，冒泡是紧挨着的两个小伙伴两两比较，直接排序是每一趟直接拿当前i与整个数组中所有元素进行比较，如果大小不一致，直接替换，相当于跳跃过去了，根本不考虑小伙伴的感受，我看到哪个小伙伴比我小，我就占领它的位置，彼此替换。
package com.rsc.sort;
import java.util.Arrays;
/**
* 冒泡排序
*
* @author 落雨 2015年6月5日09:33:13 http://ae6623.cn
*/
public class BubbleSort {
/**
* 直接排序(选择排序)
* i与j进行比较，如果大小不一致，直接将a[i]与a[j]元素进行置换
* @param array
*/
public static void selectionSort(int[] array) {
int temp = 0;
int total = 1;
for (int i = 0; i < array.length; i++) {// 循环length次
//System.out.println("第"+i+"趟");
for (int j = i + 1; j < array.length; j++) {// 从i+1开始和i进行比较，找到大小不一致的，直接与a[i]进行置换
if (array[i] > array[j]) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
for (int k : array) {
System.out.print(k + " ");
}
System.out.println("交换" + total++ + "次 【" + array[j] + "交换"
+ array[i] + "】");
}
}
}
}
/**
* 冒泡排序
* 只置换相邻的两个元素
* @param array
*/
public static void bubbleSort(int[] array) {
int temp = 0;
int total = 1;
boolean flag = false;
//对于length个元素，只需要比较length-1即可 比如 5个数字，只需要循环比较4次
for(int i=0;i<array.length-1;i++){
//由于是冒泡排序，第一个位置肯定是最小的，每循环i次，就不用再判断前i个位置，所以length-1-i
for(int j=0;j<array.length-i-1;j++){
if(array[j]>array[j+1]){
/*
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
*/
array[j] = array[j] ^ array[j+1];
array[j+1] = array[j] ^ array[j+1];
array[j] = array[j] ^ array[j+1];
flag = true;//发生了置换
for (int k : array) {
System.out.print(k + " ");
}
System.out.println("交换" + total++ + "次 【" + array[j+1] + "交换"
+ array[j] + "】");
}
}
if(!flag){//如果无置换，则跳出循环
break;
}else{
flag = false;//有置换，把标志位重新置为false，方便下一次判断
}
System.out.println("完成第"+(i+1)+"趟冒泡");
}
}
public static void swap(int a,int b){
a = a^b;
b = a^b;
a = a^b;
System.out.println(a+","+b);
}
public static void main(String[] args) {
//swap(5,3);
int[] array = { 4, 1, 3, 2, 5 , 6 , 8 , 7 , 9 };
int[] array2 = Arrays.copyOf(array, array.length) ;
System.out.println("直接排序如下:");
selectionSort(array);
System.out.println("冒泡排序如下:");
bubbleSort(array2);
}
}
打印结果如下:
直接排序如下:
1 4 3 2 5 6 8 7 9 交换1次 【4交换1】
1 3 4 2 5 6 8 7 9 交换2次 【4交换3】
1 2 4 3 5 6 8 7 9 交换3次 【3交换2】
1 2 3 4 5 6 8 7 9 交换4次 【4交换3】
1 2 3 4 5 6 7 8 9 交换5次 【8交换7】
冒泡排序如下:
1 4 3 2 5 6 8 7 9 交换1次 【4交换1】
1 3 4 2 5 6 8 7 9 交换2次 【4交换3】
1 3 2 4 5 6 8 7 9 交换3次 【4交换2】
1 3 2 4 5 6 7 8 9 交换4次 【8交换7】
完成第1趟冒泡
1 2 3 4 5 6 7 8 9 交换5次 【3交换2】
完成第2趟冒泡