TOC
冒泡排序
普通冒泡
思路
- 由index=[ 0 , length-1-rangNumber ) 开始比较a[i]与a[i+1]的大小，若a[i]>a[i+1]，则交换，因此一次循环则将最大的数冒泡至最末尾;
- 将步骤1循环执行length-1 次;
代码
public static void bubbingSortNormal(int[] source) {
if (null == source) {
throw new RuntimeException("NPE");
}
for (int rangeNumber = 0, size = source.length; rangeNumber < size - 1; rangeNumber++) {
for (int index = 0; index < size - 1 -rangeNumber; index++) {
if (source[index] >= source[index + 1]) {
//exchange source[j] and source[j + 1]
source[index] ^= source[index + 1];
source[index + 1] ^= source[index];
source[index] ^= source[index + 1];
}
}
}
}
优化冒泡
思路
- 使用一个flag标志，若某次冒泡都没有交换则提前终止冒泡;
代码
public static void bubbingSortOptimization(int[] source) {
if (null == source) {
throw new RuntimeException("NPE");
}
boolean overFlag = true;
for (int rangNumber = 0, size = source.length; rangNumber < size - 1; rangNumber++) {
overFlag = true;
for (int index = 0; index < size - 1 - rangNumber; index++) {
if (source[index] >= source[index + 1]) {
//exchange source[j] and source[j + 1]
source[index] ^= source[index + 1];
source[index + 1] ^= source[index];
source[index] ^= source[index + 1];
overFlag = false;
}
}
if (overFlag) {
break;
}
}
}
跳跃冒泡
思路
- 每次冒泡记录最后一次交换的位置lastExchangeIndex;
- 下次冒泡终点为lastExchangeIndex;
- lastExchangeIndex = 0 时终止;
代码
/**
* 设置一记录位置变量lastExchangeIndex,用于记录每趟排序中最后一次进行交换的位置。
* 由于lastExchangeIndex位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可
*
* @param source
*/
public static void bubbingSortByExchangeIndex(int[] source) {
if (null == source) {
throw new RuntimeException("NPE");
}
int endIndex = source.length - 1;
int lastExchangeIndex = 0;
while (endIndex > 0) {
lastExchangeIndex = 0;
for (int j = 0; j < endIndex; j++) {
if (source[j] > source[j + 1]) {
source[j] ^= source[j + 1];
source[j + 1] ^= source[j];
source[j] ^= source[j + 1];
lastExchangeIndex = j;
}
}
endIndex = lastExchangeIndex;
}
}
双向冒泡 + 跳跃冒泡
思路
- 每次冒泡头尾同时冒泡；
- 正向由0开始正向最后交换位置(positiveLastExchageIndex);逆向由length-1开始逆向最后交换位置结束(reverseLastExchangeIndex);
代码
/**
* 一次循环 双向冒泡 同时使用标志性变量reverseLastExchangeIndex,positiveLastExchageIndex.
* 记录最后一次交换位置。
*
* @param source
*/
public static void bubbingSortBidirectional(int[] source) {
if (null == source) {
throw new RuntimeException("NPE");
}
int endIndex = source.length - 1;
int reverseLastExchangeIndex = source.length - 1;
int beginIndex = 0;
int positiveLastExchageIndex = 0;
while (beginIndex < endIndex) {
reverseLastExchangeIndex = source.length - 1;
positiveLastExchageIndex = 0;
for (int i = beginIndex; i < endIndex; i++) {
if (source[i] > source[i + 1]) {
source[i] ^= source[i + 1];
source[i + 1] ^= source[i];
source[i] ^= source[i + 1];
positiveLastExchageIndex = i;
}
}
for (int i = endIndex; i > beginIndex; i--) {
if (source[i] <= source[i - 1]) {
source[i] ^= source[i - 1];
source[i - 1] ^= source[i];
source[i] ^= source[i - 1];
reverseLastExchangeIndex = i;
}
}
beginIndex = reverseLastExchangeIndex;
endIndex = positiveLastExchageIndex;
}
}
测试
package com.pismery.study.structure.sort;
import com.pismery.study.structure.random.RandomUtils;
import lombok.extern.slf4j.Slf4j;
import org.junit.Rule;
import org.junit.Test;
import org.junit.rules.ExpectedException;
import java.util.Arrays;
import static org.junit.Assert.assertArrayEquals;
/**
* Created by pismery on 2018-06-06.
*/
@Slf4j
public class BubbingSortTest {
@Rule
public final ExpectedException expectedException = ExpectedException.none();
@Test
public void bubbingSort_Version1() {
int[] actual = RandomUtils.randomArrayNoRepeat(1, 2000, 100);
int[] expect = Arrays.copyOf(actual, actual.length);
Arrays.sort(expect);
log.info("Array: " + Arrays.toString(actual));
BubbingSort.bubbingSortNormal(actual);
assertArrayEquals(expect, actual);
}
@Test
public void bubbingSort_Version2() {
int[] actual = RandomUtils.randomArrayNoRepeat(1, 2000, 100);
log.info("Array: " + Arrays.toString(actual));
int[] expect = Arrays.copyOf(actual, actual.length);
Arrays.sort(expect);
BubbingSort.bubbingSortOptimization(actual);
assertArrayEquals(expect, actual);
}
@Test
public void bubbingSort_Version3() {
int[] actual = RandomUtils.randomArrayNoRepeat(1, 2000, 100);
log.info("Array: " + Arrays.toString(actual));
int[] expect = Arrays.copyOf(actual, actual.length);
Arrays.sort(expect);
BubbingSort.bubbingSortByExchangeIndex(actual);
assertArrayEquals(expect, actual);
}
@Test
public void bubbingSortBidirectional() {
int[] actual = RandomUtils.randomArrayNoRepeat(1, 10, 5);
log.info("Array: " + Arrays.toString(actual));
int[] expect = Arrays.copyOf(actual, actual.length);
Arrays.sort(expect);
BubbingSort.bubbingSortBidirectional(actual);
assertArrayEquals(expect, actual);
}
@Test
public void bubbingSort_Version1_Exception() {
expectedException.expect(RuntimeException.class);
expectedException.expectMessage("NPE");
BubbingSort.bubbingSortNormal(null);
}
@Test
public void bubbingSort_Version2_Exception() {
expectedException.expect(RuntimeException.class);
expectedException.expectMessage("NPE");
BubbingSort.bubbingSortOptimization(null);
}
@Test
public void bubbingSort_Version3_Exception() {
expectedException.expect(RuntimeException.class);
expectedException.expectMessage("NPE");
BubbingSort.bubbingSortByExchangeIndex(null);
}
@Test
public void bubbingSortBidirectional_Exception() {
expectedException.expect(RuntimeException.class);
expectedException.expectMessage("NPE");
BubbingSort.bubbingSortBidirectional(null);
}
}