【C/C++学院】0907-象棋五子棋代码分析/寻找算法以及排序算法

简介: <p></p> <h2><span style="font-family:宋体; font-size:16pt">象棋五子棋代码分析</span><span style="font-family:宋体; font-size:16pt"></span></h2> <p></p> <p>编译代码报错:</p> <pre code_snippet_id="1596529" snipp

象棋五子棋代码分析

编译代码报错:

错误	1	error MSB8031: Building an MFC project for a non-Unicode character set is deprecated. You must change the project property to Unicode or download an additional library. See http://go.microsoft.com/fwlink/p/?LinkId=286820 for more information.	C:\Program Files\MSBuild\Microsoft.Cpp\v4.0\V120\Microsoft.CppBuild.targets	369	5	chess


安装vc_mbcsmfc.exe。

Pdb格式不兼容报错:





寻找算法以及排序算法

插值查找.cpp

#define  _CRT_SECURE_NO_WARNINGS

#include <stdio.h> 
#include <stdlib.h>
int Bin_Search(int *a, int key, int n)
{
	int low, high, mid;
	low = 0;
	high = n - 1;
	while (low <= high)
	{
		mid = low + (high - low) * (key - a[low]) / (a[high] - a[low]); //此处于二分查找不同,套用插值公式  
		if (a[mid] > key)         //如果key比插值小,把高位调整为插值下标的下一位            
			high = mid - 1;
		else if (a[mid] < key)
			low = mid + 1;
		else
			return mid;
	}
	return -1;
}
int mainA()
{
	int a[] = { 1, 5, 17, 25, 33, 38, 46, 55, 69, 75, 99 };
	int key;
	int len = sizeof(a) / sizeof(*a);
	printf("请输入要查找的值:\n");
	scanf("%d", &key);
	int pos = Bin_Search(a, key, len);
	if (pos != -1)
		printf("在数组的第%d个位置找到:%d\n", pos + 1, key);
	else
		printf("未在数组中找到元素:%d\n", key);


	system("pause");
	return 0;
}

斐波那契查找.cpp

#define  _CRT_SECURE_NO_WARNINGS
#define  MAXSIZE 13
#include <stdio.h>
#include <stdlib.h>
//斐波那契查找算法的明显优点在于它只涉及加法和减法运算,而不用除法。
//因为除法比加减法要占去更多的机时,因此,斐波那契查找的平均性能要比折半查找好。
void fibonacci(int *f)
{
	f[0] = 1;
	f[1] = 1;
	for (int i = 2; i < MAXSIZE; ++i)
		f[i] = f[i - 2] + f[i - 1];
}

int fibonacci_search(int *a, int key, int n)
{
	int low = 0, high = n - 1;
	int mid = 0;
	int k = 0;
	int F[MAXSIZE];
	fibonacci(F);
	while (n > F[k] - 1) //计算出n在斐波那契中的数列  
		++k;
	for (int i = n; i < F[k] - 1; ++i) //把数组补全  
	{
		a[i] = a[high];
	}
	while (low <= high)
	{
		mid = low + F[k - 1] - 1;  //根据斐波那契数列进行黄金分割  
		if (a[mid] > key)
		{
			high = mid - 1;
			k = k - 1;
		}
		else if (a[mid] < key)
		{
			low = mid + 1;
			k = k - 2;
		}
		else{
			if (mid <= high) //如果为真则找到相应的位置  
				return mid;
			else
				return -1;

		}
	}
	return -1;
}

int main14()
{

	int a[MAXSIZE] = { 5, 15, 19, 20, 25, 31, 38, 41, 45, 49, 52, 55, 57 };
	int k;
	printf("请输入要查找的数字:\n");
	scanf("%d", &k);
	int pos = fibonacci_search(a, k, 13);
	if (pos != -1)
		printf("在数组的第%d个位置找到元素:%d\n", pos + 1, k);
	else
		printf("未在数组中找到元素:%d\n", k);


	system("pause");
	return 0;
}

插入.cpp

#include <iostream>
using namespace std;

