算法总结

不可能都完全记住那么多的算法.
常用算法,拿过来就可以写出来
不常用的,拿起书来,看10分钟,就能理解算法(因为以前记过).
对以前没有记过的算法,就不好说了,难的可能要研究好几天.
这样就可以了.

应该熟练掌握的常用的算法应该有:
各种排序算法（插入排序、冒泡排序、选择排序，快速排序，堆排序，归并排序）
线性表(一般的线性表,栈,队列)的插入和删除
二叉树的遍历（前序，中序，后序）
图的遍历（深度优先，广度优先）
二分法查找，排序二叉树，Hash查找（处理冲突的方法）。

常见排序算法总结

1、稳定排序和非稳定排序

简单地说就是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就说这种排序方法是稳定的。反之，就是非稳定的。要注意的是，排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。
比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为a1,a2,a4,a3,a5，则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4,a2,a3,a5就不是稳定的了。

2、内排序和外排序

在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序；
在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。

3、算法的时间复杂度和空间复杂度

所谓算法的时间复杂度，是指执行算法所需要的计算工作量。
一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。

一.插入排序

首先新建一个空列表，用于保存已排序的有序数列（我们称之为"有序列表"）。
从原数列中取出一个数，将其插入"有序列表"中，使其仍旧保持有序状态。
重复2号步骤，直至原数列为空。
插入排序的平均时间复杂度为平方级的，效率不高，但是容易实现。它借助了"逐步扩大成果"的思想，使有序列表的长度逐渐增加，直至其长度等于原列表的长度。

①.直接插入排序(稳定)
接插入排序的过程为：在插入第i个记录时，R1,R2,..Ri-1已经排好序，将第i个记录的排序码Ki依次和R1,R2,..,Ri-1的排序码逐个进行比较，找到适当的位置。使用直接插入排序，对于具有n个记录的文件，要进行n-1趟排序。

代码如下:

#include<iostream>
using namespace std;

void Dir_Insert(int arr[],int len);

int main()
{
	int arr[]={23,31,4,9,12,7};
	int const len=sizeof(arr)/sizeof(arr[0]);
	for(int i=0;i<len;i++)
		cout<<"arr["<<i<<"]:"<<arr[i]<<endl;
	Dir_Insert(arr,len);
	cout<<"after sort: "<<endl;
	for(int i=0;i<len;i++)
		cout<<"arr["<<i<<"]:"<<arr[i]<<endl;
}

void Dir_Insert(int arr[],int len) //直接插入排序
{
	int j,t;
	for(int i=1;i<len;i++)
	{
		t=arr[i];
		j=i-1;
		while(arr[j]>t)
		{
			arr[j+1]=arr[j];
			j--;
		}
		arr[j+1]=t;
	}
}

arr[0]:23
arr[1]:31
arr[2]:4
arr[3]:9
arr[4]:12
arr[5]:7
after sort:
arr[0]:4
arr[1]:7
arr[2]:9
arr[3]:12
arr[4]:23
arr[5]:31
Press any key to continue . . .

②.希尔排序(不稳定)：
希尔(Shell)排序的基本思想是：先取一个小于n的整数d1作为第一个增量把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取得第二个增量d2<d1重复上述的分组和排序，直至所取的增量di=1，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。
一般取d1=n/2，di+1=di/2。如果结果为偶数，则加1，保证di为奇数。
希尔排序是不稳定的，希尔排序的执行时间依赖于增量序列，其平均时间复杂度为O(n^1.3).

代码如下:

http://bearzheng.blog.163.com/blog/static/1300271332009912357873/