posted in OJ题解  数据结构与算法 

Read on →
posted in 数据结构与算法 

二分查找算法在各种场合下经常会用到，在此总结一下它的标准代码。

代码

int binary_search(int array[], int n, int value)
{
	int left = 0;
	int right = n - 1;

	while (left <= right)
	{
		int mid = (left + right) >> 1;

		if (array[mid] < value)
			left = mid + 1;
		else if (array[mid] > value)
			right = mid + 1;
		else
			return mid;
	}

	return -1;
}

参考

http://blog.csdn.net/v_july_v/article/details/7093204

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40477343

posted in 数据结构与算法 

1. 冒泡排序 (Bubble Sort)  [1]

1.1 算法描述

冒泡排序过程中， 从前往后依次扫描每一对相邻元素， 一旦发现逆序即交换二者的位置。  这一过程称作一趟扫描交换。

以此类推， 最多进行n-1趟扫描交换， 整个序列就排序完成了。

算法的平均时间复杂度为O(n^2)， 空间复杂度O(1)， 是稳定排序算法。

1.2 代码实现

void bubble_sort(int a[], int n)
{
	bool sorted;
	int i;

	while (!sorted)
	{
		sorted = true;
		for (i = 1; i < n; i++)
		{
			if (a[i-1] > a[i])
			{
				int tmp = a[i-1];
				a[i-1] = a[i];
				a[i] = tmp;

				sorted = false;
			}
		}
		n--;
	}
}

2. 插入排序 (Insertion Sort)  [2]

2.1 算法描述

该算法将序列划分为两部分， 左侧的已排序部分和剩下的待排序部分， 一开始已排序部分为空， 待排序部分为整个序列。 

把待排序部分的第一个元素和已排序部分的元素从后往前依次进行比较， 直到找到合适的位置并插入进去。

如此重复直至待排序部分为空……

该算法平均时间复杂度为O(n^2)， 空间复杂度O(1), 是稳定排序算法。

2.2 代码实现

void insert_sort(int a[], int n)
{
	int i, j, temp;

	for (i = 1; i < n; i++) 
	{
		temp = a[i];
		for (j = i - 1; j >= 0 && temp < a[j]; j--)
			a[j+1] = a[j];

		a[j+1] = temp;
	}
}

3. 选择排序 (Selection Sort)    [3]

3.1 算法描述

该算法将序列划分为两部分， 左侧的已排序部分和剩下的待排序部分。 一开始已排序部分为空， 待排序部分为整个序列。 

接下来在待排序序列中找出最小值， 和待排序序列中最左侧的元素进行交换。 把已排序序列的边界右移一位。

如此重复n-1次……

算法的时间复杂度为Θ(n^2) ， 空间复杂度O(1)， 是不稳定排序算法。

3.2 代码实现

void selection_sort(int a[], int n)
{
	int i, j, min;
	for (i = 0; i < n - 1; i++)
	{
		min = i;
		for (j = i + 1; j < n; j++)
			if (a[j] < a[min])
				min = j;

		if (min != i)
		{
			int temp = a[i];
			a[i] = a[min];
			a[min] = temp;
		}
	}
}

4. 归并排序 (Merge Sort) [4]

4.1 算法描述

该算法采用分而治之的策略， 先把整个序列不断划分， 直至划分为单个元素， 

然后开始合并， 在合并的过程中进行排序。

算法的时间复杂度为O(nlogn)， 空间复杂度为O(n), 为稳定排序算法。

4.2 代码实现

void merge(int[], int, int, int);

void merge_sort(int arr[], int l, int r)
{

	if (r - l < 2)
		return;
	else
	{
		//divide and conquer
		int m = (l + r) / 2;
		merge_sort(arr, l, m);
		merge_sort(arr, m+1, r);
		merge(arr, l, m, r);
	}
}