void main3()
{

	int a[10];
	for (int i = 0; i < 10; i++)
		a[i] = rand() % 100;
	for (int i = 0; i < 10; i++)     //总索引
		for (int j = 0; j < i; j++)   //前面排好的部分
		{
		int temp = a[i];
		if (a[i] < a[j])
		{
			for (int k = i; k >= j; k--)
			{
				a[k] = a[k - 1];
			}
			a[j] = temp;
		}
		}
	for (int i = 0; i < 10; i++)
		cout << a[i] << " ";

	system("pause");
}

堆排序.cpp

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>

void PrintArr(int *pnArr, int nLen)
{
	for (int i = 0; i < nLen; i++)
	{
		printf("%d ", pnArr[i]);
	}
	printf("\n");
}

//返回i父节点下标
int Parent(int i)
{
	return (i - 1) / 2;
}

//返回i左孩子下标
int LeftChild(int i)
{
	return i * 2 + 1;
}

//返回i右孩子下标
int RightChild(int i)
{
	return i * 2 + 2;
}

void Swap(int *a, int *b)
{
	int nTmp = *a;
	*a = *b;
	*b = nTmp;
}
void MaxHeapify(int *pnArr, int nLen, int i)
{
	int LChild = LeftChild(i);
	int RChild = RightChild(i);
	int nMaxPos;
	if (LChild < nLen && pnArr[LChild] > pnArr[i])
	{
		nMaxPos = LChild;
	}
	else
	{
		nMaxPos = i;
	}
	if (RChild < nLen && pnArr[RChild] > pnArr[nMaxPos])
	{
		nMaxPos = RChild;
	}

	if (nMaxPos != i)
	{
		Swap(&pnArr[nMaxPos], &pnArr[i]);
		MaxHeapify(pnArr, nLen, nMaxPos);
	}

}
void BuildMaxHeap(int *pnArr, int nLen)
{
	for (int i = Parent(nLen - 1); i >= 0; i--)
	{
		MaxHeapify(pnArr, nLen, i);
	}
}

void HeapSort(int *pnArr, int nLen)
{
	BuildMaxHeap(pnArr, nLen);
	for (int i = nLen - 1; i > 0; i--)
	{
		Swap(&pnArr[i], &pnArr[0]);
		nLen--;
		MaxHeapify(pnArr, nLen, 0);
	}
}
int main7()
{
	int nArr[10] = { 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 };

	PrintArr(nArr, 10);
	HeapSort(nArr, 10);

	PrintArr(nArr, 10);
	system("pause");
	return 0;
}

二路插入.cpp

#include<iostream>
using namespace std;
#define MAX 20
void PrintArray(int a[], int len){
	for (int i = 0; i < len; i++)
		cout << a[i] << " ";
	cout << endl;
}
void BinInsertSort(int a[], int len){
	int *d = (int *)malloc(len*sizeof(len));
	for (int i = 0; i < len; i++)
		d[i] = 0;
	int first = 0, final = 0;
	d[0] = a[0];
	for (int i = 1; i < len; i++){
		if (a[i] <= d[first]){
			first = (first - 1 + len) % len;
			d[first] = a[i];
		}
		else if (a[i] >= d[final]){
			final = final + 1;
			d[final] = a[i];
		}
		else{
			int j = final++;
			while (a[i] < d[j]){
				d[(j + 1) % len] = d[j];
				j = (j - 1 + len) % len;
			}
			d[j + 1] = a[i];
		}
	}
	cout << "辅助数组中排序结果为:";
	PrintArray(d, len);
}
int main10(){
	int a[MAX], len;
	cout << "请输入待排序的元素个数:";
	cin >> len;
	cout << "请输入待排序的元素:";
	for (int i = 0; i < len; i++)
		cin >> a[i];
	BinInsertSort(a, len);
	system("pause");
	return 0;
}

非递归快速排序.cpp

#include<iostream>
#include<vector>
#include<stack>
#include<cstdlib>
#include<algorithm>
using namespace std;

/**把数组分为两部分,轴pivot左边的部分都小于轴右边的部分**/
template <typename Comparable>
int partition(vector<Comparable> &vec, int low, int high){
	Comparable pivot = vec[low];  //任选元素作为轴,这里选首元素
	while (low < high){
		while (low < high && vec[high] >= pivot)
			high--;
		vec[low] = vec[high];
		while (low < high && vec[low] <= pivot)
			low++;
		vec[high] = vec[low];
	}
	//此时low==high
	vec[low] = pivot;
	return low;
}

