鏁版嵁缁撴瀯璇剧▼璁捐�℃姤鍛�---鍑犵�嶆帓搴忕畻娉曠殑婕旂�?闄勬簮浠ｇ爜) - 鐧惧害鏂囧簱

素向后移一个位置，当找到插入位置后就将arr[i-1]插入，就完成了arr[0],arr[1],…,arr[n-1]的排序。

伪代码如下

template //直接插入排序 void sortlist::insertionsort() {

type temp; int j;

for(int i=1;i<=currentsize-1;i++) {

temp=arr[i];j=i-1;

while(j>=0&&temp

cout<<\第\<<++num<<\趟排序结果为:\; for(int t=0;t

num=0; }

<3>折半插入排序

折半插入排序的基本思想：设在排序表中有n个数据元素arr[0],arr[1],…,arr[n-1]。其中，arr[0],arr[1],…,arr[n-1]是已经排好序的部分数据元素序列，在插入arr[i]时，利用折半查找方法寻找arr[i]的插入位置。折半插入排序方法只能在顺序表存储结构实现。 伪代码如下：

template //折半插入排序 void sortlist::binaryinsertsort() {

type temp;

int left,right;

for(int i=1;i

left=0;right=i-1;temp=arr[i]; while(left<=right)//找插入位置 {

int mid=(left+right)/2;

if(temp

for(int k=i-1;k>=left;k--)//向后移动 arr[k+1]=arr[k];

arr[left]=temp;

cout<<\第\<<++num<<\趟排序结果为:\; for(int t=0;t

num=0; }

<4>冒泡排序

冒泡排序的基本思想是：设排序表中有n个数据元素。首先对排序表中第一，二个数据元素的关键字arr[0]和arr[1]进行比较。如果前者大于后者，则进行交换；然后对第二，三个数据做同样的处理；重复此过程直到处理完最后两个相邻的数据元素。我们称之为一趟冒泡，它将关键字最大的元素移到排序表的最后一个位置，其他数据元素一般也都向排序的最终位置移动。然后进行第二趟排序，对排序表中前n-1个元素进行与上述同样的操作，其结果使整个排序表中关键字次大的数据元素被移到arr[n-2]的位置。如此最多做n-1趟冒泡就能把所有数据元素排好序。 伪代码如下：

template //冒泡排序 void sortlist:: bubblesort() {

int i=1;

int finish=0;//0表示还没有排好序 while(i

finish=1;//排序结束标志置为,假定已经排好序 for(int j=0;jarr[j+1])//逆序 {

swap(arr[j],arr[j+1]);//相邻元素交换位置 finish=0;

}//排序结束标志置为,表示本趟发生了交换，说明还没有排好序 i++;

cout<<\第\<<++num<<\趟排序结果为:\; for(int t=0;t

num=0; }

<5>简单选择排序（直接选择排序）

直接选择排序的算法基本思想是： a)开始时设i的初始值为0。

b)如果i

c)若arr[k]不是这组数据元素中的第一个数据元素（i≠k），则将arr[k]与arr[i]这两数据元素的位置对调； d)令i=i+1转步骤 b)。

伪代码如下：

template

void sortlist::selectsort()//简单选择排序 {

int k;

for(int i=0;i<=currentsize-1;i++) {

k=i;

for(int j=i+1;j

k=j;//k 指示当前序列中最小者的位置 if(k!=i)//最小关键字的数据元素位置不等于i swap(arr[i],arr[k]);

cout<<\第\<<++num<<\趟排序结果为:\; for(int t=0;t

num=0; }

<6>快速排序

快速排序（Quick Sort）又被称做分区交换排序，这是一种平均性能非常好的排序方法。 其算法基本思想是：任取排序表中的某个数据元素(例如取第一个数据元素)作为基准，按照该数据元素的关键字大小，将整个排序表划分为左右两个子表： 左侧子表中所有数据元素的关键字都小于基准数据元素的关键字。右侧子表中所有数据元素的关键字都大于或等于基准数据元素的关键字，基准数据元素则排在这两个子表中间(这也是该数据元素最终应安放的位置)，然后分别对这两个子表重复施行上述方法的快速排序，直到所有的子表长度为1，则排序结束。

伪代码如下：

template //快速排序

void sortlist::quicksort(int low,int high)//在待排序区间[low,high]上，递归地进行快速排序 {

int i=low,j=high;

type temp=arr[low];//取区间第一个位置为基准位置 if(i

{

while(i

while(i

if(i=arr[i])i++;

if(i

}

arr[i]=temp;//将基准元素就位

cout<<\第\<<++x<<\趟排序结果为:\; for(int t=0;t

quicksort(low,i-1);//在左子区间递归进行快速排序 quicksort(i+1,high);//在右子区间递归进行快速排序 } }

<7>堆排序（包括建立最大堆和堆排序两个过程） 堆排序算法的基本思想是：

a.对排序表中的数据元素，利用堆的调整算法形成初始堆。 b.输出堆顶元素。

c.对剩余元素重新调整形成堆。

d.重复执行第b、c步，直到所有数据元素被输出。

(1)建立最大堆的伪代码如下：

template //建立最大堆

void sortlist::filterdown(const int start)

{//向下调整使从start开始到currentsize-1为止的子表成为最大堆 int i=start,j=2*i+1;//j为i的左孩子 int tablesize=currentsize; type temp=arr[i];

while(j<=currentsize-1) {

if(j=arr[j])break;

else{arr[i]=arr[j];i=j;j=2*j+1; } }

arr[i]=temp; }