排序算法习题

1.设计一个算法指出在一个无序关键字序列中的某个关键字是该序列中的第几个关键字（从小到大数），序列中关键字均为整数类型，且各不相同，要求比较的次数尽可能的少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int getPos(int arr[],int n,int k)
{
	int i=0,j=n-1;
	int temp;
	while(i<=j)
	{
		while(i<n&&arr[i]<=k) ++i; //把比这个数小的放在左边
		while(j>=0&&arr[j]>k) --j; //把比这个数大的放在右边
		if(i<j)
		{
			temp=arr[i]; //逻辑上为啥就能找到这个数的位置的原因不知道。。
			arr[i]=arr[j];
			arr[j]=temp;
			++i;
			--j;
		}
	}
	return j+1;
}

2.设计一个用二分查找法来找插入位置的改进的**插入排序算法??**。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void BSSort(int arr[],int n)
{
	int low,high,mid,place;
	for(int i=2;i<=n;++i)
	{
		low=1;high=i-1;
		arr[0]=arr[i];
		while(low<=high) // 二分查找
		{
			mid=(low+high)/2;
			if(arr[0]<arr[mid])
				high=mid+1;
			else
				low=mid+1;
		}
		place=low;  //插入arr[i]的位置？？
		for(int j=i-1;j>=place;--j)
			arr[j+1]=arr[j];
		arr[place]=arr[0];
	}
}

3.设计快速排序的递归和非递归算法**??**

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
void partition(int arr[],int low,int high,int &i) //划分函数
{
	int i; //初始化
	int temp;
	i=low;
	j=high;
	temp=arr[i];
	while(i<j)
	{
		while(i<j&&arr[j]>=temp) --j;
		if(i<j)
		{
			arr[i]=arr[j];
			++i;
		}
		while(i<j&&arr[i]<temp) ++i;
		if(i<j)
		{
			arr[j]=arr[i];
			--j;
		}

	}
	arr[i]=temp;
}

void quickSort(int arr[],int low,int high) //递归
{
	int i;
	if(low<high)
	{
		partition(arr,low,high,i);
		quickSort(arr,low,i-1);
		quickSort(arr,i+1,high);
	}
}

void quickSortNonrecursion(int arr[],int n) //非递归？？
{
	int i,low,high;
	int stack[maxSize][2],top=-1; //自己申请栈空间
	low0;high=n-1;
	++top;  //入栈
	stack[top][0]=low;
	stack[top][1]=high;
	while(top>=0)
	{
		low=stack[top][0]; //出栈
		high=stack[top][1];
		--top;
		partition(arr,low,high,i)
		if(low<high)
		{
			++top;  //入栈
			stack[top][0]=low;
			stack[top][1]=i-1;
			++top;  //出栈
			stack[top][0]=i+1;
			stack[top][1]=high;
		}
	}
}

4.设有整数0~n-1存放在整形数组A[0,1,2,…n-1]中，请设计一个时间复杂度为O(n),空间复杂度为O(1)的算法来是实现对A的排序（要求从小到大）。

1
2
3
4
5
6
void order(int A[],int n)
{
	int i;
	for(i=0;i<n;++i)
		A[A[i]]=A[i]; //???
}

5.编写一个是实现在排序二叉树中将data域（整型）值小于x的结点全部删除的算法。树中存在data域为x的结点且不存在data域值相同的结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void deleteBT(BTNode *&t)
{
	if(t!=NULL)
	{
		deleteBT(t->lChild);
		deleteBT(t->rChild);
		free(t);
		t=NULL;
	}
}
void findAndDeleteBT(BTNode *&t,int x)
{
	while(t!=NULL)
	{
		if(t->data==x)
		{
			deleteBT(t->lChild);
			return;
		}
		else if(t->data<x)
			t=t->rChild;
		else
			t=t->lChild;
	}
}