三者取中算法

Ⅰ 有没有快速排序不能排的数的组合，这与快速排序不稳定有什么关系

没有，
即使是原始待排序序列完全正序或者完全逆序，使用普通的取最左元素为基准的方法会导致排序算法性能下降，但是如果将取基准值的原则改为三者取中或者随机取值后，算法依然可以保存O(nlogn)的性能

Ⅱ 有3个4.6.7,任意取其中2个求和,得数有几种可能

典型的排列组合题，该题结果是C(2,3)，就是在三个不同的数字中取出两个，且不分顺序。所以其他结果是3*2/(1*2)=3种情况。
如果是从三个数字中取中两位组成一个二位数，这里因为存在十位与个数原因，所以可以看作是有顺序的，结果应该是P(2,3),其结果就是 3*2 = 6种。
排列组合时只要分清其组合的形式即可。一种是取出来不需要顺序的，那么取的结果就是C符号表示，如果区分顺序就用P表示。C的算法是如C(n,m) = M*(M-1)*(M-2)*...*(M-N-1)/(1*2*3*...*N)，而P的算法则不需要除法，即先从M中拿出一个的机率是M，再在剩余的结果中拿出一个即M-1，依次类推。即P(n,m)/C(n,m) = n!(n的阶乘)。只需要记好这个规律，你的初中几乎所有的排列组合计算都不会错了。说两个绝对的结果，C(n,n)的结果是1，从三个数中取出三个数，计算其和，其实只有一种可能。而P(n,n)的结果是n!，从三个数中取出三个数字，组合一个三位数，其结果就是1*2*3=6种，如果上题中，467,476,647,674,764,746这六个数字。

Ⅲ 用算法实现:单链表和顺序表删除。删除顺序表中值相同的多余结点

第8章排序(算法设计)习题练习答案
作者： 来源： http://www.csai.cn 2006年9月4日

13. 将哨兵放在R[n]中，被排序的记录放在R[0..n-1]中，重写直接插入排序算法。
解：
重写的算法如下：
void InsertSort(SeqList R)
{//对顺序表中记录R[0..n-1]按递增序进行插入排序
int i,j;
for(i=n-2;i>=0;i--) //在有序区中依次插入R[n-2]..R[0]
if(R[i].key>R[i+1].key) //若不是这样则R[i]原位不动
{
R[n]=R[i];j=i+1; //R[n]是哨兵
do{ //从左向右在有序区中查找插入位置
R[j-1]=R[j]; //将关键字小于R[i].key的记录向右移
j++;
}while(R[j].key<R[n].key]);
R[j-1]=R[n]; //将R[i]插入到正确位置上
}//endif
}//InsertSort.

14.以单链表作为存储结构实现直接插入排序算法。
解：
#define int KeyType //定义KeyType 为int型
typedef struct node{
KeyType key; //关键字域
OtherInfoType info; //其它信息域，
struct node * next; //链表中指针域
}RecNode; //记录结点类型
typedef RecNode * LinkList ; //单链表用LinkList表示

void InsertSort(LinkList head)
{//链式存储结构的直接插入排序算法,head是带头结点的单链表
RecNode *p,*q,*s;
if ((head->next)&&(head->next->next))//当表中含有结点数大于1
{
p=head->next->next;//p指向第二个节点
head->next=NULL;
q=head;//指向插入位置的前驱节点
while(p)&&(q->next)&&(p->key<q->next->key)
q=q->next;
if (p)
{s=p;p=p->next;// 将要插入结点摘下
s->next=q->next;//插入合适位置：q结点后
q->next=s;
}
}
}

15.设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前。请分析算法的时间复杂度。
解：
因为只需将负数关键字排在前面而无需进行精确排列顺序，因此本算法采用两端扫描的方法，就象快速排序采用的方法一样，左边扫描到正数时停止，开始扫描右边，遇到负数时与左边的当前记录交换，如此交替进行，一趟下来就可以完成排序。

