目录

一、二分搜索技术：

1.算法核心：

2.代码实现：

二、合并排序：

1.算法核心：

2.代码实现：

三、快速排序：

1.算法核心：

2.代码实现：

四、线性时间选择：

1.算法核心：

2.代码实现：

五、循环赛：

1.算法思想：

2.算法步骤：

3.代码实现：

1.算法核心：

（1）将数组分为大致相同的两半；

（2）比较 a[n/2] 与 x 之间的大小；

（3）重复步骤  (1)、(2)  至找到所需数据。

2.代码实现：

#include 
#include 
 
//二分查找算法，找不到就返回-1，找到了就返回值
int binary_search(int * list,int len,int target)
{
    int l = 0;
    int r = len-1;
    int middle;
    while(l <= r)
	{
        middle = (l + r)/2;
        if(list[middle] == target)
        {
            printf("已找到该值，数组下标为:%dn",middle);
            return list[middle];
        }
        else if(list[middle] > target)
        {
            r = middle -1;
        }
        else if(list[middle] < target)
        {
            l = middle + 1;
        }
    }
    printf("未找到该值");
    return -1;
}
 
int main()
{
 
    int a[] = {2,4,5,8,9,44};
    int b = binary_search(a,sizeof(a)/4,5);
    printf("b=%dn",b);
    return 0;
}

二、合并排序： 1.算法核心：

（1）将数组分为大小大致相同的两个子集合；

（2）分别对这两个子集合排序；

（3）合并已经排好序的子集合。

2.代码实现：

#include 
#include 
#define N 7

