signed

QiShunwang

“诚信为本、客户至上”

第74节 编写查找和排序函数

2021/5/14 23:08:17   来源:

一.回顾: 有序表中的二分查找

#include <stdio.h>
#define SIZE 10
int main()
{
	int d[SIZE] = { 1,3,9,12,32,41,45,62,75,77 };
	int low, high, mid, key, index = -1;
	printf("Input a key you want to search: ");
	scanf_s("%d", &key);
	low = 0, high = SIZE - 1;
	while (low <= high)
	{
		mid = (low + high) / 2;
		if (d[mid] == key)
		{
			index = mid;
			break;
		} 
		else if (d[mid] > key)
			high = mid - 1;
		else
			low = mid + 1;
	}
	if (index >= 0)
		printf("The index of the key is %d .\n", index);
	else
		printf("Not found.\n");
	return 0;
}
运行结果:
Input a key you want to search: 12
The index of the key is 3 .

二.用函数实现二分查找

#include <stdio.h>
int binary_search(int arr[], int n, int k);
#define SIZE 10
int main()
{
	int d[SIZE] = { 1,3,9,12,32,41,45,62,75,77 };
	int low, high, mid, key, index = -1;
	printf("Input a key you want to search: ");
	scanf_s("%d", &key);
	index = binary_search(d, SIZE, key);//调用函数
	if (index >= 0)
		printf("The index of the key is %d .\n", index);
	else
		printf("Not found.\n");
	return 0;
}
int binary_search(int arr[], int n, int k)
//功能:在长度为n的有序数组中查找k出现的位置
//参数:有序数组/数组元素个数/要查找的值
//返回:返回值i=-1代表没查到,否则返回k的位置
{
	int i = -1;
	int low = 0, high = n - 1, mid;
	while (low <= high) //low每次二分后+1,找不到会>high
	{
		mid = (low + high) / 2;
		if (arr[mid] == k)
		{
			i = mid;
			break;
		}
		else if (arr[mid] > k)
			high = mid - 1;
		else
			low = mid + 1;
	}
	return i;
}
运行结果:
Input a key you want to search: 12
The index of the key is 3 .

三.选择法排序

选择法:

先找出N个数中最小的数,与a[0]对换;再找出a[1]到a[N-1]中最小的数,与a[1]对换……。

每比较一轮,找出一个未经排序的数中最小的一个,并置于未排序部分的开始处。一共需要比较N-1轮.

a[0]a[1]a[2]a[3]a[4]排序任务
36194未排序时
163945个数中最小数1(a[2]),k=2,交换a[2]和a[0]
13694余下数中最小数3(a[2]), k=2,交换a[2]和a[1]
13496余下数中最小数4(a[4]), k=4,交换a[4]和a[2]
13469余下数中最小数6(a[4]), k=4,交换a[4]和a[3]
#include <stdio.h>
void select_sort(int array[], int n);
int main()
{
	int a[5] = { 3,6,1,9,4 }, i;
	select_sort(a, 5);
	printf("the sorted array:\n");
	for (i = 0; i < 5; i++)
		printf("%d ", a[i]);
	printf("\n");
	return 0;
}

void select_sort(int array[], int n)
{
	int i, j, k, t;
	for (i = 0; i < n - 1; i++) //交换n-1次
	{
		k = i;
		for (j = i + 1; j < n; j++) //找出数组中的最小值的下标
			if (array[j] < array[k])
				k = j;

		//将最小值交换到最前面
		t = array[k]; 
		array[k] = array[i];
		array[i] = t;
	}
	return;
}
运行结果:
the sorted array:
1 3 4 6 9