/**使用递归快速排序**/
template<typename Comparable>
void quicksort1(vector<Comparable> &vec, int low, int high){
	if (low < high){
		int mid = partition(vec, low, high);
		quicksort1(vec, low, mid - 1);
		quicksort1(vec, mid + 1, high);
	}
}

/**使用栈的非递归快速排序**/
template<typename Comparable>
void quicksort2(vector<Comparable> &vec, int low, int high){
	stack<int> st;
	if (low < high){
		int mid = partition(vec, low, high);
		if (low < mid - 1){
			st.push(low);
			st.push(mid - 1);
		}
		if (mid + 1 < high){
			st.push(mid + 1);
			st.push(high);
		}
		//其实就是用栈保存每一个待排序子串的首尾元素下标,下一次while循环时取出这个范围,对这段子序列进行partition操作
		while (!st.empty()){
			int q = st.top();
			st.pop();
			int p = st.top();
			st.pop();
			mid = partition(vec, p, q);
			if (p < mid - 1){
				st.push(p);
				st.push(mid - 1);
			}
			if (mid + 1 < q){
				st.push(mid + 1);
				st.push(q);
			}
		}
	}
}

int main11(){
	int len = 1000000;
	vector<int> vec;
	for (int i = 0; i < len; i++)
		vec.push_back(rand());
	clock_t t1 = clock();
	quicksort1(vec, 0, len - 1);
	clock_t t2 = clock();
	cout << "recurcive  " << 1.0*(t2 - t1) / CLOCKS_PER_SEC << endl;

	//重新打乱顺序
	random_shuffle(vec.begin(), vec.end());

	t1 = clock();
	quicksort2(vec, 0, len - 1);
	t2 = clock();
	cout << "none recurcive  " << 1.0*(t2 - t1) / CLOCKS_PER_SEC << endl;

	return 0;
}

归并.cpp

#include <iostream>

using namespace std;

const int N = 10;
int anthor[N];
void MergeSort(int *array, int begin, int end)
{
	if (end - begin > 1)
	{		//
		MergeSort(array, begin, (begin + end) / 2);
		MergeSort(array, (begin + end) / 2 + 1, end);

		int i = begin;
		int j = (begin + end) / 2 + 1;
		int k = begin;

		while (i <= (begin + end) / 2 && j <= end)//合并时,把一个串全部并入另一个串放在一个新串,剩下的直接放在尾部
		{
			if (array[i] > array[j])        //小的值进入,并将索引后移
				anthor[k++] = array[j++];
			if (array[i] < array[j])
				anthor[k++] = array[i++];

		}
		while (i <= (begin + end) / 2)
		{
			anthor[k++] = array[i++];
		}
		while (j <= end)
		{
			anthor[k++] = array[j++];
		}

		for (k = begin; k <= end; k++)    //排序好重新拷贝回数组
			array[k] = anthor[k];

	}
	else      //相邻则直接交换
	{
		if (array[end] < array[begin])
		{
			int temp = array[end];
			array[end] = array[begin];
			array[begin] = temp;
		}
	}
}


int main6()
{
	int array[N];
	for (int i = 0; i < 10; i++)
	{
		array[i] = rand() % 100;
		cout << array[i] << " ";
	}

	MergeSort(array, 0, N - 1);
	cout << endl;
	for (int i = 0; i < 10; i++)
	{

		cout << array[i] << " ";
	}
	system("pause");
	return 0;
}

红黑树.cpp

// 红黑树.cpp : 定义控制台应用程序的入口点。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef int key_t;
typedef int data_t;

typedef enum color_t
{
	RED = 0,
	BLACK = 1
}color_t;

typedef struct rb_node_t
{
	struct rb_node_t *left, *right, *parent;
	key_t key;
	data_t data;
	color_t color;
}rb_node_t;

/* forward declaration */
rb_node_t* rb_insert(key_t key, data_t data, rb_node_t* root);
rb_node_t* rb_search(key_t key, rb_node_t* root);
rb_node_t* rb_erase(key_t key, rb_node_t* root);

