向大端冒泡
public class BubbleSort {
public static <T extends Comparable<? super T>> void sort(T[] arr) {
for (int i = 0, len = arr.length; i < len - 1; i++) {
for (int j = 0; j < len - i - 1; j++) {
if (arr[j].compareTo(arr[j + 1]) > 0) {
swap(arr, j, j + 1);
}
}
}
}
private static void swap(Object[] arr, int i, int j) {
if (i != j) {
Object temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
private static void printArr(Object[] arr) {
for (Object o : arr) {
System.out.print(o);
System.out.print("t");
}
System.out.println();
}
public static void main(String args[]) {
Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
printArr(arr);//3 5 1 7 2 9 8 0 4 6
sort(arr);
printArr(arr);//0 1 2 3 4 5 6 7 8 9
}
}
向小端冒泡
public class BubbleSort {
public static <T extends Comparable<? super T>> void sort(T[] arr) {
for (int i = 0, len = arr.length; i < len - 1; i++) {
for (int j = len - 1; j > i; j--) {
if (arr[j-1].compareTo(arr[j])>0) {
swap(arr,j - 1, j);
}
}
}
}
private static void swap(Object[] arr, int i, int j) {
if (i != j) {
Object temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
private static void printArr(Object[] arr) {
for (Object o : arr) {
System.out.print(o);
System.out.print("t");
}
System.out.println();
}
public static void main(String args[]) {
Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
printArr(arr);//3 5 1 7 2 9 8 0 4 6
sort(arr);
printArr(arr);//0 1 2 3 4 5 6 7 8 9
}
}
鸡尾酒排序（来回排序）
例子来自百度：以序列(2,3,4,5,1)为例，鸡尾酒排序只需要访问两次（升序降序各一次 ）次序列就可以完成排序，但如果使用冒泡排序则需要四次。
普通冒泡和鸡尾酒都是交换了4次，但是鸡尾酒是遍历了2遍数组，也就是读取了10个数；而冒泡排序遍历了4遍数组，也就是读取了20个数。
public class BubbleSort {
public static <T extends Comparable<? super T>> void sort(T[] arr) {
int low = 0;//low前面的已经排好序
int high = arr.length - 1;//high后面的已经排好序
while (low < high) {//俩指针相遇说明排序完毕
//正向冒泡
for (int i = low; i < high; i++) {
if (arr[i].compareTo(arr[i + 1]) > 0) {
swap(arr, i, i + 1);
}
}
high--;
//反向冒泡
for (int j = high; j > low; j--) {
if (arr[j - 1].compareTo(arr[j]) > 0) {
swap(arr, j - 1, j);
}
}
low++;
}
}
private static void swap(Object[] arr, int i, int j) {
if (i != j) {
Object temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
private static void printArr(Object[] arr) {
for (Object o : arr) {
System.out.print(o);
System.out.print("t");
}
System.out.println();
}
public static void main(String args[]) {
Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
printArr(arr);//3 5 1 7 2 9 8 0 4 6
sort(arr);
printArr(arr);//0 1 2 3 4 5 6 7 8 9
}
}
冒泡优化1：用标记位提前判断有序性
在数组基本有序时，如果经过少数趟冒泡后，发现已经顺序了，则不必循环完n-1次才结束，这时已经可以立即停止排序了。
public class BubbleSort {
public static <T extends Comparable<? super T>> void sort(T[] arr) {
for (int i = 0, len = arr.length; i < arr.length; i++) {
boolean hasChanged = false;
for (int j = 0; j < len - i - 1; j++) {
if (arr[j].compareTo(arr[j + 1]) > 0) {
swap(arr, j, j + 1);
hasChanged = true;
}
}
if(!hasChanged) break;
}
}
private static void swap(Object[] arr, int i, int j) {
if (i != j) {
Object temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
private static void printArr(Object[] arr) {
for (Object o : arr) {
System.out.print(o);
System.out.print("t");
}
System.out.println();
}
public static void main(String args[]) {
Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
printArr(arr);//3 5 1 7 2 9 8 0 4 6
sort(arr);
printArr(arr);//0 1 2 3 4 5 6 7 8 9
}
}
冒泡优化2：记录下最后一次交换的位置j，表示j后面已经排好序
随时地变更i，即还需要遍历的次数在不断变更。普通冒泡排序每一趟排序只能减少1个数字的遍历规模(也就是i++)，但是记录最后交换位置后，每次可以减少多个数字(也就是i = len - lastPosition - 1)。
public class BubbleSort {
public static <T extends Comparable<? super T>> void sort(T[] arr) {
for (int i = 0, len = arr.length, lastPosition = 0; i < len - 1; i = len - lastPosition - 1) {
lastPosition = 0;
for (int j = 0; j < len - i - 1; j++) {
if (arr[j].compareTo(arr[j + 1]) > 0) {
swap(arr, j, j + 1);
lastPosition = j;
}
}
}
}
private static void swap(Object[] arr, int i, int j) {
if (i != j) {
Object temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
private static void printArr(Object[] arr) {
for (Object o : arr) {
System.out.print(o);
System.out.print("t");
}
System.out.println();
}
public static void main(String args[]) {
Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
printArr(arr);//3 5 1 7 2 9 8 0 4 6
sort(arr);
printArr(arr);//0 1 2 3 4 5 6 7 8 9
}
}
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
