public class SortTest {
static void swap(Object[] arr, int i, int j) {
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
static String toString(Object[] arr) {
String str = "[";
for (int i = 0; i < arr.length; i++) {
str += " " + arr[i] + " ";
}
str += "]";
return str;
}
static final String sortAndToString(Comparable[] arr, Sorter sorter) {
return toString(sorter.sort(arr));
}
interface Sorter {
Comparable[] sort(Comparable[] arr0);
}
/**
* 冒泡排序：比较相邻的元素。如果第一个比第二个大，就交换他们两个，最大的元素会被排到最后
*/
static class BubbleSort implements Sorter {
@Override
public Comparable[] sort(Comparable[] arr0) {
if (arr0.length < 2) {
return arr0;
}
Comparable[] arr = Arrays.copyOf(arr0, arr0.length);
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < arr.length - i; j++) {
if (arr[j].compareTo(arr[j + 1]) > 0) {
swap(arr, j, j + 1);
}
}
}
return arr;
}
}
/**
* 选择排序：未排序序列中找到最小（大）元素，存放到排序序列的起始位置
*/
static class selectionSort implements Sorter {
@Override
public Comparable[] sort(Comparable[] arr0) {
if (arr0.length < 2) {
return arr0;
}
Comparable[] arr = Arrays.copyOf(arr0, arr0.length);
int index;
for (int i = 0; i < arr.length - 1; i++) {
index = i;
for (int j = i + 1; j < arr.length; j++) {
index = arr[index].compareTo(arr[j]) > 0 ? j : index;
}
if (index != i) {
swap(arr, i, index);
}
}
return arr;
}
}
/**
* 插入排序：将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
*
*/
static class InsertSort implements Sorter {
@Override
public Comparable[] sort(Comparable[] arr0) {
if (arr0.length < 2) {
return arr0;
}
Comparable[] arr = Arrays.copyOf(arr0, arr0.length);
for (int i = 1; i < arr.length; i++) {
Comparable temp = arr[i];
int j = i;
while (j > 0 && temp.compareTo(arr[j - 1]) < 0) {
arr[j] = arr[--j];
}
arr[j] = temp;
}
return arr;
}
}
/**
* 希尔排序：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
*/
static class ShellSort implements Sorter {
@Override
public Comparable[] sort(Comparable[] arr0) {
if (arr0.length < 2) {
return arr0;
}
Comparable[] arr = Arrays.copyOf(arr0, arr0.length);
for (int step = arr0.length / 2; step >= 1; step /= 2) {
for (int i = step; i < arr0.length; i++) {
Comparable temp = arr[i];
int j = i - step;
while (j >= 0 && temp.compareTo(arr[j]) < 0) {
arr[j + step] = arr[j];
j -= step;
}
arr[j + step] = temp;
}
}
return arr;
}
}
/**
* 归并排序：建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。
* 归并排序的实现有两种方法：1.自上而下的递归；2.自下而上的迭代。
*/
static class MergeSort implements Sorter {
@Override
public Comparable[] sort(Comparable[] arr0) {
if (arr0.length < 2) {
return arr0;
}
Comparable[] arr = Arrays.copyOf(arr0, arr0.length);
Comparable[] temp = new Comparable[arr.length];
sort(arr, 0, arr.length - 1, temp);
return arr;
}
/**
* @param arr 排序的数组
* @param left 左边界索引
* @param right 右边界索引
* @param temp 临时数组
*/
private void sort(Comparable[] arr, int left, int right, Comparable[] temp) {
if (left < right) {
int mid = (left + right) / 2;
sort(arr, left, mid, temp);
sort(arr, mid + 1, right, temp);
merge(arr, left, right, temp);
}
}
private void merge(Comparable[] arr, int left, int right, Comparable[] temp) {
int mid = (left + right) / 2;
int i = left; //左序列指针
int j = mid + 1; // 右序列指针
int t = 0;
while (i<= mid && j <= right) {
if (arr[i].compareTo(arr[j]) <= 0) {
temp[t++] = arr[i++];
} else {
temp[t++] = arr[j++];
}
}
while (i <= mid) {
temp[t++] = arr[i++];
}
while (j <= right) {
temp[t++] = arr[j++];
}
t = 0;
while (left <= right) {
arr[left++] = temp[t++];
}
}
}
/**
* 归并排序：迭代方式
*/
static class MyMergeSort implements Sorter {
@Override
public Comparable[] sort(Comparable[] arr0) {
if (arr0.length < 2) {
return arr0;
}
Comparable[] arr = Arrays.copyOf(arr0, arr0.length);
Comparable[] temp = new Comparable[arr.length];
for (int step = 1; step < arr.length; step += step) {
for (int left = 0; left < arr.length; left += 2 * step) {
int mid = arr.length - left > step ? left + step : arr.length;
int right = arr.length - mid > step ? mid + step : arr.length;
int i = left; //左序列指针
int j = mid; //右序列指针
int t = left;
while (i < mid && j < right) {
if (arr[i].compareTo(arr[j]) <= 0) {
temp[t++] = arr[i++];
} else {
temp[t++] = arr[j++];
}
}
while (i < mid) {
temp[t++] = arr[i++];
}
while (j < right) {
temp[t++] = arr[j++];
}
}
// 交换arr和temp
Comparable[] t = arr;
arr = temp;
temp = t;
}
return arr;
}
}
/**
* 快速排序
*/
static class QuickSort implements Sorter {
@Override
public Comparable[] sort(Comparable[] arr0) {
if (arr0.length < 2) {
return arr0;
}
Comparable[] arr = Arrays.copyOf(arr0, arr0.length);
sort(arr, 0, arr.length - 1);
return arr;
}
private void sort(Comparable[] arr, int left, int right) {
if (left >= right) {
return;
}
int start = left;
int end = right;
Comparable pivot = arr[start]; //初始化start为基准位
while (start != end) {
while (start != end && pivot.compareTo(arr[end]) <= 0) { //从右往左找到比基准小的对象end
end--;
}
if (start != end) {
arr[start++] = arr[end]; //将end放到基准位，因为end已经与基准比较过，所以start + 1
//这里有一个隐含的变化，end被放到了start位置，end此时变为基准位
}
while (start != end && pivot.compareTo(arr[start]) >= 0) { //然后从左往右找到比基准大的对象end
start++;
}
if (start != end) {
arr[end--] = arr[start]; // 将start放到基准位end，因为start已经与基准比较过，所以end - 1
//同上，start被放到了end位置，start此时变为基准位
}
}
arr[start] = pivot; //当start与end相等，start或者end就是基准位，即基准左边都小于基准，基准右边都大于基准
sort(arr, left, start - 1); //递归排序基准左边数组
sort(arr, start + 1, right);//递归排序基准右边数组
}
}
/**
* 堆排序：根据大根堆的特性来排序，子结点的键值或索引总是小于（或者大于）它的父节点。
*/
static class HeapSort implements Sorter {
@Override
public Comparable[] sort(Comparable[] arr0) {
if (arr0.length < 2) {
return arr0;
}
Comparable[] arr = Arrays.copyOf(arr0, arr0.length);
buildMaxHeap(arr);
for (int i = arr.length - 1; i >= 0; i--) {
swap(arr, 0, i); //将最大根换到最后
adjustMaxHeap(arr, i, 0); //调整大根堆，除了最后已经排好序的元素
}
return arr;
}
private static void buildMaxHeap(Comparable[] arr) {//构造一个大根堆
for (int i = arr.length/2 - 1; i >= 0; i--) {//从最后一层
adjustMaxHeap(arr, arr.length, i);
}
}
private static void adjustMaxHeap(Comparable[] arr, int size, int i) {//调整大顶堆，使每个子树的父节点都是当前子树的最大值。
int left = 2 * i + 1;
int right = 2 * i + 2;
int max = i; //最大值的索引，默认为父节点
if (left < size && arr[left].compareTo(arr[max]) > 0) { //左子节点与父节点比大小
max = left;
}
if (right < size && arr[right].compareTo(arr[max]) > 0) { //右子节点与父节点比大小
max = right;
}
if (max != i) { //最大点是子节点
swap(arr, max, i); //与子节点交换位置
adjustMaxHeap(arr, size, max); //因为子节点发生了改变，要调整子节点
}
}
}
static boolean printErr(String... s) {
for (int i = 1; i < s.length; i++) {
if (!s[i].equals(s[i - 1])) {
System.out.println(i);
System.out.println(s[i - 1]);
System.out.println(s[i]);
return true;
}
}
return false;
}
public static void main(String[] args) {
int n = 100;
Random random = new Random();
Integer[] arr = new Integer[n];
for (int i = 0; i < n; i++) {
arr[i] = random.nextInt(n);
}
for (int i = 0; i < 100000; i++) {
String s1 = sortAndToString(arr, new BubbleSort());
String s2 = sortAndToString(arr, new selectionSort());
String s3 = sortAndToString(arr, new InsertSort());
String s4 = sortAndToString(arr, new ShellSort());
String s5 = sortAndToString(arr, new MergeSort());
String s6 = sortAndToString(arr, new MyMergeSort());
String s7 = sortAndToString(arr, new QuickSort());
String s8 = sortAndToString(arr, new HeapSort());
if (printErr(s1, s2, s3, s4, s5, s6, s7, s8)) {
System.out.println(toString(arr) + "原数组，出错啦");
return;
}
}
}
}
网友评论