//merge two array, arr[l]...arr[m] and arr[m+1]...arr[r]
void merge(int arr[], int l, int m, int r)
{
	int n1 = m - l + 1;
	int n2 = r - m;
	int a[n1], b[n2];

	for (int i = 0, int j = l; i < n1; i++, j++)
		a[i] = arr[j];

	for (int i = 0, int j = m + 1; i < n2; i++, j++)
		b[i] = arr[j];

	int i = 0;
	int j = 0;
	int k = l;
	while (i < n1 && j < n2)
	{
		if (a[i] <= b[j]) 
		{
			arr[k] = a[i];
			i++;
		} 
		else 
		{
			arr[k] = b[j];
			j++;
		}
		k++;
	}

	while (i < n1) 
	{
		arr[k] = a[i];
		k++;
		i++;
	}

	while (j < n2) 
	{
		arr[k] = b[j];
		k++;
		j++;
	}
}

5. 桶排序 (Bucket Sort) [5]

6. 计数排序 (Counting Sort) [6]

7. 基排序 (Radix Sort) [7]

8. 堆排序 (Heap Sort) [8]

8.1 算法描述

该算法可以说是选择排序的改进版本，把整个序列分为左侧的未排序序列（组织为大顶堆的形式）和右侧的已排序部分。一开始右侧的已排序部分为空，左侧的未排序的部分为整个序列。

接下来从左侧未排序部分取出最大元素， 把已排序序列的边界左移一位， 把取出的最大元素放到右侧已排序部分的最左侧。 

如此重复直至未排序部分（大顶堆）为空……

算法的时间复杂度为Θ(n*log(n)) ， 空间复杂度O(1)， 是不稳定排序算法。

8.2 代码实现 （需其他函数代码支持）

void head_sort(int a, int low, int high)
{
	PQ_complHeap H(a, low, high);  //floyd法建堆
	while (!H.empty())
		a[--high] = H.delMax();
}

9. 锦标赛排序 (Tournament Sort) [9]

10. 快速排序 (Quick Sort) [10]

10.1 算法描述

该算法和归并算法类似，快速排序也是采用分而治之的策略来提高排序效率的。所不同的是，归并排序的时间主要消耗在归并上， 而快速排序的时间主要消耗在划分上。

快速排序排序时， 首先把序列划分为两个子序列， 然后递归的对两个子序列进行快速排序。 直到划分到平凡情况，每个子序列的个数为1， 这时便返回。

问题的关键， 如何进行子序列的划分？

可以把该序列的第一个数移动到它排序后的正确位置，同时它左侧都是比它小的数， 它右侧都是比它大的数。 以该数作为轴， 将两边的数划分为两个子序列。

算法的平均时间复杂度为Θ(n*log(n))  ， 平均空间复杂度O(n*log(n))， 是不稳定排序算法。

10.2 代码实现

int partition(int a[], int lo, int hi);
void quick_sort(int a[], int lo, int hi)
{
	if (hi - lo < 2)
		return;
	else
	{
		int mid = partition(a, lo, hi);
		quick_sort(a, lo, mid);
		quick_sort(a, mid + 1, hi);
	}
}

int partition(int a[], int lo, int hi)
{
	int pivot = a[lo];
	while (lo < hi)
	{
		while ((lo < hi) && (pivot <= a[hi]))
			hi--;
		a[lo] = a[hi];
		while ((lo < hi) && (pivot >= a[lo]))
			lo++;
		a[hi] = a[lo];
	}
	a[lo] = pivot;
	return lo;
}

11. 希尔排序 (Shell Sort) [11]

12. 性能总结 [12]

          排序法          

          平均时间         

        最差情形       

          稳定度          

       额外空间         

                                                   备注                                           

冒泡

 O(n2)

  O(n2)

 稳定

O(1)

n小时较好

插入

  O(n2)

  O(n2)

稳定

O(1)

大部分已排序时较好

选择

 O(n2)

 O(n2)

不稳定

O(1)

n小时较好

归并

 O(nlogn)

 O(nlogn)

稳定

O(1)

 n大时较好

桶






基数

O(logRB)

O(logRB)

稳定

O(n)

B是真数(0-9)，R是基数(个十百)s是所选分组

堆

O(nlogn)

O(nlogn)

不稳定

O(1)

n大时较好

锦标赛






快速

O(nlogn)

O(n2)

不稳定 

O(nlogn)

n大时较好

Shell 

O(nlogn)  

O(ns) 1<s<2  

不稳定 

O(1)  



参考：

