数据结构第10章讲解.ppt
文本预览下载声明
第10章 排序;10.1 排序的基本概念 ;;10.2插入排序 ;算法如下：
void InsertSort (DataType a[], int n)
//用直接插入法对a[0]--a[n-1]排序
{
int i, j;
DataType temp;
for(i=0; in-1; i++)
{ temp = a[i+1];
j = i;
while(j -1 temp.key a[j].key)
{ a[j+1] = a[j];
j--;
}
a[j+1] = temp;
}
};算法分析:;{64};2.希尔(shell)排序(又称缩小增量排序);
算法如下：
void ShellSort (DataType a[], int n, int d[], int numOfD)
//用希尔排序法对元素a[0]--a[n-1]排序，d[0]--d[numOfD-1]为希尔增量值
{ int i, j, k, m, span; DataType temp;
? for(m = 0; m numOfD; m++) //共numOfD次循环
{ span = d[m]; //取本次的增量值
for(k = 0; k span; k++) //共span个小组
{
//组内是直接插入排序，区别是每次不是增1而是增span
for(i = k; i n-span; i = i+span) { temp = a[i+span];
j = i;
while(j -1 temp.key a[j].key)
{ a[j+span] = a[j];
j = j-span;
}
a[j+span] = temp;
}
}
}
};65;10.3 选择排序 ;1.直接选择排序;算法如下：
void SelectSort(DataType a[], int n)
{
int i, j, small; DataType temp;
?
for(i = 0; i n-1; i++)
{ small = i; //设第i个数据元素关键字最小
for(j = i+1; j n; j++) //寻找关键字最小的数据元素
if(a[j].key a[small].key) small=j; //记住最小元素的下标
if(small != i) //当最小元素的下标不为i时交换位置
{
temp = a[i];
a[i] = a[small];
a[small] = temp;
}
}
};64;算法分析
时间效率： O(n2)——虽移动次数较少，但比较次数仍多。
空间效率：O(1)——仅用到若干个临时变量。
算法的稳定性：不稳定;2.堆排序 ;10;二、 创建堆 ;void CreatHeap (DataType a[], int n, int h)
{
int i, j, flag;
DataType temp;
? i = h; // i为要建堆的二叉树根结点下标
j = 2*i+1; // j为i的左孩子结点的下标
temp = a[i];
flag = 0;
? while(j n flag !=
显示全部