void ReSort(SeqList R)
{//重排数组，使负值关键字在前
int i=1,j=n; //数组存放在R[1..n]中
while (i<j) //i<j表示尚未扫描完毕
{ while(i<j&&R[i].key<0) //遇到负数则继续扫描
i++;
R[0]=R[i]; //R[0]为辅助空间
while(i<j&&R[j].key>=0)// 遇到正数则继续向左扫描
j--;
R[i++]=R[j];R[j--]=R[0];//交换当前两个元素并移动指针
}//endwhile
}//ReSort

本算法在任何情况下的比较次数均为n(每个元素和0)相比，交换次数少于n/2，总的来说，时间复杂度为O(n).

*16.写一个双向冒泡排序的算法，即在排序过程中交替改变扫描方向。
解：
算法如下：
void BubbleSort(SeqList R)
{//R[1..n]是待排序文件，双向扫描冒泡排序
int i,j,k;
Boolean exchange; //交换标记
i=n;j=1;
exchange=TRUE;
while (i>j)&&(exchange)
{k=i-1;exchange=FALSE;
while (k>=j)//由下往上扫描
{if (r[k]>r[k+1])
{r[0]=r[k];r[k]=r[k+1];r[k+1]=r[k];exchange=TRUE;//交换
}//endif
k--;
}//endwhile
if (exchange)
{exchange=FALSE;
j++;k=j+1;
while(k<=i)//由上往下扫描
{if (r[k]<r[k-1])
{r[0]=r[k];r[k]=r[k-1];r[k-1]=r[k];exchange=TRUE;//交换
}//endif
k++;
}endwhile
i--;
}//endif
}endwhile
}//endsort

17.下面是一个自上往下扫描的冒泡排序的伪代码算法，它采用lastExchange 来记录每趟扫描中进行交换的最后一个元素的位置，并以它作为下一趟排序循环终止的控制值。请仿照它写一个自下往上扫描的冒泡排序算法。
void BubbleSort(int A[],int n)
//不妨设A[0..n-1]是整型向量
int lastExchange,j,i=n-1;
while (i>0)
lastExchange=0;
for(j=0;j<i;j++)//从上往下扫描A[0..i]
if(A[j+1]<A[j]){
交换A[j]和A[j+1];
lastExchange=j;
}
i=lastExchange;//将i置为最后交换的位置
}//endwhile
}//BubbleSort

解：算法如下：
void BubbleSort(int A[],int n)
//不妨设A[0..n-1]是整型向量
int lastExchange,j,i=0;
while (i<n) //这一条很重要，如不改为这样，算法将无限循环下去
lastExchange=n;
for(j=n-1;j>i;j--)//从下往上扫描A[0..i]
if(A[j-1]<A[j]){
交换A[j]和A[j-1];
lastExchange=j;
}
i=lastExchange;//将i置为最后交换的位置
}//endwhile
}//BubbleSort

18.改写快速排序算法，要求采用三者取中的方式选择划分的基准记录；若当前被排序的区间长度小于等于3时，无须划分而是直接采用直接插入方式对其排序。
解：
改写后的算法如下：
void QuickSort(SeqList R,int low ,int high)
{//对R[low..high]快速排序
int pivotpos;
if(high-low<=2)//若当前区内元素少于3个
{//则进行直接插入排序
InsertSort(R,low,high);
}
else
{
pivotpos=midPartion(R,low,high);
QuickSort(R,low,pivotpos-1);
QuickSort(R,pivotpos+1，high);
}
}//QuickSort

int midPartion(SeqList R,int i, int j)
{//三者取中规则定基准
if(R[(i+j)/2].key>R[i].key)
{ 交换R[(i+j)/2]和R[i];}
if(R[i].key>R[j].key)
{ 交换R[i]和R[j];}
if(R[i].key)<R[(i+j)/2].key)
{ 交换R[i]和R[(i+j)/2];}
//以上三个if语句就使区间的第一个记录的key值为三个key的中间值
return Partion(R,i,j);//这样我们就可以仍使用原来的划分算法了
}

