CH8内部排序教程.ppt
文本预览下载声明
Date;;;8.1 排序的基本概念;作为排序依据的键称为“排序码” ：
若是主键，则对于任意待排序列，经排序后得到的结果是唯一的；
若是次键，则排序结果可能不唯一，即排序后的元素位置关系与排序前不一定保持不变。
排序算法的稳定性: 如果在对象序列中有两个对象ri和rj，它们的关键码 ki == kj，且在排序之前，对象ri排在rj前面。如果在排序之后，对象ri一定仍在对象rj的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。;;;;package ch07;
public class RecordNode{
public Comparable key;
public Object element;
public RecordNode(Comparable key){ this.key = key;}
public RecordNode(Comparable key, Object element){
this.key = key; this.element = element;
}
};public class KeyType implements ComparablekeyType{
public int key;
public KeyType(){};
public KeyType(int key) { this.key = key;}
public String toString() { return key + “”; }
public int compareTo(KeyType another) {
int thisVal = this.key;
int anotherVal = another.key;
return (thisVal anotherVal ? -1 : (thisVal == anotherVal ? 0 :1));
}
};public class ElementType{
public String data;
…… // 可以自定义其他数据项
public ElementType(String data) { this.data = data;}
public ElementType() { }
public String toString( ) {
return data;
}
};public class SeqList{
public RecordNode[] r;
public int curlen;
public int maxSize;
public SeqList(int size) {
maxSize = size; this.r = new RecordNode[maxSize]; this.curlen = 0;
}
public void insert(int i, RecordNode x) throws Exception {
if(curlen == r.length ){ throw new Exception(“表已满！！！”); }
if(i 1 || i curlen + 1) {throw new Exception(); } // 0号位置待用（监视哨）
for(int j = curlen; j i; --j) { r[j] = r[j – 1]; }
r[i] =x;
++this.curlen;
}
};
;;;;public void insertSortWithGuard() { // 直接插入排序
int i,j;
for(i = 1; i = this.curlen; ++i) {
r[0] = r[i]; // 设置监视哨
for(j = i - 1; r[0].pareTo(r[j].key) 0; --j) { // r[i] r [j]，r[j]后移
r[j + 1] = r[j];
}
r[j + 1] = r[0]; // r[i]插入到合适位置
}
};;;;;;;;;;public void shellSort(int[] d) { // 希尔排序
Recor
显示全部