[1] 《数据结构》（C++语言版）（第3版） 邓俊辉  P5

[2] 《算法导论》

[3] http://en.wikipedia.org/wiki/Selection_sort

[4] 《数据结构》（C++语言版）（第3版） 邓俊辉  P63

[5]

[6]

[7]

[8] 《数据结构》（C++语言版）（第3版） 邓俊辉  P297

[9]

[10] 《数据结构》（C++语言版）（第3版） 邓俊辉  P335

[11]

[12] http://blog.csdn.net/iamfranter/article/details/6825207

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39400513

posted in 数据结构与算法 

前几天参加了美团的校招笔试， 结果状态不好， 答得跟屎一样， 现在考完了总结一下好了。

5. 旋转二维数组

SouthEast

分析

就是一道找规律的题

代码

#include <iostream>

using namespace std;

#define N 3

class Solution
{
public:
	void print_rotate_matrix(int matrix[N][N], int n)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < i + 1; j++)
				cout << matrix[j][j-i+n-1] << ' ';
			cout << endl;
		}

		for (int i = 0; i < n - 1; i++)
		{
			for (int j = 0; j < n - i - 1; j++)
				cout << matrix[i+j+1][j] << ' ';
			cout << endl;
		}
	}
};

int main()
{
	int matrix[N][N] = {1, 2, 3, 4, 5, 6, 7, 8, 9};

	Solution s;
	s.print_rotate_matrix(matrix, N);

	return 0;
}

参考

http://blog.csdn.net/cow__sky/article/details/39226677

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39399955

posted in 数据结构与算法  

/*
   2012年9月15日21:32:32
   了解队列
 */
#include <stdio.h>
#include <malloc.h>

typedef struct Queue
{
	int * pBase;
	int front;
	int rear;
}QUEUE;

void init(QUEUE *);               //初始化队列
bool full_queue(QUEUE *);         //判断是否满
bool en_queue(QUEUE *, int);      //入队
bool empty_queue(QUEUE *);        //判断是否为空
bool out_queue(QUEUE *, int *);   //出队
void traverse(QUEUE *);           //遍历队列

int main()
{
	QUEUE Q;
	int val;
	init(&Q);
	en_queue(&Q, 1);
	en_queue(&Q, 2);
	en_queue(&Q, 3);
	en_queue(&Q, 4);
	en_queue(&Q, 5);
	en_queue(&Q, 6);
	en_queue(&Q, 7);
	en_queue(&Q, 8);
	traverse(&Q);
	if (out_queue(&Q, &val))
		printf("出队成功，删除的元素是:%d\n", val);
	traverse(&Q);
	return 0;
}

void init(QUEUE * pQ)
{
	pQ->pBase = (int *)malloc(sizeof(int) * 6);
	pQ->front = pQ->rear = 0;
}
bool full_queue(QUEUE * pQ)
{
	if (((pQ->rear+1) % 6) == pQ->front)
		return true;
	else
		return false;
}
bool en_queue(QUEUE * pQ, int val)
{
	if (full_queue(pQ))
		return false;
	else
	{
		pQ->pBase[pQ->rear] = val;
		pQ->rear = (pQ->rear+1) % 6;
		return true;
	}
}
bool empty_queue(QUEUE * pQ)
{
	if (pQ->front == pQ->rear)
		return true;
	else
		return false;
}
bool out_queue(QUEUE * pQ, int * val)
{
	if (empty_queue(pQ))
		return false;
	else
	{
		*val = pQ->pBase[pQ->front];
		pQ->front = (pQ->front+1) % 6;
		return true;
	}
}
void traverse(QUEUE * pQ)
{
	if (empty_queue(pQ))
		printf("队列为空！\n");
	else
	{
		int i;
		for (i = pQ->front; i != pQ->rear; i = (i+1) % 6)
			printf("%d ", pQ->pBase[i]);
		printf("\n");
	}
}

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/7983127

posted in 数据结构与算法  

/*
   2012年9月11日11:45:30
   了解栈的构造方法
 */
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

typedef struct Node
{
	int data;
	struct Node * pNext;
}NODE, * PNODE;
typedef struct Stack
{
	PNODE pTop;
	PNODE pBottom;
}STACK, * PSTACK;

