排序与查找问题

设有8个待排序的记录，其关键字分为别：

49.38.65.97.76.13.27.49

对以上关键字分别进行直接插入排序和折半插入排序。

各位大侠帮帮忙···

折半插入排序的基本条件是往一个有序的数列中插入数据，可是你给的数据不是有序的。

这事我以前编的：用了五种排序方法（简单插入排序、冒泡排序、快速排序、归并排序、堆排序）

你可以自己改造一下

#include<stdio.h>

#include<stdlib.h>

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR

#define OVERFLOW -2

#define MAXSIZE 20 //一个用作示例的小顺序表的最大长度

#define LT(a,b) ((a)<(b))

#define LQ(a,b) ((a)<=(b))

typedef int KeyType;//定义关键字类型为整数类型

typedef int InfoType;

typedef struct

{

KeyType key;//关键字项

InfoType otherinfo;//其他数据项

}RedType;//记录类型

typedef struct

{

RedType r[MAXSIZE+1];//r[0]闲置或用作哨兵单元

int length;//顺序表长度

}SqList;//顺序表类型

int InitList_Sq(SqList &L)

{//构造一个空的顺序表L。

int i;

printf("请输入待排序的记录的个数：");

scanf("%d",&L.length);

printf("请输入待排序的记录的关键字（整型数）：");

for(i=1;i<=L.length;i++)

scanf("%d",&L.r[i]);

return OK;

}

void Print_Sq(SqList &L) //输出

{

int i;

for(i=1;i<=L.length;i++)

{

printf("%4d",L.r[i]);

}

printf("\n");

}

//------------插入排序---

void InsertSort(SqList &L)

{//对顺序表L作直接插入排序。

int i,j;

for(i=2;i<=L.length;++i)

if(LT(L.r[i].key,L.r[i-1].key))//“<”，需将L.r[i]插入有序子表

{

L.r[0]=L.r[i];//复制为哨兵

L.r[i]=L.r[i-1];

for(j=i-2;LT(L.r[0].key,L.r[j].key);--j)

L.r[j+1]=L.r[j];//记录后移

L.r[j+1]=L.r[0];//插入到正确位置

}

}

//--------------冒泡排序---

void BubbleSort(SqList &L)

{//L.r是待排序的文件，采用自下向上扫描，对L.r做冒泡排序

int i,j;

int exchange; // 交换标志

for(i=1;i<L.length;i++)

{// 最多做 n-1 趟排序

exchange=FALSE; // 本趟排序开始前，交换标志应为假

for(j=L.length-1;j>=i;j--) // 对当前无序区 R[i..n] 自下向上扫描

if(LT(L.r[j+1].key,L.r[j].key))

{ // 交换记录

L.r[0]=L.r[j+1]; //L.r[0]不是哨兵，仅做暂存单元

L.r[j+1]=L.r[j];

L.r[j]=L.r[0];

exchange=TRUE; // 发生了交换，故将交换标志置为真

}

if(!exchange) // 本趟排序未发生交换，提前终止算法

return;

}

}

//-----------快速排序---

int Partition(SqList &L,int low,int high)

{//交换顺序表L中子表r[low..high]的记录，枢轴记录到位，并返回其所在位置，此时

//在它之前（后）的记录均不大（小）于它。

KeyType pivotkey;

L.r[0]=L.r[low];//用子表的第一个记录作枢轴记录

pivotkey=L.r[low].key;//枢轴记录关键字

while(low<high)

{//从表的两端交替地向中间扫描

while (low<high&&L.r[high].key>=pivotkey) --high;

L.r[low]=L.r[high];//将比枢轴记录小的记录移到低端

while (low<high&&L.r[low].key<=pivotkey) ++low;

L.r[high]=L.r[low];//将比枢轴记录大的记录移到高端

}

L.r[low]=L.r[0];//枢轴记录到位

return low;//返回枢轴位置

}

void QSort(SqList &L,int low,int high)

{//对顺序表L中的子序列L.r[low..high]进行快速排序

int pivotloc;

if(low<high)

{//长度大于1

pivotloc=Partition(L,low,high);//将L.r[low..high]一分为二

QSort(L,low,pivotloc-1);//对低子表递归排序pivotloc是枢轴位置

QSort(L,pivotloc+1,high);//对高子表递归排序

}

}

void QuickSort(SqList &L)

{//对顺序表L作快速排序。

QSort(L,1,L.length);

}

//----------归并排序---

void Merge(RedType SR[],RedType TR[],int i,int m,int n)

{//将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]

int j,k;

for(j=m+1,k=i;i<=m&&j<=n;++k)

{//将SR中记录由小到大地并入TR

if LQ(SR[i].key,SR[j].key) TR[k]=SR[i++];

else TR[k]=SR[j++];

}

if(i<=m)//TR[k..n]=SR[i..m];将剩余的SR[i..m]复制到TR

while(k<=n&&i<=m) TR[k++]=SR[i++];

if(j<=n)//将剩余的SR[j..n]复制到TR

while(k<=n&&j<=n) TR[k++]=SR[j++];

}

void MSort(RedType SR[],RedType TR1[],int s,int t)

{//将SR[s..t]归并排序为TR1[s..t]。

int m;

RedType TR2[20];

if(s==t) TR1[t] = SR[s];

else

{

m=(s+t)/2;//将SR[s..t]平分为SR[s..m]和SR[m+1..t]

MSort(SR,TR2,s,m);//递归地将SR[s..m]归并为有序的TR2[s..m]

MSort(SR,TR2,m+1,t);//将SR[m+1..t]归并为有序的TR2[m+1..t]

Merge(TR2,TR1,s,m,t);//将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]

}

}

void MergeSort(SqList &L)

{// 对顺序表L作归并排序。

MSort(L.r, L.r, 1, L.length);

}

//-----------堆排序---

void HeapAdjust(SqList &H,int s,int m)

{//已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义，

//本函数调整H.r[s]的关键字，使H.r[s..m]成为一个大顶堆

//（对其中记录的关键字而言）

int j;

RedType rc;

rc=H.r[s];

for(j=2*s;j<=m;j*=2)

{//沿key较大的孩子结点向下筛选

if(j<m&&H.r[j].key<H.r[j+1].key) ++j;//j为key较大的记录的下标

if(rc.key>=H.r[j].key) break;//rc应插入在位置s上

H.r[s]=H.r[j];

s=j;

}

H.r[s]=rc;//插入

}

void HeapSort(SqList &H)

{//对顺序表H进行堆排序。

int i;

RedType temp;

for(i=H.length/2;i>0;--i)//把H.r[1..H.length]建成大顶堆

HeapAdjust(H,i,H.length);

for(i=H.length;i>1;--i)

{

temp=H.r[i];

H.r[i]=H.r[1];

H.r[1]=temp;//将堆顶记录和当前未经排序子序列Hr[1..i]中

//最后一个记录相互交换

HeapAdjust(H,1,i-1);//将H.r[1..i-1]重新调整为大顶堆

}

}

void main()

{

SqList S;

printf("---------- 五种排序算法 ----------\n");

InitList_Sq(S);

printf(" 1.简单插入排序\n");

InsertSort(S);

Print_Sq(S);

printf(" 2.冒泡排序\n");

BubbleSort(S);

Print_Sq(S);

printf(" 3.快速排序\n");

QuickSort(S);

Print_Sq(S);

printf(" 4.归并排序\n");

MergeSort(S);

Print_Sq(S);

printf(" 5.堆排序\n");

HeapSort(S);

Print_Sq(S);

}

结果如图

冒泡顺序