int main()
{
	int i, count = 90;
	key_t key;
	rb_node_t* root = NULL, *node = NULL;

	//srand(time(NULL));
	for (i = 1; i < count; ++i)
	{
		key = rand() % count;
		if ((root = rb_insert(key, i, root)))
		{
			printf("[i = %d] insert key %d success!\n", i, key);
		}
		else
		{
			printf("[i = %d] insert key %d error!\n", i, key);
			exit(-1);
		}

		if ((node = rb_search(key, root)))
		{
			printf("[i = %d] search key %d success!\n", i, key);
		}
		else
		{
			printf("[i = %d] search key %d error!\n", i, key);
			exit(-1);
		}
		if (!(i % 10))
		{
			if ((root = rb_erase(key, root)))
			{
				printf("[i = %d] erase key %d success\n", i, key);
			}
			else
			{
				printf("[i = %d] erase key %d error\n", i, key);
			}
		}
	}
	return 0;
}

static rb_node_t* rb_new_node(key_t key, data_t data)
{
	rb_node_t *node = (rb_node_t*)malloc(sizeof(struct rb_node_t));

	if (!node)
	{
		printf("malloc error!\n");
		exit(-1);
	}
	node->key = key, node->data = data;

	return node;
}

/*-----------------------------------------------------------
|   node           right
|   / \    ==>     / \
|   a  right     node  y
|       / \           / \
|       b  y         a   b
-----------------------------------------------------------*/
static rb_node_t* rb_rotate_left(rb_node_t* node, rb_node_t* root)
{
	rb_node_t* right = node->right;

	if ((node->right = right->left))
	{
		right->left->parent = node;
	}
	right->left = node;

	if ((right->parent = node->parent))
	{
		if (node == node->parent->right)
		{
			node->parent->right = right;
		}
		else
		{
			node->parent->left = right;
		}
	}
	else
	{
		root = right;
	}
	node->parent = right;

	return root;
}

/*-----------------------------------------------------------
|       node           left
|       / \            / \
|    left  y   ==>    a   node
|   / \               / \
|  a   b             b   y
-----------------------------------------------------------*/
static rb_node_t* rb_rotate_right(rb_node_t* node, rb_node_t* root)
{
	rb_node_t* left = node->left;

	if ((node->left = left->right))
	{
		left->right->parent = node;
	}
	left->right = node;

	if ((left->parent = node->parent))
	{
		if (node == node->parent->right)
		{
			node->parent->right = left;
		}
		else
		{
			node->parent->left = left;
		}
	}
	else
	{
		root = left;
	}
	node->parent = left;

	return root;
}

static rb_node_t* rb_insert_rebalance(rb_node_t *node, rb_node_t *root)
{
	rb_node_t *parent, *gparent, *uncle, *tmp;

	while ((parent = node->parent) && parent->color == RED)
	{
		gparent = parent->parent;

		if (parent == gparent->left)
		{
			uncle = gparent->right;
			if (uncle && uncle->color == RED)
			{
				uncle->color = BLACK;
				parent->color = BLACK;
				gparent->color = RED;
				node = gparent;
			}
			else
			{
				if (parent->right == node)
				{
					root = rb_rotate_left(parent, root);
					tmp = parent;
					parent = node;
					node = tmp;
				}

				parent->color = BLACK;
				gparent->color = RED;
				root = rb_rotate_right(gparent, root);
			}
		}
		else
		{
			uncle = gparent->left;
			if (uncle && uncle->color == RED)
			{
				uncle->color = BLACK;
				parent->color = BLACK;
				gparent->color = RED;
				node = gparent;
			}
			else
			{
				if (parent->left == node)
				{
					root = rb_rotate_right(parent, root);
					tmp = parent;
					parent = node;
					node = tmp;
				}

				parent->color = BLACK;
				gparent->color = RED;
				root = rb_rotate_left(gparent, root);
			}
		}
	}

	root->color = BLACK;

	return root;
}

