java五种排序算法汇总
java的排序算法工具有哪些?这个工具类简单明了地总结了java的快速排序,希尔排序,插入排序,堆排序,归并排序五种排序算法,代码中并没有对这几种排序算法的一个说明,关于思想部分希望在自行查阅相关说明,这里只是对这几种算法进行一个概括,以供大家使用。
private static > void insertionSort(AnyType[] a, int left, int right) {
int j; // 记录第一个比tmp小的.元素的后边一位的位置
for (int p = left; p <= right; p++) {
AnyType tmp = a[p];
for (j = p; j > left && areTo(a[j - 1]) < 0; j--) {
a[j] = a[j - 1];
}
a[j] = tmp;
}
}
public static > void shellSort(AnyType[] arr) {
int j;
for (int gap = th / 2; gap > 0; gap /= 2) {
for (int i = gap; i < th; i++) {
AnyType tmp = arr[i];
for (j = i; j >= gap && areTo(arr[j - gap]) < 0; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = tmp;
}
}
}
private static int leftChild(int i) {
return i * 2 + 1;
}
private static > void perculateDown(AnyType[] arr, int i, int size) {
AnyType tmp = arr[i];
for (int child; (child = leftChild(i)) < size; i = child) {
if (child != size - 1 && arr[child]areTo(arr[child + 1]) < 0) {
child++;
}
if (areTo(arr[child]) < 0) {
arr[i] = arr[child];
} else {
break;
}
}
arr[i] = tmp;
}
public static > void heapSort(AnyType[] arr) {
for (int i = th / 2; i >= 0; i--) {
perculateDown(arr, i, th);
}
for (int i = th - 1; i >= 0; i--) {
swapReferences(arr, 0, i);
perculateDown(arr, 0, i);
}
}
private static > void swapReferences(AnyType[] arr, int i, int j) {
AnyType tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static > void mergeSort(AnyType[] arr) {
AnyType[] tmp = ((AnyType[]) new Comparable[th]);
mergeSort(arr, 0, th - 1, tmp);
}
private static > void mergeSort(AnyType[] arr, int start, int end, AnyType[] tmp) {
if (start < end) {
int mid = (start + end) >> 1;
mergeSort(arr, start, mid, tmp);
mergeSort(arr, mid + 1, end, tmp);
merge(arr, start, mid, end, tmp);
}
}
private static > void merge(AnyType[] arr, int start, int mid, int end, AnyType[] tmp) {
int i = start, j = mid + 1, k = start;
while (i <= mid && j <= end) {
if (arr[i]areTo(arr[j]) < 0) {
tmp[k++] = arr[i++];
} else {
tmp[k++] = arr[j++];
}
}
while (i <= mid) {
tmp[k++] = arr[i++];
}
while (j <= end) {
tmp[k++] = arr[j++];
}
for (int m = start; m <= end; m++) {
arr[m] = tmp[m];
}
}
public static > void quickSort(AnyType[] arr) {
quickSort(arr, 0, th - 1);
}
private static > void quickSort(AnyType[] arr, int left, int right) {
if (left + LENGTH_DIFF <= right) {
AnyType pivot = medium(arr, left, right);
int i = left, j = right;
while (true) {
while (arr[++i]areTo(pivot) < 0);
while (arr[--j]areTo(pivot) > 0);
if (i < j) {
swapReferences(arr, i, j);
} else {
break;
}
}
swapReferences(arr, i, right);
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
} else {
insertionSort(arr, left, right);
}
}
private static > AnyType medium(AnyType[] arr, int left,
int right) {
int center = (left + right) / 2;
if (arr[center]areTo(arr[left]) < 0) {
swapReferences(arr, center, left);
}
if (arr[left]areTo(arr[right]) > 0) {
swapReferences(arr, left, right);
}
if (arr[center]areTo(arr[right]) < 0) {
swapReferences(arr, center, right);
}
return arr[right];
}
private final static int LENGTH_DIFF = 20;
}
-
2017计算机二级考试C语言冲刺题及答案
好的复习题是备考计算机二级考试C语言的关键,为了让考生更好地复习。本站小编为大家准备了计算机二级C语言冲刺题。欢迎阅读。一、选择题(1)下列关于栈叙述正确的是A)栈顶元素最先能被删除B)栈顶元素最后才能被删除C)栈底元素永远不能被删除D)以上三种说法都不...
-
2016下半年计算机二级VB上机考试答题攻略
计算机等级考试进入冲刺备考阶段,为帮助同学们考过计算机等级考试,本站小编为大家分享的是二级VB上机考试答题攻略——常用算法,希望对同学们考试有所帮助!常用算法熟练地掌握算法原理、编程思想和代码实现,就能够做到举一反三,轻松备考,顺利过关。1.累加...
-
2017年浙江省计算机三级网络技术考试试题
计算机网络包括计算机和网络两部分.其中计算机又称电子计算机,俗称电脑,是一种能够按照程序运行,自动、高速处理海量数据的现代化智能电子设备。下面是小编整理的关于计算机三级网络技术考试试题,欢迎大家参考!1).对于下列说法,错误的是()。协议可以提供可靠的数据...
-
2017年计算机二级MSOffice上机操作题及答案
2017年NCRE继续实施2013年版考试大纲(部分科目有修订),大纲和教材详情可查询本网站大纲教材栏目。下面是小编收集的计算机二级MSOffice上机操作题及答案,希望可以帮助大家!一、字处理题请在【答题】菜单下选择【进入考生文件夹】命令,并按照题目要求完成下面的操...