19.对给定的j(1≤j≤n ),要求在无序的记录区R[1..n]中找到按关键字自小到大排在第j个位置上的记录(即在无序集合中找到第j个最小元)，试利用快速排序的划分思想编写算法实现上述的查找操作。
答：
int QuickSort(SeqList R,int j,int low,int high)
{ //对R[low..high]快速排序
int pivotpos； //划分后的基准记录的位置
if(low<high){//仅当区间长度大于1时才须排序
pivotpos=Partition(R，low，high)； //对R[low..high]做划分
if (pivotpos==j) return r[j];
else if (pivotpos>j) return(R,j,low,pivotpos-1);
else return quicksort(R,j,pivotpos+1,high);
}
} //QuickSort

20.以单链表为存储结构，写一个直接选择排序算法。
答：
#define int KeyType //定义KeyType 为int型
typedef struct node{
KeyType key; //关键字域
OtherInfoType info; //其它信息域，
struct node * next; //链表中指针域
}RecNode; //记录结点类型

typedef RecNode * LinkList ; //单链表用LinkList表示

void selectsort(linklist head)
{RecNode *p,*q,*s;
if(head->next)&&(head->next->next)
{p=head->next;//p指向当前已排好序最大元素的前趋
while (p->next)
{q=p->next;s=p;
while(q)
{if (q->key<s->key) s=q;
q=q->next;
}//endwhile
交换s结点和p结点的数据；
p=p->next;
}//endwhile
}//endif
}//endsort

21.写一个heapInsert(R,key)算法，将关键字插入到堆R中去，并保证插入R后仍是堆。提示：应为堆R增加一个长度属性描述(即改写本章定义的SeqList类型描述，使其含有长度域)；将key先插入R中已有元素的尾部(即原堆的长度加1的位置，插入后堆的长度加1)，然后从下往上调整，使插入的关键字满足性质。请分析算法的时间。
答：
#define n 100//假设文件的最长可能长度
typedef int KeyType; //定义KeyType 为int型
typedef struct node{
KeyType key; //关键字域
OtherInfoType info; //其它信息域，
}Rectype; //记录结点类型

typedef struct{
Rectype data[n] ; //存放记录的空间
int length;//文件长度
}seqlist;

void heapInsert(seqlist *R,KeyType key)
{//原有堆元素在R->data[1]~R->data[R->length],
//将新的关键字key插入到R->data[R->length+1]位置后，
//以R->data[0]为辅助空间，调整为堆(此处设为大根堆)
int large;//large指向调整结点的左右孩子中关键字较大者
int low,high;//low和high分别指向待调整堆的第一个和最后一个记录
int i;
R->length++；R->data[R->length].key=key;//插入新的记录
for(i=R->length/2;i>0;i--)//建堆
{
low=i;high=R->length;
R->data[0].key=R->data[low].key;//R->data[low]是当前调整的结点
for(large=2*low;large<=high;large*=2){
//若large>high，则表示R->data[low]是叶子，调整结束；
//否则令large指向R->data[low]的左孩子
if(large<high&&R->data[large].key<R->data[large+1].key)
large++;//若R->data[low]的右孩子存在
//且关键字大于左兄弟，则令large指向它
if (R->data[0].key<R->data[large].key)
{ R->data[low].key= R->data[large].key;
low=large;//令low指向新的调整结点
}
else break;//当前调整结点不小于其孩子结点的关键字，结束调整
}//endfor
R->data[low].key=R->data[0].key;//将被调整结点放入最终的位置上
}//end of for
}end of heapinsert

算法分析：
设文件长度为n,则该算法需进行n/2趟调整，总的时间复杂度与初建堆类似，最坏时间复杂度为O(nlgn)，辅助空间为O(1).

22.写一个建堆算法：从空堆开始，依次读入元素调用上题中堆插入算法将其插入堆中。
答：
void BuildHeap(seqlist *R)
{
KeyType key;
R->length=0;//建一个空堆
scanf("%d",&key);//设MAXINT为不可能的关键字
while(key!=MAXINT)
{
heapInsert(R,key);
scanf("%d",&key);
}
}