static rb_node_t* rb_erase_rebalance(rb_node_t *node, rb_node_t *parent, rb_node_t *root)
{
	rb_node_t *other, *o_left, *o_right;

	while ((!node || node->color == BLACK) && node != root)
	{
		if (parent->left == node)
		{
			other = parent->right;
			if (other->color == RED)
			{
				other->color = BLACK;
				parent->color = RED;
				root = rb_rotate_left(parent, root);
				other = parent->right;
			}
			if ((!other->left || other->left->color == BLACK) &&
				(!other->right || other->right->color == BLACK))
			{
				other->color = RED;
				node = parent;
				parent = node->parent;
			}
			else
			{
				if (!other->right || other->right->color == BLACK)
				{
					if ((o_left = other->left))
					{
						o_left->color = BLACK;
					}
					other->color = RED;
					root = rb_rotate_right(other, root);
					other = parent->right;
				}
				other->color = parent->color;
				parent->color = BLACK;
				if (other->right)
				{
					other->right->color = BLACK;
				}
				root = rb_rotate_left(parent, root);
				node = root;
				break;
			}
		}
		else
		{
			other = parent->left;
			if (other->color == RED)
			{
				other->color = BLACK;
				parent->color = RED;
				root = rb_rotate_right(parent, root);
				other = parent->left;
			}
			if ((!other->left || other->left->color == BLACK) &&
				(!other->right || other->right->color == BLACK))
			{
				other->color = RED;
				node = parent;
				parent = node->parent;
			}
			else
			{
				if (!other->left || other->left->color == BLACK)
				{
					if ((o_right = other->right))
					{
						o_right->color = BLACK;
					}
					other->color = RED;
					root = rb_rotate_left(other, root);
					other = parent->left;
				}
				other->color = parent->color;
				parent->color = BLACK;
				if (other->left)
				{
					other->left->color = BLACK;
				}
				root = rb_rotate_right(parent, root);
				node = root;
				break;
			}
		}
	}

	if (node)
	{
		node->color = BLACK;
	}

	return root;
}

static rb_node_t* rb_search_auxiliary(key_t key, rb_node_t* root, rb_node_t** save)
{
	rb_node_t *node = root, *parent = NULL;
	int ret;

	while (node)
	{
		parent = node;
		ret = node->key - key;
		if (0 < ret)
		{
			node = node->left;
		}
		else if (0 > ret)
		{
			node = node->right;
		}
		else
		{
			return node;
		}
	}

	if (save)
	{
		*save = parent;
	}

	return NULL;
}

rb_node_t* rb_insert(key_t key, data_t data, rb_node_t* root)
{
	rb_node_t *parent = NULL, *node;

	parent = NULL;
	if ((node = rb_search_auxiliary(key, root, &parent)))
	{
		return root;
	}

	node = rb_new_node(key, data);
	node->parent = parent;
	node->left = node->right = NULL;
	node->color = RED;

	if (parent)
	{
		if (parent->key > key)
		{
			parent->left = node;
		}
		else
		{
			parent->right = node;
		}
	}
	else
	{
		root = node;
	}

	return rb_insert_rebalance(node, root);
}

rb_node_t* rb_search(key_t key, rb_node_t* root)
{
	return rb_search_auxiliary(key, root, NULL);
}

rb_node_t* rb_erase(key_t key, rb_node_t *root)
{
	rb_node_t *child, *parent, *old, *left, *node;
	color_t color;

	if (!(node = rb_search_auxiliary(key, root, NULL)))
	{
		printf("key %d is not exist!\n");
		return root;
	}

	old = node;

	if (node->left && node->right)
	{
		node = node->right;
		while ((left = node->left) != NULL)
		{
			node = left;
		}
		child = node->right;
		parent = node->parent;
		color = node->color;

		if (child)
		{
			child->parent = parent;
		}
		if (parent)
		{
			if (parent->left == node)
			{
				parent->left = child;
			}
			else
			{
				parent->right = child;
			}
		}
		else
		{
			root = child;
		}

		if (node->parent == old)
		{
			parent = node;
		}

		node->parent = old->parent;
		node->color = old->color;
		node->right = old->right;
		node->left = old->left;

		if (old->parent)
		{
			if (old->parent->left == old)
			{
				old->parent->left = node;
			}
			else
			{
				old->parent->right = node;
			}
		}
		else
		{
			root = node;
		}

		old->left->parent = node;
		if (old->right)
		{
			old->right->parent = node;
		}
	}
	else
	{
		if (!node->left)
		{
			child = node->right;
		}
		else if (!node->right)
		{
			child = node->left;
		}
		parent = node->parent;
		color = node->color;

		if (child)
		{
			child->parent = parent;
		}
		if (parent)
		{
			if (parent->left == node)
			{
				parent->left = child;
			}
			else
			{
				parent->right = child;
			}
		}
		else
		{
			root = child;
		}
	}

	free(old);

	if (color == BLACK)
	{
		root = rb_erase_rebalance(child, parent, root);
	}
	system("pause");
	return root;
}

