为了方便测试，排序方法必须实现该接口。
public interface SortMethod {
int[] sortAlgorithm(int[] data);
default void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
排序方法：
1、冒泡排序法
package arithmetic.sort_method;
import arithmetic.test_environment.strategy.SortMethod;
public class BubbleSort implements SortMethod {
public int[] sortAlgorithm(int[] data) {
int temp = 0;
for (int i = 1; i < data.length; i++) {
for (int j = 0; j < data.length - i; j++) {
if (data[j] > data[j + 1]) {
swap(data, j, j + 1);
}
}
}
return data;
}
}
2、选择排序
package arithmetic.sort_method;
import arithmetic.test_environment.strategy.SortMethod;
public class SelectSort implements SortMethod {
@Override
public int[] sortAlgorithm(int[] data) {
int min,temp;
for (int i = 0; i < data.length - 1; i++){
min = i;
for (int k = i + 1; k < data.length; k++){
if (data[min] > data[k])
min = k;
}
if (min != i){
swap(data, min, i);
}
}
return data;
}
}
3、插入排序
package arithmetic.sort_method;
import arithmetic.test_environment.strategy.SortMethod;
public class InsertSort implements SortMethod {
@Override
public int[] sortAlgorithm(int[] data) {
int k,temp;
for (int i = 1;i < data.length; i++){
temp = data[i];
k = i;
while (k > 0 && temp < data[k - 1]){
data[k] = data[k - 1];
k--;
}
if (k != i){
data[k] = temp;
}
}
return data;
}
}
4、希尔排序
package arithmetic.sort_method;
import arithmetic.test_environment.strategy.SortMethod;
public class ShellSort implements SortMethod {
@Override
public int[] sortAlgorithm(int[] data) {
int step = 1;
while (step < data.length) {
step = step * 3 + 1;
}
int k,temp;
while (step > 0) {
for (int i = step; i < data.length; i++) {
//括号内是一个插入排序
temp = data[i];
k = i;
while (k >= step && temp < data[k - step]) {
data[k] = data[k - step];
k -= step;
}
if (k != i)
data[k] = temp;
}
step = (int) Math.floor(step / 3);
}
return data;
}
}
5、归并排序
package arithmetic.sort_method;
import arithmetic.test_environment.strategy.SortMethod;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.MethodSource;
public class MergeSort implements SortMethod {
@Override
public int[] sortAlgorithm(int[] data) {
mergeSort(data, 0, data.length - 1);
return data;
}
private void mergeSort(int[] data, int low, int high){
if (low < high){
int middle = (low + high) / 2;
mergeSort(data,low,middle);
mergeSort(data,middle + 1, high);
merge(data,low,middle,high);
}
}
@ParameterizedTest
@MethodSource("arithmetic.test_method.ProvideData#provideSourceData")
public void merge(int[] data, int start, int middle, int end){
int[] temp = new int[end - start + 1];
int low = start;
int high = middle + 1;
int index = 0;
while (low <= middle && high <= end){
if (data[low] <= data[high]){
temp[index] = data[low];
low++;
}
else {
temp[index] = data[high];
high++;
}
index++;
}
while (low <= middle){
temp[index] = data[low];
low++;
index++;
}
while (high <= end){
temp[index] = data[high];
high++;
index++;
}
for (int i = 0; i < temp.length; i++){
data[start] = temp[i];
start++;
}
}
}
6、单指针快速排序
package arithmetic.sort_method.quick_sort;
import arithmetic.test_environment.strategy.SortMethod;
public class QuickSortSingleNeedle implements SortMethod {
@Override
public int[] sortAlgorithm(int[] data) {
return quickSort(data,0,data.length);
}
private int[] quickSort(int[] data, int left, int right) {
//递归约束
if (left < right) {
int partitionIndex = partition(data, left, right);
quickSort(data, left, partitionIndex);
quickSort(data, partitionIndex + 1, right);
}
return data;
}
private int partition(int[] data, int left, int right) {
// 设定基准值（pivot）
int pivot = left;
int index = pivot + 1;
for (int i = index; i < right; i++) {
if (data[i] < data[pivot]) {
swap(data, i, index);
index++;
}
}
swap(data, pivot, index - 1);
return index - 1;
}
}
7、双指针快速排序
package arithmetic.sort_method.quick_sort;
import arithmetic.test_environment.strategy.SortMethod;
public class QuickSortDoubleNeedle implements SortMethod {
@Override
public int[] sortAlgorithm(int[] data) {
return quickSort(data,0,data.length -1);
}
private int[] quickSort(int[] data, int start, int end) {
if (start < end){
int partition = partition(data, start, end);
quickSort(data,start,partition);
quickSort(data,partition + 1,end);
}
return data;
}
private int partition(int[] data, int start, int end){
int left = start;
int right = end;
int pivot = data[left];
while (left < right) {
while (right > left && data[right] >= pivot) {
right--;
}
data[left] = data[right];
while (right > left && data[left] <= pivot) {
left++;
}
data[right] = data[left];
}
data[left] = pivot;
return left;
}
}
8、堆排序
package arithmetic.sort_method;
import arithmetic.test_environment.strategy.SortMethod;
public class HeapSort implements SortMethod {
@Override
public int[] sortAlgorithm(int[] data) {
int size = data.length - 1;
int start = size / 2;
for (int i = start; i >= 0; i--){
MaxHeap(data, data.length, i);
}
for (int i = size; i > 0; i--){
swap(data, 0 ,i);
MaxHeap(data, i, 0);
}
return data;
}
private void MaxHeap(int[] data, int size, int index){
int leftNode = 2 * index + 1;
int rightNode = 2 * index + 2;
int max = index;
if (leftNode < size && data[max] < data[leftNode])
max = leftNode;
if (rightNode < size && data[max] < data[rightNode])
max = rightNode;
if (max != index){
swap(data, max, index);
MaxHeap(data, size, max);
}
}
}
9、计数排序
package arithmetic.sort_method;
import arithmetic.test_environment.strategy.SortMethod;
public class CountSort implements SortMethod {
@Override
public int[] sortAlgorithm(int[] data) {
int maxValue = getMaxValue(data);
return countingSort(data, maxValue);
}
private int[] countingSort(int[] arr, int maxValue) {
int bucketLen = maxValue + 1;
int[] bucket = new int[bucketLen];
for (int value : arr) {
bucket[value]++;
}
int sortedIndex = 0;
for (int j = 0; j < bucketLen; j++) {
while (bucket[j] > 0) {
arr[sortedIndex++] = j;
bucket[j]--;
}
}
return arr;
}
private int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if (maxValue < value) {
maxValue = value;
}
}
return maxValue;
}
}
10、桶排序
package arithmetic.sort_method;
import arithmetic.test_environment.strategy.SortMethod;
import java.util.Arrays;
public class BucketSort implements SortMethod {
private static final SortMethod sortMethod = new InsertSort();
@Override
public int[] sortAlgorithm(int[] data) {
try {
bucketSort(data, 100);
} catch (Exception e) {
e.printStackTrace();
}
return data;
}
private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
if (arr.length == 0) {
return arr;
}
int minValue = arr[0];
int maxValue = arr[0];
for (int value : arr) {
if (value < minValue) {
minValue = value;
} else if (value > maxValue) {
maxValue = value;
}
}
int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
int[][] buckets = new int[bucketCount][0];
// 利用映射函数将数据分配到各个桶中
for (int i = 0; i < arr.length; i++) {
int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
buckets[index] = arrAppend(buckets[index], arr[i]);
}
int arrIndex = 0;
for (int[] bucket : buckets) {
if (bucket.length <= 0) {
continue;
}
// 对每个桶进行排序，这里使用了插入排序
bucket = sortMethod.sortAlgorithm(bucket);
for (int value : bucket) {
arr[arrIndex++] = value;
}
}
return arr;
}
private int[] arrAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
}
11、基数排序
package arithmetic.sort_method;
import arithmetic.test_environment.strategy.SortMethod;
import java.util.Arrays;
public class RadixSort implements SortMethod {
@Override
public int[] sortAlgorithm(int[] data) {
int maxBit = getMaxBit(data);
return radixSort(data, maxBit);
}
private int[] radixSort(int[] data, int max) {
int mod = 10;
int dev = 1;
int index;
for (int i = 0; i < max; i++, dev *= 10, mod *= 10){
//乘以2是用于处理负数情况
int[][] queues = new int[10 * 2][0];
for (int k = 0; k < data.length; k++){
index = data[k] % mod / dev + 10;
queues[index] = queueAppend(queues[index],data[k]);
}
index = 0;
for (int[] queue : queues){
for (int value : queue){
data[index] = value;
index++;
}
}
}
return data;
}
private int getMaxBit(int data[]){
int max = 0;
for (int k = 1; k < data.length; k++){
if (data[max] < data[k])
max = k;
}
return (data[max] + "").length();
}
private int[] queueAppend(int[] queue, int value) {
queue = Arrays.copyOf(queue, queue.length + 1);
queue[queue.length - 1] = value;
return queue;
}
}
测试方法：