void merge(int arr[], int l, int mid, int r)
{
    int i, k;
    int *tmp = (int *)malloc((r-l+1)*sizeof(int));
	
	//申请空间，使其大小为两个
    int left_low = l;
    int left_high = mid;
    int right_low = mid + 1;
    int right_high = r;
    
	for(k=0; left_low<=left_high && right_low<=right_high; k++)//比较两个指针所指向的元素，取较小的元素赋值给tmp[k] 
	{  
        if(arr[left_low]<=arr[right_low])
		{
            tmp[k] = arr[left_low];
            left_low++;
        }
		else
		{
            tmp[k] = arr[right_low];
            right_low++;
        }
    }
    
    if(left_low <= left_high)//若第一个序列有剩余，直接复制出来粘到合并序列尾
	{ 
		for(i=left_low;i<=left_high;i++)
        	tmp[k++] = arr[i];
    }
    if(right_low <= right_high) //若第二个序列有剩余，直接复制出来粘到合并序列尾
	{
        for(i=right_low; i<=right_high; i++)
        	tmp[k++] = arr[i];
    }
    for(i=0; i 
三、快速排序： 
1.算法核心： 
（1）分解：先从数列中取出一个数作为基准数，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。将数组   a[p:r]  分解为两个数组：a[p:k]  ,  a[k+1:r]；
 
（2）递归：对这两个数组分别排序，重复（1）至只有一个元素；
 
（3）合并：合并两个数组。
 
2.代码实现： 
#include 
#include 
#define BUF_SIZE 10
 
void display(int array[], int maxlen)
{
    int i;
    for(i = 0; i < maxlen; i++)
    {
        printf("%-3d", array[i]);
    }
    printf("n");
    return ;
}

int partition(int *arr,int p, int r)
{
	int x;
	int key = arr[p];		// 记下最前面的数
	while (p < r)			// 把小于key的放前面, 大于key的放后面
	{
		while (arr[r] >= key && p < r)
			r--;
		if (p < r)
			arr[p] = arr[r];
		while (arr[p] <= key && p < r)
			p++;
		if (p < r)
			arr[r] = arr[p];
	}
	// 分别从两头开始, 找到中间时, 把key存回
	arr[p] = key;
	return p;
}

void QuickSort(int *arr, int l, int r)
{
    if (l < r)
    {
    	int q=partition(arr,l,r);
        // 递归调用
        QuickSort(arr, l, q - 1);     // 排序k左边
        QuickSort(arr, q + 1, r);    // 排序k右边
    }
}
 
// 主函数
int main()
{
    int array[BUF_SIZE] = {12,85,25,16,34,23,49,95,17,61};
    int maxlen = BUF_SIZE;
    
    QuickSort(array, 0, maxlen-1);  // 快速排序

    display(array, maxlen);
    return 0;
}
 
四、线性时间选择： 
1.算法核心： 
线性时间的选择的精髓就在Select算法之中，其算法复杂度最坏情况为 O(n) ，具体步骤如下：
 
（1）将 n 个元素，分成组，取出每组的中位数（第三小的元素）;
 （2）取出个中位数的中位数（Select函数可以取中位数）；
 （3）利用快速排序中的分解函数 partition()，以所求中位数为基准，划分 a[p : r] 为两段；
 （4）取其中一段进行递归。
 
2.代码实现： 
#include 
#include 

int num[2000000];

int select(int p, int r, int k);
int partition(int p, int r, int median);
void selectSort(int p, int r);
void swap(int &a, int &b);

int main()
{
	int n, m, i;
	while (~scanf("%d%d", &n, &m))
	{
		for (i = 0; i < n; i++)
		{
			scanf("%d", &num[i]);
		}						
		printf("%dn", select(0, n - 1, m - 1));
	}
	return 0;
}
// 中位数法线性时间选择
int select(int p, int r, int k)
{
	// 小于75个数据
	if (r - p < 74)
	{
		selectSort(p, r);				// 选择排序
		return num[p + k];				
	}

	for (int i = 0; i <= (r-p-4)/5; i++)
	{
		int start = p + 5 * i;			
		int end = start + 4;		
		for (int j = 0; j < 3; j++)				//
			for (int m = start; m < end - j; m++)
				if (num[m] > num[m + 1])
					swap(num[m], num[m+1]);
		swap(num[p + i], num[start + 2]);		// 每组的中位数交换到前面第p + i的位置
	}
	
	int median = select(p, p + (r-p-4)/5, (r-p+6) / 10);	// 找中位数的中位数
	int i = partition(p, r, median);	//将数组分为两段, 左边的小于中位数的中位数, 右边的大于中位数的中位数
	int j = i - p + 1;		

	if (k == j)					//a[k]等于中位数 
		return num[i];			
	if (k < j)					//a[k]小于中位数 
		return select(p, i - 1, k);				
	if (k > j)					//a[k]大于中位数 
		return select(i + 1, r, k - j);	
}

int partition(int p, int r, int median)		// 以中位数进行分割, 分成两半
{
	int x;
	for (int i = p; i <= r; i++)
		if (num[i] == median)
		{
			x = i;			//记录中位数下标 
			break;
		}

	swap(num[x], num[p]);	// 将中位数交换到最前面
	int key = num[p];		// 记下最前面的数

	while (p < r)			// 把小于key的放前面, 大于key的放后面
	{
		while (num[r] >= key && p < r)
			r--;
		if (p < r)
			num[p] = num[r];
		while (num[p] <= key && p < r)
			p++;
		if (p < r)
			num[r] = num[p];
	}
	// 分别从两头开始, 找到中间时, 把key存回
	num[p] = key;
	return p;
}
// 选择排序
void selectSort(int p, int r)
{
	for (int i = p; i <= r; i++)//将第i大的值放在第i位 
	{
		int MIN = i;
		for (int j = i + 1; j <= r; j++)//找到最大值 
			if (num[MIN] > num[j])
				MIN = j;
		swap(num[i], num[MIN]);
	}
}
// 交换两个元素
void swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}
 
五、循环赛： 
1.算法思想： 
        将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。
 
2.算法步骤： 
（1）初始化第一行：
 
（2）定义一个m值，作为填充矩阵的起始位置标记
 
（3）将问题分成k部分（）。以k=3为例，将问题分成3大部分：
 
        第一部分为，根据已经初始化的第一行，填写第二行；
 
        第二部分为，根据已经填充好的第一部分，填写第三四行；
 
        第三部分为，根据已经填充好的前四行，填写最后四行。
 
（4）将第 i 部分都划分为  即：第一部分有四个小单元，第二部分有两个小单元，第三部分有一个小单元。
 
（5）对单元内的矩阵进行赋值（对角线填充）。
 
3.代码实现： 
#include
#include 
using namespace std;

void order(int k,int n)
{
	int** a;
	int x=n;
	a=new int*[n];
	for(int i=1;i<=n;i++)
		a[i]=new int[n];
	for(int i=1;i<=n;i++)//初始化第一行 
		a[1][i]=i;

	int m=1;//m代表着分组的长度 
	for(int s=1;s<=k;s++)
	{
		n=n/2;
		for(int t=1;t<=n;t++)//内部对称赋值所需的次数 
		{
			for(int i=m+1;i<=2*m;i++)
			{
				for(int j=m+1;j<=2*m;j++)
				{
					a[i][j+(t-1)*(2*m)]=a[i-m][j+(t-1)*(2*m)-m];//右下角==左上角 
					a[i][j+(t-1)*(2*m)-m]=a[i-m][j+(t-1)*(2*m)];//左下角==右上角 
				}
			}
		}
		m=m*2;
	}
	for(int i=1;i<=x;i++)
	{
		for(int j=1;j<=x;j++)
		{
			cout<>k;
	for(int i=0;i