基数.cpp

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>

static void PrintArr(int *pnArr, int nLen)
{
	for (int i = 0; i < nLen; i++)
	{
		printf("%d ", pnArr[i]);
	}
	printf("\n");
}

void CountSort(int *pnArr, int nArrR[], int nLen, int k)
{
	int *pnArrTmp = (int *)malloc(sizeof(int) * k);

	for (int i = 0; i < k; i++)
	{
		pnArrTmp[i] = 0;
	}

	for (int i = 0; i < nLen; i++)
	{
		pnArrTmp[pnArr[i]] = pnArrTmp[pnArr[i]] + 1;
	}

	PrintArr(pnArrTmp, k);

	for (int i = 1; i < k; i++)
	{
		pnArrTmp[i] = pnArrTmp[i] + pnArrTmp[i - 1];
	}

	PrintArr(pnArrTmp, k);

	
	for (int i = nLen - 1; i >= 0; i--)
	{
		nArrR[pnArrTmp[pnArr[i]] - 1] = pnArr[i];
		pnArrTmp[pnArr[i]] = pnArrTmp[pnArr[i]] - 1;
	}
}

int main9()
{
	int nArr[11] = { 0, 2, 1, 3, 2, 6, 9, 7, 4, 8, 6 };
	int nArrR[11]; //存放排序后的结果
	PrintArr(nArr, 11);
	CountSort(nArr, nArrR, 11, 10);

	PrintArr(nArrR, 11);
	system("pause");
	return 0;
}

快速.cpp

#include<iostream>  
using namespace std;
int a[200001], n;
void swap(int &a, int &b){
	int tmp = a;
	a = b;
	b = tmp;
}

int partition(int p, int r){
	int rnd = rand() % (r - p + 1) + p;
	swap(a[rnd], a[r]);
	int pvt = r, i = p - 1;
	for (int j = i + 1; j < r; j++)
		if (a[j] < a[pvt])
			swap(a[j], a[++i]);
	swap(a[++i], a[pvt]);
	return i;
}

void qsort(int p, int r){
	if (p < r){
		int q = partition(p, r);
		qsort(p, q - 1);
		qsort(q + 1, r);
	}
}
int main5()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	qsort(0, n - 1);
	for (int i = 0; i < n; i++)
		cout << a[i];
	system("pause");
	return 0;
}

冒泡.cpp

#include <iostream>
#include<stdlib.h>
using namespace std;

int main1()
{
	int a[10];
	for (int i = 0; i < 10; i++)
		a[i] = rand() % 100;
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10 - i; j++)
		{
		if (a[j] < a[j + 1])
		{
			int temp = a[j];
			a[j] = a[j + 1];
			a[j + 1] = temp;
		}
		}
	for (int i = 0; i < 10; i++)
		cout << a[i] << " ";
	system("pause");

	return 0;
}

木桶.cpp

