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 C/C++ 

简介

这大概是大二数据结构课上老师布置的一个作业， 当年忙着打DOTA所以直接抄同学的， 今天补上。。。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>

using namespace std;

class Solution
{
public:
	void generate_nums()
	{
		srand(time(NULL));
		for (auto &r : nums_)
			r = rand();
	}

	void save_nums(string file_name)
	{
		ofstream ofs(file_name);

		for (auto &r : nums_)
			ofs << &r << '\n';
		
		ofs.close();
	}

	void sort_nums()
	{
		sort(nums_.begin(), nums_.end());
	}
private:
	vector<int> nums_ = vector<int>(1000000);
};

int main()
{
	Solution s;

	s.generate_nums();		//generate 1 million nums
	s.save_nums("nums");	//save to file "nums"
	s.sort_nums();			//sort
	s.save_nums("nums2");	//save to file "nums2"

	return 0;
}

参考

http://blog.csdn.net/hackbuteer1/article/details/6574908

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

posted in OJ题解 

题目

https://oj.leetcode.com/problems/remove-nth-node-from-end-of-list/

分析

  1. 两个指针， 第一个指针先走n步， 然后两个指针一起走， 直到第一个指针走到结尾处， 此时第二个指针即为要删除的结点的上一个结点。

  2. 特别要注意的一点是， 如果要删除的结点是第一个结点， 要特别的处理一下， 因为第二个指针无法指向第一个结点的上一个结点。

代码

class Solution
{
public:
	ListNode *removeNthFromEnd(ListNode *head, int n)
	{
		ListNode *l, *r;

		l = head;
		r = head;
		for (int i = 0; i < n; i++)
			r = r->next;

		if (r == NULL)
		{
			ListNode *t = head;
			head = head->next;
			delete t;
		}
		else
		{
			while (r->next != NULL)
			{
				l = l->next;
				r = r->next;
			}
			ListNode *t = l->next;
			l->next = t->next;
			delete(t);
		}
		return head;
	}
};

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

posted in OJ题解 

题目：

https://oj.leetcode.com/problems/letter-combinations-of-a-phone-number/

分析：

DFS

代码：

class Solution
{
public:
	vector<string> letterCombinations(string digits)
	{
		string solution;
		dfs(digits, 0, solution);

		return res;
	}
	void dfs(string &digits, int index, string &solution)
	{
		if (index == digits.size())
		{
			res.push_back(solution);
			return;
		}
		else
		{
			for (auto &r : key[digits[index] - '0'])
			{
				solution.push_back(r);
				dfs(digits, index+1, solution);
				solution.pop_back();
			}
		}
	}
	vector<string> res;
	string key[10] = {"", 
		"", "abc", "def", 
		"ghi", "jkl", "mno",
		"pqrs", "tuv", "wxyz"};
};

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

posted in OJ题解 

题目

https://oj.leetcode.com/problems/maximum-subarray/

分析

  1. 一开始想用穷举法找出所有的子序列， 并求出最大的和，然后结果是超时了。

  2. 后来发现这道题是一道很巧妙的DP题，

首先我们先来求另一个问题， “数组A[]中包含最后一个元素的最大连续子序列的和为多少？”

包含最后一个元素的最大连续子序列的和有两种情况： 

最后一个元素和前面的元素构成一个子序列

或者最后一个元素自成一个子序列。

递归的求包含最后一个元素的最大连续子序列就是  f(n) = max(f(n-1), A[n]);

以此类推， 每个元素为结尾的最大连续子序列的和就求出来了，

  1. 在2中， 其中的最大值便是整个数列的最大连续子序列的和。

把上面递归用改写为递归的形式， 就是最终结果了。

代码

class Solution
{
public:
	int maxSubArray(int A[], int n)
	{
		int sum[n], res;

		sum[0] = A[0];
		res = sum[0];
		for (int i = 1; i < n; i++)
		{
			sum[i] = max(A[i], sum[i-1] + A[i]);
			res = max(res, sum[i]);
		}

		return res;
	}
};

参考

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

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

posted in OJ题解 

题目

https://oj.leetcode.com/problems/regular-expression-matching/

分析

  1. 普通字符和'.'的匹配很好解决， 直接匹配即可， 关键是'*'如何进行匹配

  2. 一开始我的想法是， ‘*’尽可能“贪婪”的匹配多个字符， 直到不再匹配为止。 然后在 s = "aaa", p = "a*a" 这个测试用例上跪了。。。

  3. 这说明'*'并不是尽可能多的进行匹配， 而是匹配一定数量的字符。 那么这个“一定数量”到底应该如何确定呢？ 

可以这样确定， 每匹配一个字符， 就跳过'*'继续匹配下面的， 成功了就返回true, 如果失败了就返回'*'处再多匹配一个字符， 再跳过'*'匹配后面的……以此类推。 显然这的返回现场就是通过递归算法的DFS来实现了。

代码

class Solution
{
public:
	bool isMatch(const char *s, const char *p)
	{
		//递归基
		if (*p == '\0')
			return (*s == '\0');

		//如果下一个字符不是'*'
		if (*(p+1) != '*')
			return (*s != '\0') && (*s == *p || *p == '.') && isMatch(s+1, p+1);

		//如果下一个字符是'*'
		if (isMatch(s, p+2))
			return true;
		while ((*s != '\0') && (*s == *p || *p == '.')) 
		{
			s++;
			if (isMatch(s, p+2))
				return true;
		}
		return false;
	}
};

参考

http://leetcode.com/2011/09/regular-expression-matching.html

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

/** * 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); })();