排序算法java实现
https://github.com/xiaoyinliuyun/AlgorithmSortTest
插入排序类：
直接插入排序
public class InsertionSorter {
// 4,6,2,1,7,9,8,0,5,3,
// 4,6,2,1,7,9,8,0,5,3,
// 2,4,6,1,7,9,8,0,5,3,
// 1,2,4,6,7,9,8,0,5,3,
// 1,2,4,6,7,9,8,0,5,3,
// 1,2,4,6,7,9,8,0,5,3,
// 1,2,4,6,7,8,9,0,5,3,
// 0,1,2,4,6,7,8,9,5,3,
// 0,1,2,4,5,6,7,8,9,3,
// 0,1,2,3,4,5,6,7,8,9,
/**
* 插入排序 O(n^2) O(n) O(n^2)
* 最好的情况:要排序的表本身就是有序的 比较n-1次 移动0次
* 最坏的情况:待排序表是逆序的 比较（n+2)(n-1)/2次 移动（n+4)(n-1)/2次
* 随机情况:平均比较和移动次数 (n^2)/4
*
* 直接插入排序比冒泡和简单选择排序的性能要好一些
*
* @param a
* @param <AnyType>
*/
public static <AnyType extends Comparable<? super AnyType>> void sort(AnyType[] a) {
ArrayUtils.printArray(a);
int j = 0;
for (int p = 1; p < a.length; p++) {
AnyType tmp = a[p];
for (j = p; j > 0 && tmp.compareTo(a[j - 1]) < 0; j--) {
a[j] = a[j - 1];
}
a[j] = tmp;
// ArrayUtils.printArray(a);
}
}
public static <AnyType extends Comparable<? super AnyType>> void sort(AnyType[] a, int left, int right) {
int j = 0;
for (int p = left + 1; p < right + 1; p++) {
AnyType tmp = a[p];
for (j = p; j > left && tmp.compareTo(a[j - 1]) < 0; j--) {
a[j] = a[j - 1];
}
a[j] = tmp;
}
ArrayUtils.printArray(a);
}
}希尔排序
public class ShellSorter {
/**
* 希尔排序 O(n^1.25)
*
* @param a
* @param <AnyType>
*/
public static <AnyType extends Comparable<? super AnyType>> void sort(AnyType[] a) {
int j = 0;
for (int gap = a.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < a.length; i++) {
AnyType tmp = a[i];
for (j = i; j >= gap && tmp.compareTo(a[j - gap]) < 0; j -= gap) {
a[j] = a[j - gap];
}
a[j] = tmp;
}
}
// printArray(a);
}
}选择排序类
简单选择排序
public class SimpleSelectSorter {
// 0,6,2,1,7,9,8,4,5,3,
// 0,1,2,6,7,9,8,4,5,3,
// 0,1,2,6,7,9,8,4,5,3,
// 0,1,2,3,7,9,8,4,5,6,
// 0,1,2,3,4,9,8,7,5,6,
// 0,1,2,3,4,5,8,7,9,6,
// 0,1,2,3,4,5,6,7,9,8,
// 0,1,2,3,4,5,6,7,9,8,
// 0,1,2,3,4,5,6,7,8,9,
// 0,1,2,3,4,5,6,7,8,9,
/**
* 简单选择排序 O(n^2) O(n^2) O(n^2) O(1) 稳定
* <p/>
* 基本思想 每一趟在 n - i + 1 (i = 1,2,...,n-1) 个记录中选取关键字最小的记录作为 有序序列的第i个记录
* <p/>
* 特点 交换移动的数据相当少 性能上略优于冒泡排序
* 关键字信息量较大时，优势明显（因为移动的次数少）
* <p/>
* 比较：第i趟排序需要进行n-i次关键字的比较 无论最好最差情况比较次数一样多 n(n-1)/2次
* 交换：最好的时候交换 0 次 最差的时候交换 n-1次
*
* @param a
* @param <AnyType>
*/
public static <AnyType extends Comparable<? super AnyType>> void sort(AnyType[] a) {
for (int i = 0, min = 0; i < a.length; i++) {
min = i;
for (int j = i + 1; j < a.length; j++) {
if (a[min].compareTo(a[j]) > 0) {
min = j;
}
}
if (i != min) {
ArrayUtils.swapReferences(a, i, min);
}
// ArrayUtils.printArray(a);
}
}
}堆排序
public class HeapSorter {
public static void heapSort(int[] array) {
if (array == null || array.length <= 1) {
return;
}
buildMaxHeap(array);
for (int i = array.length - 1; i >= 1; i--) {
ArrayUtils.exchangeElements(array, 0, i);
maxHeap(array, i, 0);
}
}
private static void buildMaxHeap(int[] array) {
if (array == null || array.length <= 1) {
return;
}
int half = array.length / 2;
for (int i = half; i >= 0; i--) {
maxHeap(array, array.length, i);
}
}
private static void maxHeap(int[] array, int heapSize, int index) {
int left = index * 2 + 1;
int right = index * 2 + 2;
int largest = index;
if (left < heapSize && array[left] > array[index]) {
largest = left;
}
if (right < heapSize && array[right] > array[largest]) {
largest = right;
}
if (index != largest) {
ArrayUtils.exchangeElements(array, index, largest);
maxHeap(array, heapSize, largest);
}
}
/**
* 堆排序方法 O(nlogn) O(nlogn) O(nlogn) O(1)不稳定 不适合序列个数较少的情况
*
* 对空间要求很少
*
* @param a
* @param <AnyType>
*/
public static <AnyType extends Comparable<? super AnyType>> void sort(AnyType[] a) {
for (int i = a.length / 2 - 1; i >= 0; i--) {
percDown(a, i, a.length);
}
for (int i = a.length - 1; i > 0; i--) {
swapReferences(a, 0, i);
percDown(a, 0, i);
}
}
private static <AnyType extends Comparable<? super AnyType>> void swapReferences(AnyType[] a, int i, int i1) {
AnyType temp = a[i];
a[i] = a[i1];
a[i1] = temp;
}
private static <AnyType extends Comparable<? super AnyType>> void percDown(AnyType[] a, int i, int n) {
int child = 0;
AnyType tmp = null;
for (tmp = a[i]; leftChild(i) < n; i = child) {
child = leftChild(i);
if (child != n - 1 && a[child].compareTo(a[child + 1]) < 0) {
child++;
}
if (tmp.compareTo(a[child]) < 0) {
a[i] = a[child];
} else {
break;
}
}
a[i] = tmp;
}
private static int leftChild(int i) {
return 2 * i + 1;
}
}交换排序类
冒泡排序
public class BubbleSorter {
// 4,6,2,1,7,9,8,0,3,5,
// 4,6,2,1,7,9,0,8,3,5,
// 4,6,2,1,7,0,9,8,3,5,
// 4,6,2,1,0,7,9,8,3,5,
// 4,6,2,0,1,7,9,8,3,5,
// 4,6,0,2,1,7,9,8,3,5,
// 4,0,6,2,1,7,9,8,3,5,
// 0,4,6,2,1,7,9,8,3,5,
// --------------------------
// 0,4,6,2,1,7,9,3,8,5,
// 0,4,6,2,1,7,3,9,8,5,
// 0,4,6,2,1,3,7,9,8,5,
// 0,4,6,1,2,3,7,9,8,5,
// 0,4,1,6,2,3,7,9,8,5,
// 0,1,4,6,2,3,7,9,8,5,
// --------------------------
// 0,1,4,6,2,3,7,9,5,8,
// 0,1,4,6,2,3,7,5,9,8,
// 0,1,4,6,2,3,5,7,9,8,
// 0,1,4,2,6,3,5,7,9,8,
// 0,1,2,4,6,3,5,7,9,8,
// --------------------------
// 0,1,2,4,6,3,5,7,8,9,
// 0,1,2,4,3,6,5,7,8,9,
// 0,1,2,3,4,6,5,7,8,9,
// --------------------------
// 0,1,2,3,4,5,6,7,8,9,
// --------------------------
// --------------------------
/**
* 冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定
* <p/>
* 排序思想 两两比较相邻记录
* 最好情况：本身是有序的 比较n-1次
* 最坏情况：本身是逆序的 比较n(n-1)/2次
* <p/>
* 适用于基本有序的序列或数据量小的
*
* @param a
* @param <AnyType>
*/
public static <AnyType extends Comparable<? super AnyType>> void sort(AnyType[] a) {
// int count = 0;
boolean flag = true;
for (int i = 0; i < a.length && flag; i++) {
flag = false;
for (int j = a.length - 1 - 1; j >= i; j--) {
if (a[j].compareTo(a[j + 1]) > 0) {
ArrayUtils.swapReferences(a, j, j + 1);
// ArrayUtils.printArray(a);
flag = true;
// count++;
}
}
// System.out.println("--------------------------");
}
// for (int i = 0; i < a.length; i++) {
// for (int j = 0; j < a.length - 1 - i; j++) {
// if (a[j].compareTo(a[j + 1]) > 0) {
// ArrayUtils.swapReferences(a, j, j + 1);
// ArrayUtils.printArray(a);
// count++;
// }
// }
// }
// System.out.println(count);
}
}快速排序
public class BubbleSorter {
// 4,6,2,1,7,9,8,0,3,5,
// 4,6,2,1,7,9,0,8,3,5,
// 4,6,2,1,7,0,9,8,3,5,
// 4,6,2,1,0,7,9,8,3,5,
// 4,6,2,0,1,7,9,8,3,5,
// 4,6,0,2,1,7,9,8,3,5,
// 4,0,6,2,1,7,9,8,3,5,
// 0,4,6,2,1,7,9,8,3,5,
// --------------------------
// 0,4,6,2,1,7,9,3,8,5,
// 0,4,6,2,1,7,3,9,8,5,
// 0,4,6,2,1,3,7,9,8,5,
// 0,4,6,1,2,3,7,9,8,5,
// 0,4,1,6,2,3,7,9,8,5,
// 0,1,4,6,2,3,7,9,8,5,
// --------------------------
// 0,1,4,6,2,3,7,9,5,8,
// 0,1,4,6,2,3,7,5,9,8,
// 0,1,4,6,2,3,5,7,9,8,
// 0,1,4,2,6,3,5,7,9,8,
// 0,1,2,4,6,3,5,7,9,8,
// --------------------------
// 0,1,2,4,6,3,5,7,8,9,
// 0,1,2,4,3,6,5,7,8,9,
// 0,1,2,3,4,6,5,7,8,9,
// --------------------------
// 0,1,2,3,4,5,6,7,8,9,
// --------------------------
// --------------------------
/**
* 冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定
* <p/>
* 排序思想 两两比较相邻记录
* 最好情况：本身是有序的 比较n-1次
* 最坏情况：本身是逆序的 比较n(n-1)/2次
* <p/>
* 适用于基本有序的序列或数据量小的
*
* @param a
* @param <AnyType>
*/
public static <AnyType extends Comparable<? super AnyType>> void sort(AnyType[] a) {
// int count = 0;
boolean flag = true;
for (int i = 0; i < a.length && flag; i++) {
flag = false;
for (int j = a.length - 1 - 1; j >= i; j--) {
if (a[j].compareTo(a[j + 1]) > 0) {
ArrayUtils.swapReferences(a, j, j + 1);
// ArrayUtils.printArray(a);
flag = true;
// count++;
}
}
// System.out.println("--------------------------");
}
// for (int i = 0; i < a.length; i++) {
// for (int j = 0; j < a.length - 1 - i; j++) {
// if (a[j].compareTo(a[j + 1]) > 0) {
// ArrayUtils.swapReferences(a, j, j + 1);
// ArrayUtils.printArray(a);
// count++;
// }
// }
// }
// System.out.println(count);
}
}归并排序类
归并排序
public class MergeSorter {
/**
* 归并排序方法 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
*
* 对空间复杂度有要求
*
* @param a
* @param <AnyType>
*/
public static <AnyType extends Comparable<? super AnyType>> void sort(AnyType[] a) {
AnyType[] tmpArray = (AnyType[]) new Comparable[a.length];
mergeSort(a, tmpArray, 0, a.length - 1);
}
private static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] a, AnyType[] tmpArray, int left, int right) {
if (left < right) {
int center = (left + right) / 2;
mergeSort(a, tmpArray, left, center);
mergeSort(a, tmpArray, center + 1, right);
merge(a, tmpArray, left, center + 1, right);
}
}
private static <AnyType extends Comparable<? super AnyType>> void merge(AnyType[] a, AnyType[] tmpArray, int leftPos, int rightPos, int rightEnd) {
int leftEnd = rightPos - 1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos + 1;
//Main loop
while (leftPos <= leftEnd && rightPos <= rightEnd) {
if (a[leftPos].compareTo(a[rightPos]) <= 0) {
tmpArray[tmpPos++] = a[leftPos++];
} else {
tmpArray[tmpPos++] = a[rightPos++];
}
}
while (leftPos <= leftEnd) {//拷贝上一半的副本
tmpArray[tmpPos++] = a[leftPos++];
}
while (rightPos <= rightEnd) {//拷贝另一半的副本
tmpArray[tmpPos++] = a[rightPos++];
}
for (int i = 0; i < numElements; i++, rightEnd--) {
a[rightEnd] = tmpArray[rightEnd];
}
}
}附工具类
public class ArrayUtils {
public static void exchangeElements(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
public static <AnyType extends Comparable<? super AnyType>> void swapReferences(AnyType[] a, int i, int i1) {
AnyType temp = a[i];
a[i] = a[i1];
a[i1] = temp;
}
public static <AnyType extends Comparable<? super AnyType>> void printArray(AnyType[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + ",");
}
System.out.println();
}
public static void printArray(int[] array) {
System.out.print("{");
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]);
if (i < array.length - 1) {
System.out.print(", ");
}
}
System.out.println("}");
}
}