冒泡排序与选择排序之间的联系

package com.algorithm.tiger.tree;

import java.util.Arrays;

/**
* 冒泡排序与选择排序之间的联系。
*
* @author tiger
* @Date 2017年7月22日
*/
public class BubbleSort {
public static void main(String[] args) {
// int[] arr = {21, 32, 43, 24, 33, 54, 23, 1, 56, 12, 2};
int[] arr = {1, 2, 13,12, 21, 24, 32, 33, 43, 534, 562333};
System.out.print("原始数组：");
System.out.println(Arrays.toString(arr));

System.out.println("====== 冒泡排序正统 ======");
// System.out.println(Arrays.toString(bubble(arr)));
System.out.println(Arrays.toString(bubbleOptimize(arr)));

System.out.println("====== 选择排序的前奏排序 ======");
int[] arr1 = {21, 32, 43, 24, 33, 54, 23, 1, 56, 12, 2};

System.out.println(Arrays.toString(select01(arr1)));
System.out.println("====== 选择排序 ======");
int[] arr2 = {21, 32, 43, 24, 33, 54, 23, 1, 56, 12, 2};
System.out.println(Arrays.toString(select02(arr2)));

}

/**
* 冒泡排序实现原理：相邻两个数两两比较，如果满足条件则交换，不满足，则进行下一个相邻的比较。
* 第一轮，将最大或最小的数搬到索引末端。
* 第二轮，将次大的放到索引次末端。
* ......
* 最后一轮，实现全部排序。
*
* @param arr
*/
public static int[] bubble(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
return arr;
}

/**
* 冒泡排序的优化
*
* @param arr
* @return
*/
public static int[] bubbleOptimize(int[] arr) {
//记录最后一次交换的位置，如没有交换，说明有序
int lastExchangeIndex = 0;
//无序数列的边界，每次比较只需要比到这里为止
int sortBorder = arr.length - 1;
for (int i = 0; i < arr.length - 1; i++) {
//有序标记，每一轮的初始值都是true
boolean isSorted = true;
//里层循环
for (int j = 0; j < sortBorder; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
//有交换，说明无序
isSorted = false;
//记录最后一次交换的位置
lastExchangeIndex = j;
}
}
sortBorder = lastExchangeIndex;
if (isSorted) break;
}
return arr;
}

/**
* 一轮选一个索引号固定，依次与其他的进行比较，满足条件则交换，直到比完所有数。接着下一轮比较
*
* @param arr
*/
public static int[] select01(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
//每轮比较，i位置的索引是固定的。一共比较arr.length-1轮
if (arr[j] < arr[i]) {
swap(arr, i, j);
}
}
}
return arr;
}

/**
* 选择排序，对上边冒泡排序[sort02]的改进
*
* @param arr
*/
public static int[] select02(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int max = arr[i];
int index = i;
for (int j = i + 1; j < arr.length; j++) {
//如果前边的比后边的大，则将最大值赋予max
if (arr[j] < max) {
max = arr[j];
//记录每一轮最终需要与 arr[i] 交换的索引号
index = j;
}
}
//一轮比较完再进行交换，减少了交换的次数，是对上面一种冒泡排序算法的优化
swap(arr, i, index);
}
return arr;
}

/**
* 交换元素
*
* @param arr
* @param i
* @param j
*/
public static void swap(int[] arr, int i, int j) {
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}