23.写一个堆删除算法：HeapDelete(R,i),将R[i]从堆中删去，并分析算法时间，提示：先将R[i]和堆中最后一个元素交换，并将堆长度减1，然后从位置i开始向下调整，使其满足堆性质。
答：
void HeapDelete(seqlist *R,int i)
{//原有堆元素在R->data[1]~R->data[R->length],
//将R->data[i]删除，即将R->data[R->length]放入R->data[i]中后，
//将R->length减1，再进行堆的调整，
//以R->data[0]为辅助空间，调整为堆(此处设为大根堆)
int large;//large指向调整结点的左右孩子中关键字较大者
int low,high;//low和high分别指向待调整堆的第一个和最后一个记录
int j;
if (i>R->length)
Error("have no such node");
R->data[i].key=R->data[R->length].key;
R->length--；R->data[R->length].key=key;//插入新的记录
for(j=i/2;j>0;j--)//建堆
{
low=j;high=R->length;
R->data[0].key=R->data[low].key;//R->data[low]是当前调整的结点
for(large=2*low;large<=high;large*=2){
//若large>high，则表示R->data[low]是叶子，调整结束；
//否则令large指向R->data[low]的左孩子
if(large<high&&R->data[large].key<R->data[large+1].key)
large++;//若R->data[low]的右孩子存在
//且关键字大于左兄弟，则令large指向它
if (R->data[0].key<R->data[large].key)
{ R->data[low].key= R->data[large].key;
low=large;//令low指向新的调整结点
}
else break;//当前调整结点不小于其孩子结点的关键字，结束调整
}//endfor
R->data[low].key=R->data[0].key;//将被调整结点放入最终的位置上
}//end of for
}end of HeapDelete

24.已知两个单链表中的元素递增有序，试写一算法将这两个有序表归并成一个递增有序的单链表。算法应利用原有的链表结点空间。
答：
typedef struct node{
KeyType key; //关键字域
OtherInfoType info; //其它信息域，
struct node * next; //链表中指针域
}RecNode; //记录结点类型

typedef RecNode * LinkList ; //单链表用LinkList表示

void mergesort(LinkList la,LinkList lb,LinkList lc)
{RecNode *p,*q,*s,*r;
lc=la;
p=la;//p是la表扫描指针，指向待比较结点的前一位置
q=lb->next;//q是lb表扫描指针，指向比较的结点
while(p->next)&&(q)
if (p->next->key<=q->key)
p=p->next;
else {s=q;q=q->next;
s->next=p->next;p->next=s;//将s结点插入到p结点后
p=s;}
if (!p->next) p->next=q;
free(lb);
}

25.设向量A[0..n-1]中存有n个互不相同的整数，且每个元素的值均在0到n-1之间。试写一时间为O(n)的算法将向量A排序，结果可输出到另一个向量B[0..n-1]中。
答：
sort(int *A,int *B)
{//将向量A排序后送入B向量中
int i;
for(i=0;i<=n-1;i++)
B[A[i]]=A[i];
}

*26.写一组英文单词按字典序排列的基数排序算法。设单词均由大写字母构成，最长的单词有d个字母。提示：所有长度不足d个字母的单词都在尾处补足空格，排序时设置27个箱子，分别与空格，A，B...Z对应。
答：
#define KeySize 10 //设关键字位数d=10
#define Radix 27 //基数rd为27
typedef RecType DataType;//将队列中结点数据类型改为RecType类型
typedef struct node{
char key[KeySize]; //关键字域
OtherInfoType info; //其它信息域，
}RecType; //记录结点类型
typedef RecType seqlist[n+1];

void RadixSort(seqlist R)
{
LinkQueue B[Radix];
int i;
for(i=0;i<Radix;i++)//箱子置空
InitQueue(&B[i]);
for(i=KeySize-1;i>=0;i--){//从低位到高位做d趟箱排序
Distribute(R,B,i);//第KeySize-i趟分配
Collect(R,B);//第KeySize-i趟收集
}
}