#include<stdio.h>
#include<stdlib.h>
#define SIZE 100
void bucket_sort(unsigned *, int);//桶排序函数的原型
void print(unsigned *, int);//打印函数的原型
int main8()
{
	unsigned array[SIZE];
	int i = 0;

	//为数组元素随机赋值
	for (i = 0; i < SIZE; ++i)
		array[i] = rand();

	printf("排序前\n");
	print(array, SIZE);

	//排序
	bucket_sort(array, SIZE);

	printf("排序后\n");
	print(array, SIZE);
	system("pause");
	return 0;
}
void bucket_sort(unsigned * arr, int len)
{
	unsigned *buckets[10];//指针数组
	unsigned n = 1;//用于取整数各位上的值
	int index;//数组下标计数索引
	int indexs[10];//各个桶下标计数索引
	int i, j;

	//分配动态内存作为桶
	for (i = 0; i < 10; ++i)
		buckets[i] = (unsigned *)malloc(sizeof(unsigned)*len);

	while (1)
	{
		//计数索引清零
		index = 0;
		for (i = 0; i < 10; ++i)
			indexs[i] = 0;

		//数组至桶
		for (i = 0; i < len; ++i)
			buckets[arr[i] / n % 10][indexs[arr[i] / n % 10]++] = arr[i];

		//桶至数组
		for (i = 0; i < 10; ++i)
			for (j = 0; j < indexs[i]; ++j)
				arr[index++] = buckets[i][j];

		//为取元素的下一位做准备
		n *= 10;

		//判断是否该结束
		for (i = 0; arr[i] < n&&i < len; ++i);
		if (i == len) break;
	}

	//释放动态内存
	for (i = 0; i < 10; ++i)
		free(buckets[i]);
}
void print(unsigned * arr, int len)
{
	int i = 0;
	for (i = 0; i < len; ++i)
	{
		printf("%8d", arr[i]);

		//5个元素一行
		if ((i + 1) % 5 == 0)
			printf("\n");
	}
}

希尔.cpp

#include <iostream>
#include<stdlib.h>

using namespace std;
const int N = 10;
void shell_sort(const int len, int *array)
{
	int j, i, key;
	int gap = 0;
	if (len <= 0 || array == NULL)
		return;
	while (gap <= len)
	{
		gap = gap * 3 + 1;
	}
	while (gap > 0)
	{
		for (i = gap; i < len; i++)
		{
			j = i - gap;
			key = array[i];
			while ((j >= 0) && (array[j] > key))
			{
				array[j + gap] = array[j];
				j = j - gap;
			}
			array[j + gap] = key;
		}
		//display_array(len,array,gap);
		gap = (gap - 1) / 3;
	}
}

// 3  5  18   29     35   24   12  0
// 3                           12   
//     5                            0
// 3   0  18  29    35    24  12    5
//3                       24
//    0                       12
//        18                        5
//3   0   5  29     35    24  12    18
//3                  35
//   0                   24
//       5                   12
//           29                     18
//3  0   5   18   35   24   12     29   
//3          18             12
//   0            35               29
//        5            24
//3  0    5  12   29   24      18   35
//3       5       29            18
//   0        12        24          35
//3   0   5   12     18    24        29 35
//0    3  5 12    18  24   29  35

int main4()
{
	int array[N];
	for (int i = 0; i < 10; i++)
	{
		array[i] = rand() % 100;
		cout << array[i] << " ";
	}
	shell_sort(N - 1, array);
	cout << endl;
	for (int i = 0; i < 10; i++)
	{

		cout << array[i] << " ";
	}
	system("pause");
	return 0;
}

选择.cpp

#include <iostream>
using namespace std;

void main2()
{
	int a[10];
	for (int i = 0; i < 10; i++)
		a[i] = rand() % 100;

	for (int i = 0; i < 10; i++)
	{

		for (int j = i; j < 10 - i; j++)
			if (a[j] < a[i])
			{
			int temp = a[j];
			a[j] = a[i];
			a[i] = temp;
			}
	}
	
	for (int i = 0; i < 10; i++)
		cout << a[i] << " ";
	system("pause");
}


