素向后移一个位置,当找到插入位置后就将arr[i-1]插入,就完成了arr[0],arr[1],…,arr[n-1]的排序。
伪代码如下
template
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
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