void Distribute(seqlist R,LinkQueue B[], int j)
{//按关键字的第j个分量进行分配，初始时箱子为空
int i;
j=KeySize-j; // 确定关键字从低位起的位置
for(i=0;i<n;i++) //依次扫描R[i]，将其装箱
if (R[i].key[j]-'A'>26)
EnQueue(&B[0],R[i]);//将第j位关键字位空格的记录入第0个队列
else EnQueue(&B[0],R[R[i].key[j]-'A'+1]);
}

void Collect(seqlist R,LinkQueue B[])
{
//依次将各非空箱子中的记录收集起来，本过程结束，各箱子都变空
int i,j;
for (j=0;j<Radix;j++)
while(!QueueEmpty(&B[j]))
R[i++]=DeQueue(&B[j]);//将出队记录依次输出到R[i]中
}

Ⅳ 怎么计算中位值

中位值算法：将所有数排序，然后取最中间的数，如果是偶数则取中间的两个数然后除以2。

比如说有99个数字从小到大排列，排在第50的，就是这组数的中位数。这个数字的前面有49个数字，后面有49个数字，它正好排在最中间，就是中位数。

中位值---是将所给的一组数从小到大或从大到小排列，奇数个数的话取中间的数字，偶数个数的话取中间两个数的平均数。

(4)三者取中算法扩展阅读

1、特点

中位数：与数据的排列位置有关，某些数据的变动对它没有影响；它是一组数据中间位置上的代表值，不受数据极端值的影响。

2、作用

中位数：作为一组数据的代表，可靠性比较差，因为它只利用了部分数据。但当一组数据的个别数据偏大或偏小时，用中位数来描述该组数据的集中趋势就比较合适。

Ⅳ 数据结构一道排序题怎么排啊我想知道思路 答案已经有请告诉帮我分析一下

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：

1）、设置两个变量I、J，排序开始的时候I：=1，J：=N；

2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；

3）、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换；

4）、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；

5）、重复第3、4步，直到I=J；

例如：待排序的数组A的值分别是：（初始关键数据X：=49）

A[1] A[2] A[3] A[4] A[5] A[6] A[7]：

49 38 65 97 76 13 27

进行第一次交换后： 27 38 65 97 76 13 49