目录
相关文章
|
4月前
|
存储 监控 算法
基于 C++ 哈希表算法实现局域网监控电脑屏幕的数据加速机制研究
企业网络安全与办公管理需求日益复杂的学术语境下,局域网监控电脑屏幕作为保障信息安全、规范员工操作的重要手段,已然成为网络安全领域的关键研究对象。其作用类似网络空间中的 “电子眼”,实时捕获每台电脑屏幕上的操作动态。然而,面对海量监控数据,实现高效数据存储与快速检索,已成为提升监控系统性能的核心挑战。本文聚焦于 C++ 语言中的哈希表算法,深入探究其如何成为局域网监控电脑屏幕数据处理的 “加速引擎”,并通过详尽的代码示例,展现其强大功能与应用价值。
104 2
|
5月前
|
存储 算法 C++
Windows共享文件:探秘C++实现的B树索引算法奇境
在数字化时代,Windows共享文件的高效管理至关重要。B树算法以其自平衡多路搜索特性,在文件索引与存储优化中表现出色。本文探讨B树在Windows共享文件中的应用,通过C++实现具体代码,展示其构建文件索引、优化数据存储的能力,提升文件检索效率。B树通过减少磁盘I/O操作,确保查询高效,为企业和个人提供流畅的文件共享体验。
|
2月前
|
存储 搜索推荐 算法
加密算法、排序算法、字符串处理及搜索算法详解
本文涵盖四大类核心技术知识。加密算法部分介绍了对称加密(如 AES)、非对称加密(如 RSA)、哈希摘要(如 SHA-2)、签名算法的特点及密码存储方案(加盐、BCrypt 等)。 排序算法部分分类讲解了比较排序(冒泡、选择、插入、归并、快排、堆排序)和非比较排序(计数、桶、基数排序)的时间复杂度、适用场景及实现思路,强调混合排序的工业应用。 字符串处理部分包括字符串反转的双指针法,及项目中用正则进行表单校验、网页爬取、日志处理的实例。 搜索算法部分详解了二分查找的实现(双指针与中间索引计算)和回溯算法的概念(递归 + 剪枝),以 N 皇后问题为例说明回溯应用。内容全面覆盖算法原理与实践
128 0
|
2月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
81 0
|
3月前
|
存储 机器学习/深度学习 算法
基于 C++ 的局域网访问控制列表(ACL)实现及局域网限制上网软件算法研究
本文探讨局域网限制上网软件中访问控制列表(ACL)的应用,分析其通过规则匹配管理网络资源访问的核心机制。基于C++实现ACL算法原型,展示其灵活性与安全性。文中强调ACL在企业与教育场景下的重要作用,并提出性能优化及结合机器学习等未来研究方向。
98 4
|
4月前
|
监控 算法 数据处理
基于 C++ 的 KD 树算法在监控局域网屏幕中的理论剖析与工程实践研究
本文探讨了KD树在局域网屏幕监控中的应用,通过C++实现其构建与查询功能,显著提升多维数据处理效率。KD树作为一种二叉空间划分结构,适用于屏幕图像特征匹配、异常画面检测及数据压缩传输优化等场景。相比传统方法,基于KD树的方案检索效率提升2-3个数量级,但高维数据退化和动态更新等问题仍需进一步研究。未来可通过融合其他数据结构、引入深度学习及开发增量式更新算法等方式优化性能。
140 17
|
3月前
|
机器学习/深度学习 存储 算法
基于 C++ 布隆过滤器算法的局域网上网行为控制:URL 访问过滤的高效实现研究
本文探讨了一种基于布隆过滤器的局域网上网行为控制方法,旨在解决传统黑白名单机制在处理海量URL数据时存储与查询效率低的问题。通过C++实现URL访问过滤功能,实验表明该方法可将内存占用降至传统方案的八分之一,查询速度提升约40%,假阳性率可控。研究为优化企业网络管理提供了新思路,并提出结合机器学习、改进哈希函数及分布式协同等未来优化方向。
88 0
|
5月前
|
存储 监控 算法
基于 C++ 哈希表算法的局域网如何监控电脑技术解析
当代数字化办公与生活环境中,局域网的广泛应用极大地提升了信息交互的效率与便捷性。然而,出于网络安全管理、资源合理分配以及合规性要求等多方面的考量,对局域网内计算机进行有效监控成为一项至关重要的任务。实现局域网内计算机监控,涉及多种数据结构与算法的运用。本文聚焦于 C++ 编程语言中的哈希表算法,深入探讨其在局域网计算机监控场景中的应用,并通过详尽的代码示例进行阐释。
115 4
|
6月前
|
存储 算法 安全
企业员工数据泄露防范策略:基于 C++ 语言的布隆过滤器算法剖析[如何防止员工泄密]
企业运营过程中,防范员工泄密是信息安全领域的核心议题。员工泄密可能致使企业核心数据、商业机密等关键资产的流失,进而给企业造成严重损失。为应对这一挑战,借助恰当的数据结构与算法成为强化信息防护的有效路径。本文专注于 C++ 语言中的布隆过滤器算法,深入探究其在防范员工泄密场景中的应用。
115 8
|
4天前
|
传感器 机器学习/深度学习 算法
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)