包括插入排序、冒泡排序、快速排序、希尔排序、堆排序、归并排序和简单选择排序，用Java实现
public interface arrSorter {
public static <T extends Comparable<T>> void insertSort(T[] t) {}
public static <T extends Comparable<T>> void shellSort(T[] t) {}
public static <T extends Comparable<T>> void BubbleSort(T[] t) {}
public static <T extends Comparable<T>> void quickSort(T[] t) {}
public static <T extends Comparable<T>> void selectSort(T[] t) {}
public static <T extends Comparable<T>> void heapSort(T[] t) {}
public static <T extends Comparable<T>> void mergeSort(T[] t) {}
}
public class arrSort implements arrSorter{
/*
* 插入排序 直接插入排序算法,稳定 升序
*
* @param t 要排序的数组
*/
public static <T extends Comparable<T>> void insertSort(T[] t) {
if (t.length >= 2) {
for (int i = 1; i < t.length; i++) {
T var1 = t[i];// 要插入的变量
for (int j = 0; j < i; j++) {
if (var1.compareTo(t[j]) < 0) {
for (int k = i; k > j; k--) {
t[k] = t[k - 1];
}
t[j] = var1;
break;
}
}
}
}
}
/*
* 插入排序 希尔排序算法,不稳定 升序
*
* @param t 要排序的数组
*/
public static <T extends Comparable<T>> void shellSort(T[] t) {
int gap;// 步长
int n = t.length;
for (gap = n / 2; gap > 0; gap /= 2) {
for (int i = 0; i < gap; i++) {
for (int j = i + gap; j < n; j += gap) {
if (t[j].compareTo(t[j - gap]) < 0) {
T temp = t[j];
int k = j - gap;
while (k >= 0 && t[k].compareTo(temp) > 0) {
t[k + gap] = t[k];
k -= gap;
}
t[k + gap] = temp;
}
}
}
}
}
/*
* 交换排序 冒牌排序 稳定 升序
*
* @param t 要排序的数组
*/
public static <T extends Comparable<T>> void BubbleSort(T[] t) {
// boolean flag;
for (int i = 1; i < t.length; i++) {
for (int j = t.length - 1; j > i; j--) {
if (t[j - 1].compareTo(t[j]) > 0) {
T temp = t[j];
t[j] = t[j - 1];
t[j - 1] = temp;
}
}
}
}
/*
* 交换排序 快速排序 不稳定 升序
*
* @param t 要排序的数组
*/
public static <T extends Comparable<T>> void quickSort(T[] t) {
preQuickSort(t, 0, t.length - 1);
}
private static <T extends Comparable<T>> void preQuickSort(T[] t, int l, int r) {
int left = l, right = r;
if (left <= right) {
T temp = t[left];// 以第一个元素为基准
while (left != right) {
while (right > left && t[right].compareTo(temp) >= 0)
right--;// 从右往左扫描，找到第一个比基准元素小的元素
t[left] = t[right];
while (left < right && t[left].compareTo(temp) <= 0)
left++;// 从左往右扫描，找到第一个比基准元素大的元素
t[right] = t[left];
}
t[right] = temp;// 基准元素归位
preQuickSort(t, l, left - 1); // 对基准元素左边的元素进行递归排序
preQuickSort(t, right + 1, r); // 对基准元素右边的进行递归排序
}
}
/*
* 选择排序 简单选择排序 不稳定 升序
*
* @param t 要排序的数组
*/
public static <T extends Comparable<T>> void selectSort(T[] t) {
for (int i = 0; i < t.length; i++) {
int min = i;
for (int j = i; j < t.length; j++) {
if (t[min].compareTo(t[j]) > 0)
min = j;
}
T temp = t[min];
t[min] = t[i];
t[i] = temp;
}
}
/*
* 选择排序 堆排序，基于最小队 不稳定 升序
*
* @param t 要排序的数组
*/
public static <T extends Comparable<T>> void heapSort(T[] t) {
for (int i = t.length / 2 - 1; i >= 0; i--)
adjustHeap(t, i, t.length - 1);
for (int i = t.length - 1; i > 0; i--) {
T temp = t[0];
t[0] = t[i];
t[i] = temp;
adjustHeap(t, 0, i - 1);
}
}
/*
* 最小堆的调整过程
*
* @param t 要排序的数组
*
* @param start 调节点的起始位置，一般为0，即从第一个节点开始
*
* @param end 截止范围，一般为最后一个节点的索引
*/
private static <T extends Comparable<T>> void adjustHeap(T[] t, int start, int end) {
int cur = start, left = 2 * start + 1;
T temp = t[cur];
for (; left < end; cur = left, left = 2 * left + 1) {
if (left < end && t[left].compareTo(t[left + 1]) <= 0)
left++;
if (temp.compareTo(t[left]) > 0)
break;
else {
t[cur] = t[left];
t[left] = temp;
}
}
}
/*
* 二路归并排序 稳定 升序
*
* @param t 要排序的数组
*/
public static <T extends Comparable<T>> void mergeSort(T[] t) {
T[] temp = t.clone();
preMergSort(t, 0, t.length - 1, temp);
}
private static <T extends Comparable<T>> void preMergSort(T[] t, int first, int last, T[] temp) {
if (first < last) {
int mid = (first + last) / 2;
preMergSort(t, first, mid, temp);
preMergSort(t, mid + 1, last, temp);
mergeArr(t, first, mid, last, temp);
}
}
private static <T extends Comparable<T>> void mergeArr(T[] t, int first, int mid, int last, T[] temp) {
int i = first, j = mid + 1, m = mid, n = last, k = 0;
while (i <= m && j <= n) {
if (t[i].compareTo(t[j]) <= 0)
temp[k++] = t[i++];
else
temp[k++] = t[j++];
}
while (i <= m)
temp[k++] = t[i++];
while (j <= n)
temp[k++] = t[j++];
for (i = 0; i < k; i++)
t[first + i] = temp[i];
}
}
