bool operator==(Element<T>&x) return key ==x.key; /判*this与x相等 bool operator<=(Element<T>&x) return key <=x.key;} /判*this小于或等于x bool operator>=(Element<T>&x) return key >=x.key;} /判*this大于或等于x bool operator>(Element<T>&x) return key x.key; /判*this大于x bool operator<(Element<T>&x) return key x.key; /判*this小于x }; 6
bool operator == (Element<T>& x) { return key == x.key; } //判*this与x相等 bool operator <= (Element<T>& x) { return key <= x.key; } //判*this小于或等于x bool operator >= (Element<T>& x) { return key >= x.key; } //判*this大于或等于x bool operator > (Element<T>& x) { return key > x.key; } //判*this大于x bool operator < (Element<T>& x) { return key < x.key; } //判*this小于x }; 6
template <class T> class dataList{ /川数据表类定义 private: Element <T>*Vector; /存储排序元素的向量 int maxSize; 川向量中最大元素个数 int currentSize; /川当前元素个数 public: datalist(int maxSz=DefaultSize):/构造函数 maxSize(maxSz),currentSize(0) Vector new Element<T>[maxSize];} int Length(return currentSize; 川取表长度 7
template <class T> class dataList{ //数据表类定义 private: Element <T>* Vector; //存储排序元素的向量 int maxSize; //向量中最大元素个数 int currentSize; //当前元素个数 public: datalist (int maxSz = DefaultSize) : //构造函数 maxSize(maxSz), currentSize(0) { Vector = new Element<T>[maxSize]; } int Length() { return currentSize; } //取表长度 7
void Swap (Element<T>&x,Element<T>&y) Element<T>temp =x;x=y;y =temp;} Element<T>&operator (int i) /川取第i个元素 return Vector[i];} int Partition(const int low,const int high); 川快速排序划分 };
void Swap (Element<T>& x, Element<T>& y) { Element<T> temp = x; x = y; y = temp; } Element<T>& operator [](int i) //取第i个元素 { return Vector[i]; } int Partition (const int low, const int high); //快速排序划分 }; 8
插入排序(Insert Sorting) ·基本方法是：每步将一个待排序的元素，按其排序 码大小，插入到前面已经排好序的一组元素的适当 位置上，直到元素全部插入为止。 -直接插入排序 -折半插入排序 希尔排序 9
插入排序 (Insert Sorting) • 基本方法是：每步将一个待排序的元素，按其排序 码大小，插入到前面已经排好序的一组元素的适当 位置上, 直到元素全部插入为止。 – 直接插入排序 – 折半插入排序 – 希尔排序 9
直接插入排序(Insert Sort) 基本思想是： 当插入第i(21)个元素时，前面的V0,V[1小，， V[i-1已经排好序。这时，用V[的排序码与V[i- 1,V[i-2,.…的排序码顺序进行比较，找到插入位 置即将V[插入，原来位置上的元素向后顺移。 10
• 基本思想是 : 当插入第i (i≥1) 个元素时，前面的V[0], V[1], …, V[i-1]已经排好序。这时，用V[i]的排序码与V[i- 1], V[i-2], …的排序码顺序进行比较，找到插入位 置即将V[i]插入，原来位置上的元素向后顺移。 10 直接插入排序 (Insert Sort)