基于array的序列和排序算法学习笔记

有两种基本类型:

无序序列: 单位不按照特定顺序放置

有序序列: 单位按照字母顺序或者数字顺序放置

例子：无序序列

我们直接来看删除操作

/*这里是重点.无序序列取出单位的方法很特别：首先遍历序列并找出所要取掉的单位，然后使用最后单位代替它，最后擦除最后单位。这个过程的程序效率用Big-O表示是N。*/

void List::Delete(/* in */ ItemType item)

// Precondition:

// length > 0 && item is assigned

// Postcondition:

// If item is in data array

// First occurrence of item is removed from the list; and

// length is updated;

// else

// no change to the list.

{

int index = 0;

// search for the item

while (index < length && item != data[index])

index++;

if (index < length) { // if the item is found

data[index] = data[length-1]; // replace the item

length–;

}

下面是有序序列:

直接看重点insert和delete

Insert序列原理就是倒序地遍历序列，同时把单位右移空出一个位置。把插入的单位和空位前的单位比较，一旦发现插入单位大于空位前单位，立刻停止遍历把单位插入当前空位。

————————————————————

void SortedList::Insert(ItenType item)

{

int index;

// find proper location for new element starting at bottom.

index = length – 1;

while (index>=0 && item<data[index])

{

data[index+1] = data[index]; // shift element down by one position

index–;

}

data[index+1] = item; // store the new item at the found location

length++; // increment the length of the list

}

————————————————————-

Delete操作:

算法概述：通过Binary search找出需要删除的单位，然后把此单位以后的所有单位左移一位，此单位自动被后一个单位覆盖。

————————————————————————-

void SortedList::Delete(ItemType item)

{

int position; // a positive number – position of item, if found

// -1, if not found

int index;

position = BinarySearch(item);

if (position >= 0) {

// shift up elements that follow deleted element in sorted list

for (index=position; index<length; index++)

data[index] = data[index+1];

length–;

}

————————————————————