- [ package 排序;
public class SqList {
public RecordNode[] r; // 顺序表记录结点数组
public int curlen; // 顺序表长度,即记录个数
public SqList() { }// 顺序表的构造方法，构造一个存储空间容量为 maxSize 的顺序表
public SqList(int maxSize) {
this.r = new RecordNode[maxSize]; // 为顺序表分配 maxSize 个存储单元
this.curlen = 0; // 置顺序表的当前长度为 0
}
// 求顺序表中的数据元素个数并由函数返回其值
public int length() {
return curlen; // 返回顺序表的当前长度
}// 在当前顺序表的第 i 个结点之前插入一个 RecordNode 类型的结点 x
public void insert(int i, RecordNode x) throws Exception {
if (curlen == r.length) { // 判断顺序表是否已满
throw new Exception("顺序表已满");
}
if (i < 0 || i > curlen) { // i 小于 0 或者大于表长
throw new Exception("插入位置不合理");
}
for (int j = curlen; j > i; j--) {
r[j] = r[j - 1]; // 插入位置及之后的元素后移
}
r[i] = x; // 插入 x
this.curlen++; // 表长度增 1
}
public void display() { // 输出顺序表元素
for (int i = 0; i < this.curlen; i++) {
System.out.print(" " + r[i].toString());
}
System.out.println();
}
// 不带监视哨的直接插入排序算法
public void insertSort() {
RecordNode temp;
int i, j;
for (i = 1; i < this.curlen; i++) {// n-1趟扫描
temp = r[i]; // 将待插入的第i条记录暂存在temp中
for (j = i - 1; j >= 0 && temp.getKey()<r[j].getKey(); j--) { // 将前面比r[i]大的记录向后移动
r[j + 1] = r[j];
}
r[j + 1] = temp;
}
}
// r[i]插入到第j+1个位置
// 希尔排序算法
public void shellSort(int[] d) { // d[]为增量数组
RecordNode temp;
int i, j;
System.out.println("希尔排序");
// 控制增量，增量减半，若干趟扫描
for (int k = 0; k < d.length; k++) {
// 一趟中若干子表，每个记录在自己所属子表内进行直接插入排序
int dk = d[k];
for (i = dk; i < this.curlen; i++) {
temp = r[i];
for (j = i - dk; j >= 0 &&
temp.getKey()<r[j].getKey(); j -= dk) {
r[j + dk] = r[j];
}
r[j + dk] = temp;
}
}
}
// 冒泡排序算法
public void bubbleSort() {
RecordNode temp; // 辅助结点
boolean flag = true; // 是否交换的标记
for (int i = 1; i < this.curlen && flag; i++) {
// 有交换时再进行下一趟，最多n-1趟
flag = false; // 假定元素未交换
for (int j = 0; j < this.curlen - i; j++) { // 一次比较、交换
if (r[j].getKey()>r[j + 1].getKey()) { // 逆序时，交换
temp = r[j];
r[j] = r[j + 1];
r[j + 1] = temp;
flag = true;
}
}
// System.out.print("第" + i + "趟: "); display();
}
}
// 一趟快速排序
// 交换排序表 r[i..j]的记录，使支点记录到位，并返回其所在位置
// 此时，在支点之前(后)的记录关键字均不大于(小于)它
public int Partition(int i, int j) {
RecordNode pivot = r[i]; // 将第1个记录作为枢轴
while (i<j) {
while(i<j&& r[j].getKey ()>=pivot.getKey ())
-- j; // 从右向左搜索
if (i<j) { r[i] = r[j]; i++;}
while (i<j && r[i] .getKey ()<=pivot.getKey ())
++ i; // 从左向右搜索
if (i<j) {r[j] = r[i]; j--;}
}
r[i] =pivot;
return i;
}
// 递归形式的快速排序算法
// 对子表 r[low..high]快速排序
public void qSort(int low, int high) {
if (low < high) {
int pivotloc = Partition (low, high);
//一趟排序，将排序表分为两部分
qSort(low, pivotloc - 1);
//低子表递归排序
qSort( pivotloc + 1, high);
//高子表递归排序
}
}
// 顺序表快速排序算法
public void quickSort() {
qSort(0, curlen-1);
}
//直接选择排序
public void selectSort() {
RecordNode temp; // 辅助结点
for (int i = 0; i < this.curlen - 1; i++) {// n-1趟排序
// 每趟在从r[i]开始的子序列中寻找最小元素
int min = i; // 设第i条记录的关键字最小
for (int j = i + 1; j < this.curlen; j++) {
// 在子序列中选择关键字最小的记录
if (r[j].getKey()<r[min].getKey()) {
min = j; // 记住关键字最小记录的下标
}
}
if (min != i) { // 将本趟关键字最小的记录与第i条记录交换
temp = r[i];
r[i] = r[min];
r[min] = temp;
}// System.out.print("第" + (i + 1) + "趟: "); display();
}
}
//将以筛选法调整堆算法
// 将以 low 为根的子树调整成小顶堆，low、high 是序列下界和上界
public void sift(int low, int high) {
int i = low; // 子树的根
int j = 2 * i + 1; // j为i结点的左chil
RecordNode temp = r[i];
while (j < high) { // 沿较小值chil结点向下筛选
if (j < high - 1 && r[j].getKey()>r[j + 1].getKey()) {
j++; // 数组元素比较,j为左右chil的较小者
}
if (temp.getKey()>r[j].getKey()) { // 若父母结点值较大
r[i] = r[j]; // chil结点中的较小值上移
i = j;
j = 2 * i + 1;
} else {
j = high + 1; } // 退出循环
}
r[i] = temp; // 当前子树的原根值调整后的位置
}
//堆排序算法
public void heapSort() {
int n = this.curlen;
RecordNode temp;
for (int i = n / 2 - 1; i >= 0; i--) //创建堆
sift (i, n); //算法7.1
//每趟将最小关键字值交换到后面，再调整成堆
for (int i = n - 1; i > 0; i--){
temp = r[0];
r[0] = r[i];
r[i] = temp;
sift(0, i);
}
}
}
]
每个算法输出排序过程
我想要把这个排序的中间的过程，把它输出来