void init(PSTACK);             //初始化栈
void push(PSTACK, int);        //压栈
bool empty(PSTACK);            //判断栈是否为空
void traverse(PSTACK);         //遍历栈
void pop(PSTACK);              //出栈
void clear(PSTACK);            //清空栈

int main()
{
	STACK S;
	int val;
	/*测试初始化栈及压栈函数*/
	init(&S);
	push(&S, 1);
	push(&S, 2);
	push(&S, 3);
	push(&S, 4);
	push(&S, 5);
	traverse(&S);
	/*测试出栈*/
	pop(&S);
	traverse(&S);
	/*测试清空栈*/
	clear(&S);
	traverse(&S);

	return 0;
}

/*初始化栈——使pTop和pBottom指向同一节点*/
void init(PSTACK pS)
{
	pS->pBottom = (PNODE)malloc(sizeof(NODE));
	if (pS->pBottom == NULL)
	{
		printf("动态内存分配失败！\n");
		exit(-1);
	}
	pS->pBottom->pNext = NULL;
	pS->pTop = pS->pBottom;
	return;
}
/*压栈——创建一个新节点，连到定节点上面，把新节点标记为顶节点*/
void push(PSTACK pS, int val)
{
	PNODE pNew;
	pNew = (PNODE)malloc(sizeof(NODE));
	if (NULL == pNew)
	{
		printf("动态内存分配失败！\n");
		exit(-1);
	}
	pNew->data = val;
	pNew->pNext = pS->pTop;
	pS->pTop = pNew;
	return;
}
/*判断栈是否为空*/
bool empty(PSTACK pS)
{
	if (pS->pTop == pS->pBottom)
		return true;
	else
		return false;
}
/*遍历栈——定义临时变量temp，从pTop开始一直往下指*/
void traverse(PSTACK pS)
{
	if (empty(pS))
		printf("栈为空 ！\n");
	else
	{
		PNODE temp;
		temp = pS->pTop;
		printf("遍历栈：");
		while (temp != pS->pBottom)
		{
			printf("%d ", temp->data);
			temp = temp->pNext;
		}
		printf("\n");
	}
	return;
}
/*出栈—— pTop下移，且把原pTop占用的空间释放*/
void pop(PSTACK pS)
{
	if (empty(pS))
		printf("栈为空！\n");
	else
	{
		PNODE temp = pS->pTop;
		pS->pTop = pS->pTop->pNext;
		printf("被删除的栈的数据域为：%d\n", temp->data);
		free(temp);
	}
	return;
}
/*清空栈——类似出栈*/
void clear(PSTACK pS)
{
	if (empty(pS))
		printf("栈为空！\n");
	else
		while (pS->pTop != pS->pBottom)
		{
			PNODE temp = pS->pTop;
			pS->pTop = pS->pTop->pNext;
			free(temp);
		}
	return;
}

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/7966528

posted in 数据结构与算法  

/*
   2012年9月5日10:36:48
   了解联系链表数据结构
 */
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

typedef struct Node
{
	int data;                //数据域
	struct Node * pNext;     //指针域
}NODE, * PNODE;

PNODE create_list(void);   //创建链表
void traverse_list(PNODE); //遍历链表
bool is_empty(PNODE);      //判断链表是否为空
int length_list(PNODE);    //求链表长度
void sort_list(PNODE);     //链表排序
bool insert_list(PNODE pHead, int pos, int val);     //插入节点
bool delete_list(PNODE pHead, int pos, int * val);   //删除节点

int main()
{
	PNODE pHead = NULL;
	int val;

	pHead = create_list();
	traverse_list(pHead);
	insert_list(pHead, 3, 89);
	traverse_list(pHead);
	delete_list(pHead, 4, &val);
	traverse_list(pHead);



	//if (is_empty(pHead))
	// printf("链表为空\n");
	//else
	// printf("链表不为空\n");
	//printf("链表的长度为:%d\n", length_list(pHead));
	//sort_list(pHead);
	//traverse_list(pHead);

	return 0;
}

