Java排序方法
2024-09-01 11:59:16
下面是用JAVA代码实现的数据结构中的7种基本排序算法，希望对你有所帮助。
（1）直接插入排序
/** 直接插入排序 **/
/** 数组是引用类型，元素值将被改变 **/
public static void insertSort(int[] table) {
/** n-1趟扫描 **/
for (int i = 1; i < table.length; i++) {
/** 每趟将table[i]插入到前面已排序的序列中 **/
int temp = table[i], j;
/** 将前面较大元素向后移动 **/
for (j = i - 1; j > -1 && temp < table[j]; j--) {
table[j + 1] = table[j];
}
/** temp值到达插入位置 **/
table[j + 1] = temp;
}
}
（2）希尔排序
<span style="white-space:pre"> </span>/** 希尔排序 **/
public static void shellSort(int[] table) {
/** 控制增量，增量减半，若干趟扫描 **/
for (int delta = table.length / 2; delta > 0; delta /= 2) {
/** 一趟中若干组，每个元素在自己所属组内进行直接插入排序 **/
for (int i = delta; i < table.length; i++) {
/** 当前待插入元素 **/
int temp = table[i];
/** 相距delta远 **/
int j = i - delta;
/** 一组中前面较大的元素向后移动 **/
/** 继续与前面的元素比较 **/
while (j >= 0 && temp < table[j]) {
table[j + delta] = table[j];
j -= delta;
}
/** 插入元素位置 **/
table[j + delta] = temp;
}
}
}
（3）冒泡排序
<span style="white-space:pre"> </span> /** 冒泡排序 **/
public static void bubbleSort(int[] table) {
/** 是否交换的标记 **/
boolean exchange = true;
/** 有交换时再进行下一趟，最多n-1趟 **/
for (int i = 1; i < table.length && exchange; i++) {
/** 假定元素未交换 **/
exchange = false;
/** 一次比较、交换 **/
for (int j = 0; j < table.length - i; j++) {
/** 反序时，交换 **/
if (table[j] > table[j + 1]) {
int temp = table[j];
table[j] = table[j + 1];
table[j + 1] = temp;
/** 有交换 **/
exchange = true;
}
}
}
}
（4）快速排序
<span style="white-space:pre"> </span>/** 快速排序 **/
public static void quickSort(int[] table) {
quickSort(table, 0, table.length - 1);
} /** 一趟快速排序，递归算法 **/
private static void quickSort(int[] table, int low, int high) { // low、high指定序列的下界和上界
/** 序列有效 **/
if (low < high) {
int i = low, j = high;
/** 第一个值作为基准值 **/
int vot = table[i];
/** 一趟排序 **/
while (i != j) {
/** 从后向前寻找较小值 **/
while (i < j && vot <= table[j])
j--;
if (i < j) {
/** 较小元素向前移动 **/
table[i] = table[j];
i++;
}
/** 从前向后寻找较大值 **/
while (i < j && table[i] < vot)
i++;
if (i < j) {
/** 较大元素向后移动 **/
table[j] = table[i];
j--;
}
}
/** 基准值的最终位置 **/
table[i] = vot;
/** 前端子序列再排序 **/
quickSort(table, low, j - 1);
/** 后端子序列再排序 **/
quickSort(table, i + 1, high);
}
}
（5）直接选择排序
<span style="white-space:pre"> </span>/** 直接选择排序 **/
public static void selectSort(int[] table) {
/** n-1趟排序 **/
for (int i = 0; i < table.length - 1; i++) {
/** 每趟在从table[i]开始的子序列中寻找最小元素 **/
/** 设第i个数据元素最小 **/
int min = i;
/** 在子序列中查找最小值 **/
for (int j = i + 1; j < table.length; j++)
if (table[j] < table[min])
/** 记住最小元素下标 **/
min = j;
/** 将本趟最小元素交换到前边 **/
if (min != i) {
int temp = table[i];
table[i] = table[min];
table[min] = temp;
}
}
}
（6）堆排序
<span style="white-space:pre"> </span>/** 堆排序 **/
public static void heapSort(int[] table) {
int n = table.length;
/** 创建最小堆 **/
for (int j = n / 2 - 1; j >= 0; j--)
sift(table, j, n - 1);
/** 每趟将最小值交换到后面，再调整成堆 **/
for (int j = n - 1; j > 0; j--) {
int temp = table[0];
table[0] = table[j];
table[j] = temp;
sift(table, 0, j - 1);
}
} /** 将以low为根的子树调整成最小堆 **/
private static void sift(int[] table, int low, int high) {
/** low、high是序列下界和上界 **/
/** 子树的根 **/
int i = low;
/** j为i结点的左孩子 **/
int j = 2 * i + 1;
/** 获得第i个元素的值 **/
int temp = table[i];
/** 沿较小值孩子结点向下筛选 **/
while (j <= high) {
/** 数组元素比较（改成<为最大堆） **/
if (j < high && table[j] > table[j + 1])
/** j为左右孩子的较小者 **/
j++;
/** 若父母结点值较大（改成<为最大堆） **/
if (temp > table[j]) {
/** 孩子结点中的较小值上移 **/
table[i] = table[j];
/** i、j向下一层 **/
i = j;
j = 2 * i + 1;
} else
j = high + 1;
}
/** 当前子树的原根值调整后的位置 **/
table[i] = temp;
}
（7）归并排序
<span style="white-space:pre"> </span>/** 归并排序 **/
public static void mergeSort(int[] X) {
/** 已排序的子序列长度，初值为1 **/
int n = 1;
/** Y数组长度同X数组 **/
int[] Y = new int[X.length];
do {
/** 一趟归并，将X数组中各子序列归并到Y中 **/
mergepass(X, Y, n);
/** 子序列长度加倍 **/
n *= 2; if (n < X.length) {
/** 将Y数组中各子序列再归并到X中 **/
mergepass(Y, X, n);
n *= 2;
}
} while (n < X.length);
} /** 一趟归并 **/
private static void mergepass(int[] X, int[] Y, int n) {
int i = 0;
while (i < X.length - 2 * n + 1) {
merge(X, Y, i, i + n, n);
i += 2 * n;
}
if (i + n < X.length)
/** 再一次归并 **/
merge(X, Y, i, i + n, n);
else
/** 将X剩余元素复制到Y中 **/
for (int j = i; j < X.length; j++)
Y[j] = X[j];
} /** 一次归并 **/
private static void merge(int[] X, int[] Y, int m, int r, int n) {
int i = m, j = r, k = m;
/** 将X中两个相邻子序列归并到Y中 **/
while (i < r && j < r + n && j < X.length)
/** 较小值复制到Y中 **/
if (X[i] < X[j])
Y[k++] = X[i++];
else
Y[k++] = X[j++];
/** 将前一个子序列剩余元素复制到Y中 **/
while (i < r)
Y[k++] = X[i++];
/** 将后一个子序列剩余元素复制到Y中 **/
while (j < r + n && j < X.length)
Y[k++] = X[j++];
}
最新文章
- QQ拼音输入法 该到放弃的时候了
- iOS开发中常用方法调用顺序
- iOS 中使用Block时需要注意的retain circle
- Open Sourcing Kafka Monitor
- SaltStack 入门(赵班长)
- android学习日记13--数据存储之ContentProvide
- http协议学习（一）http状态
- Log4net日志组件使用
- 二.ubuntu14.04 3D特效设置
- java多线程学习（一）
- Android中使用开源框架Fresco处理图片
- 每天一个Linux命令（23）--linux 目录结构（二）
- Java web AJAX入门
- linux修改root账户的用户名所得的教训
- Java 读书笔记 (七) 变量
- jQuery(九)、ajax对象操作
- Kubernetes移除node节点
- golang 常用的正则查找与替换
- SQL 连接操作 及 查询分析
- P1077 摆花