( 按照算法的第三步从后面开始找

进行第二次交换后： 27 38 49 97 76 13 65

( 按照算法的第四步从前面开始找>X的值，65>49,两者交换，此时I：=3 )

进行第三次交换后： 27 38 13 97 76 49 65

( 按照算法的第五步将又一次执行算法的第三步从后开始找

进行第四次交换后： 27 38 13 49 76 97 65

( 按照算法的第四步从前面开始找大于X的值，97>49,两者交换，此时J：=4 )

此时再执行第三不的时候就发现I=J，从而结束一躺快速排序，那么经过一躺快速排序之后的结果是：27 38 13 49 76 97 65，即所以大于49的数全部在49的后面，所以小于49的数全部在49的前面。

快速排序就是递归调用此过程——在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过程如图6所示：

初始状态 {49 38 65 97 76 13 27}

进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65}

分别对前后两部分进行快速排序 {13} 27 {38}

结束 结束 {49 65} 76 {97}

49 {65} 结束

结束

图6 快速排序全过程

1）、设有N（假设N=10）个数，存放在S数组中；

2）、在S[1。。N]中任取一个元素作为比较基准，例如取T=S[1]，起目的就是在定出T应在排序结果中的位置K，这个K的位置在：S[1。。K-1]<=S[K]<=S[K+1..N]，即在S[K]以前的数都小于S[K]，在S[K]以后的数都大于S[K]；

3）、利用分治思想（即大化小的策略）可进一步对S[1。。K-1]和S[K+1。。N]两组数据再进行快速排序直到分组对象只有一个数据为止。

如具体数据如下，那么第一躺快速排序的过程是：

数组下标： 1 2 3 4 5 6 7 8 9 10

45 36 18 53 72 30 48 93 15 36

I J

（1） 36 36 18 53 72 30 48 93 15 45

（2） 36 36 18 45 72 30 48 93 15 53

（3） 36 36 18 15 72 30 48 93 45 53

（4） 36 36 18 15 45 30 48 93 72 53

（5） 36 36 18 15 30 45 48 93 72 53

通过一躺排序将45放到应该放的位置K，这里K=6，那么再对S[1。。5]和S[6。。10]分别进行快速排序。

一般来说，冒泡法是程序员最先接触的排序方法，它的优点是原理简单，编程实现容易，但它的缺点就是--程序的大忌--速度太慢。下面我介绍一个理解上简单但编程实现上不是太容易的排序方法，我不知道它是不是现有排序方法中最快的，但它是我见过的最快的。排序同样的数组，它所需的时间只有冒泡法的 4% 左右。我暂时称它为“快速排序法”。

“快速排序法”使用的是递归原理，下面我结合一个例子来说明“快速排序法”的原理。首先给出一个数组{53，12，98，63，18，72，80，46， 32，21}，先找到第一个数--53，把它作为中间值，也就是说，要把53放在一个位置，使得它左边的值比它小，右边的值比它大。{21，12，32， 46，18，53，80，72，63，98}，这样一个数组的排序就变成了两个小数组的排序--53左边的数组和53右边的数组，而这两个数组继续用同样的方式继续下去，一直到顺序完全正确。

我这样讲你们是不是很胡涂，不要紧，我下面给出实现的两个函数：

/*
n就是需要排序的数组，left和right是你需要排序的左界和右界，
如果要排序上面那个数组，那么left和right分别是0和9
*/

void quicksort(int n[], int left,int right)
{
int dp;
if (left<right) {

/*
这就是下面要讲到的函数，按照上面所说的，就是把所有小于53的数放
到它的左边，大的放在右边，然后返回53在整理过的数组中的位置。
*/
dp=partition(n,left,right);

quicksort(n,left,dp-1);

quicksort(n,dp+1,right); //这两个就是递归调用，分别整理53左边的数组和右边的数组
}
}

我们上面提到先定位第一个数，然后整理这个数组，把比这个数小的放到它的左边，大的放右边，然后

返回这中间值的位置，下面这函数就是做这个的。
int partition(int n[],int left,int right)
{
int lo,hi,pivot,t;

pivot=n[left];
lo=left-1;
hi=right+1;

while(lo+1!=hi) {
if(n[lo+1]<=pivot)
lo++;
else if(n[hi-1]>pivot)
hi--;
else {
t=n[lo+1];
n[++lo]=n[hi-1];
n[--hi]=t;
}
}

n[left]=n[lo];
n[lo]=pivot;
return lo;
}

这段程序并不难，应该很好看懂，我把过程大致讲一下，首先你的脑子里先浮现一个数组和三个指针，第一个指针称为p指针，在整个过程结束之前它牢牢的指向第一个数，第二个指针和第三个指针分别为lo指针和hi指针，分别指向最左边的值和最右边的值。lo指针和hi指针从两边同时向中间逼近，在逼近的过程中不停的与p指针的值比较，如果lo指针的值比p指针的值小，lo++，还小还++，再小再++，直到碰到一个大于p指针的值，这时视线转移到hi指针，如果 hi指针的值比p指针的值大，hi--，还大还--，再大再--，直到碰到一个小于p指针的值。这时就把lo指针的值和hi指针的值做一个调换。持续这过程直到两个指针碰面，这时把p指针的值和碰面的值做一个调换，然后返回p指针新的位置。

Ⅵ c语言给定三个数abc试写出中间数的算法。

1、直接比较啊，就六种情况，都列出来即可找到中间数
2、先对着三个数进行排序，取中间位置的即是中间数
3、求三个数的和，及最大值和最小值，用和减去最大值和最小值即是中间数。

Ⅶ 设有三个整数abc，求找出中间值的算法流程图

设有三个整数abc，求找出中间值的算法流程图？（a+b+c）/2