/*创建链表*/
PNODE create_list(void)
{
	int len;         //链表长度
	int val;         //临时存放数据域
	int i;

	/*创建头结点*/
	PNODE pHead;
	pHead = (PNODE)malloc(sizeof(NODE));
	if (NULL == pHead)
	{
		printf("动态分配内存失败\n");
		exit(-1);
	}

	/*创建尾节点*/
	PNODE pTail = pHead;

	/*追加节点*/
	printf("请输入您要创建节点的个数： len = ");
	scanf("%d", &len);
	for (i = 0; i < len; ++i)
	{
		printf("请输入第%d个数的数值：", i + 1);
		scanf("%d", &val);
		PNODE pNew = (PNODE)malloc(sizeof(NODE));
		if(NULL == pNew)
		{
			printf("动态分配内存失败\n");
			exit(-1);
		}
		pNew->data = val;
		pNew->pNext = NULL;
		pTail->pNext = pNew;
		pTail = pNew;
	}

	return pHead;
}
/*遍历链表*/
void traverse_list(PNODE pHead)
{

	PNODE p = pHead->pNext;

	printf("遍历链表结果为：\n");
	while(NULL != p)
	{
		printf("%d ", p->data);
		p = p->pNext;
	}

	printf("\n\n");
	return;
}
/*判断链表是否为空*/
bool is_empty(PNODE pHead)
{
	if (NULL == pHead->pNext)
		return true;
	else
		return false;
}
/*求链表长度*/
int length_list(PNODE pHead)
{
	PNODE p = pHead;
	int cnt = 0;

	while (NULL != p->pNext)
	{
		cnt++;
		p = p->pNext;
	}

	return cnt;
}

/*链表大小排序*/
void sort_list(PNODE pHead)
{
	int i, j, t;
	int len = length_list(pHead);
	PNODE p, q;
	/*理解泛型的概念，用p=p->pNext代替了p++*/
	for (i = 0, p = pHead->pNext; i < len-1; i++, p = p->pNext)   
	{
		for (j = i+1,  q = p->pNext; j < len; j++, q = q->pNext)
		{
			if (p->data > q->data)
			{
				t = p->data;
				p->data = q->data;
				q->data = t;
			}
		}
	}
}

/*插入节点*/
bool insert_list(PNODE pHead, int pos, int val)
{
	PNODE p = pHead;
	int i = 0;
	/*把p的指针移到pos的前一个节点*/
	while (i<pos-1 && NULL!=p)
	{
		p = p->pNext;
		i++;
	}
	/*增强程序健壮性，避免【pos为-1】 或者 【pos大于length】的情况，程序崩溃*/
	if (i>pos-1 || NULL==p)
		return false;
	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	if (NULL == pNew)
	{
		printf("动态内存分配失败\n");
		exit(-1);
	}
	pNew->data = val;
	pNew->pNext = p->pNext;
	p->pNext = pNew;
	return true;
}
/*删除节点*/
bool delete_list(PNODE pHead, int pos, int * val)
{
	int i = 0;
	PNODE p = pHead;
	while (NULL!=p->pNext && i<pos-1)
	{
		p = p->pNext;
		i++;
	}
	if (NULL==p->pNext || i>pos-1)
		return false;
	PNODE q = p->pNext;
	p->pNext = p->pNext->pNext;
	free(q);
	q = NULL;
	return true;
}

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/7945231

/** * RECOMMENDED CONFIGURATION VARIABLES: EDIT AND UNCOMMENT THE SECTION BELOW TO INSERT DYNAMIC VALUES FROM YOUR PLATFORM OR CMS. * LEARN WHY DEFINING THESE VARIABLES IS IMPORTANT: https://disqus.com/admin/universalcode/#configuration-variables*/ /* var disqus_config = function () { this.page.url = PAGE_URL; // Replace PAGE_URL with your page's canonical URL variable this.page.identifier = PAGE_IDENTIFIER; // Replace PAGE_IDENTIFIER with your page's unique identifier variable }; */ (function() { // DON'T EDIT BELOW THIS LINE var d = document, s = d.createElement('script'); s.src = 'https://chenzz.disqus.com/embed.js'; s.setAttribute('data-timestamp', +new Date()); (d.head || d.body).appendChild(s); })();