1，冒泡Bubble：从第0个开始，一直往上，与相邻的元素比较，如果下面的大，则交换。
Analysis：
Implementation：
void BubbleSort(int *pData, int iNum)
2，插入Insertion：与打扑克牌时整理牌很想象，假定第一张牌是有序的，从第二张牌开始，拿出这张牌来，往下比较，如果有比这张牌大的，则把它拨到上一个位置，直到找到比手上的这张更小的（或到顶了），
则把手上的这张牌插入到这张更小的牌的后面。
Analysis：
Implementation：
void InsertionSort(int *list, int length)
{
int i, j, temp
for (i = 1i <lengthi++)
{
temp = list[i]
j = i - 1
while ((j >= 0) &&(list[j] >temp))
{
list[j+1] = list[j]
j--
}
list[j+1] = temp
}
}
3，选择Selection：从所有元素中找到最小的放在0号位置，从其它元素（除了0号元素）中再找到最小的，放到1号位置，......。
Analysis：
Implementation：
void SelectionSort(int data[], int count)
{
int i, j, min, temp
for (i = 0i <count - 1i++)
{
/* find the minimum */
min = i
for (j = i+1j <countj++)
{
if (data[j] <data[min])
{
min = j
}
}
/* swap data[i] and data[min] */
temp = data[i]
data[i] = data[min]
data[min] = temp
}
}
4，快速Quick：先拿出中间的元素来（值保存到temp里），设置两个索引（index or pointer），一个从0号位置开始往最大位置寻找比temp大的元素；一个从最大号位置开始往最小位置寻找比temp小的元素，找到了或到顶了，则将两个索引所指向的元素
互换，如此一直寻找交换下去，直到两个索引交叉了位置，这个时候，从0号位置到第二个索引的所有元素就都比temp小，从第一个索引到最大位置的所有元素就都比temp大，这样就把所有元素分为了两块，然后采用前面的办法分别排序这两个部分。总的来
说，就是随机找一个元素（通常是中间的元素），然后把小的放在它的左边，大的放右边，对左右两边的数据继续采用同样的办法。只是为了节省空间，上面采用了左右交换的方法来达到目的。
Analysis：
Implementation：
void QuickSort(int *pData, int left, int right)
{
int i, j
int middle, iTemp
i = left
j = right
middle = pData[(left + right) / 2]//求中间值
do
{
while ((pData[i] <middle) &&(i <right)) //从左扫描大于中值的数
i++
while ((pData[j] >middle) &&(j >left)) //从右扫描小于中值的数
j--
if (i <= j) //找到了一对值
{
//交换
iTemp = pData[i]
pData[i] = pData[j]
pData[j] = iTemp
i++
j--
}
} while (i <= j)//如果两边扫描的下标交错，就停止（完成一次）
//当左边部分有值(left<j)，递归左半边
if(left <j)
QuickSort(pData, left, j)
//当右边部分有值(right>i)，递归右半边
if(right >i)
QuickSort(pData, i, right)
}
5，希尔Shell：是对Insertion Sort的一种改进，在Insertion Sort中，从第2个位置开始取出数据，每次都是与前一个（step/gap==1）进行比较。Shell Sort修改为，在开始时采用较大的步长step，
从第step位置开始取数据，每次都与它的前step个位置上的数据进行比较（如果有8个数据，初始step==4，那么pos(4)与pos(0)比较，pos(0)与pos(-4)，pos(5)与pos(1)，pos(1)与pos(-3)，
...... pos(7)与pos(3)，pos(3)与pos(-1)），然后逐渐地减小step，直到step==1。step==1时，排序过程与Insertion Sort一样，但因为有前面的排序，这次排序将减少比较和交换的次数。
Shell Sort的时间复杂度与步长step的选择有很大的关系。Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相对比较简单，它适合
于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。
Analysis：
Implementation：
template<typename RandomIter, typename Compare>
void ShellSort(RandomIter begin, RandomIter end, Compare cmp)
{
typedef typename std::iterator_traits<RandomIter>::value_type value_type
typedef typename std::iterator_traits<RandomIter>::difference_type diff_t
diff_t size = std::distance(begin, end)
diff_t step = size / 2
while (step >= 1)
{
for (diff_t i = stepi <size++i)
{
value_type key = *(begin+i)
diff_t ins = i// current position
while (ins >= step &&cmp(key, *(begin+ins-step)))
{
*(begin+ins) = *(begin+ins-step)
ins -= step
}
*(begin+ins) = key
}
if(step == 2)
step = 1
else
step = static_cast<diff_t>(step / 2.2)
}
}
template<typename RandomIter>
void ShellSort(RandomIter begin, RandomIter end)
{
typedef typename std::iterator_traits<RandomIter>::value_type value_type
ShellSort(begin, end, std::less<value_type>())
}
6，归并Merge：先将所有数据分割成单个的元素，这个时候单个元素都是有序的，然后前后相邻的两个两两有序地合并，合并后的这两个数据再与后面的两个合并后的数据再次合并，充分前面的过程直到所有的数据都合并到一块。
通常在合并的时候需要分配新的内存。
Analysis：
Implementation：
void Merge(int array[], int low, int mid, int high)
{
int k
int *temp = (int *) malloc((high-low+1) * sizeof(int))//申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
int begin1 = low
int end1 = mid
int begin2 = mid + 1
int end2 = high
for (k = 0begin1 <= end1 &&begin2 <= end2++k) //比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
{
if(array[begin1]<=array[begin2])
{
temp[k] = array[begin1++]
}
else
{
temp[k] = array[begin2++]
}
}
if(begin1 <= end1) //若第一个序列有剩余，直接拷贝出来粘到合并序列尾
{
memcpy(temp+k, array+begin1, (end1-begin1+1)*sizeof(int))
}
if(begin2 <= end2) //若第二个序列有剩余，直接拷贝出来粘到合并序列尾
{
memcpy(temp+k, array+begin2, (end2-begin2+1)*sizeof(int))
}
memcpy(array+low, temp, (high-low+1)*sizeof(int))//将排序好的序列拷贝回数组中
free(temp)
}
void MergeSort(int array[], unsigned int first, unsigned int last)
{
int mid = 0
if (first <last)
{
mid = (first+last)/2
MergeSort(array, first, mid)
MergeSort(array, mid+1,last)
Merge(array,first,mid,last)
}
}
由于PyQt的安装比较麻烦，尝试了几次都没有成功，便决定用spidermonkey，但若直接从官网下载和安装，由于涉及到js引擎等的安装，比较麻烦，经过试验验证，如下方法可以快速达到目的：1.spidermonkey下载及安装
1)下载 svn checkout http://python-spidermonkey.googlecode.com/svn/trunk spidermonkey
2）编译安装
python setup install
3)如果编译时出现
spidermonkey.pyx:82:3: Syntax error in simple statement list 这样错误：则修改spidermonkey.pyx:注释如下代码
#IF UNAME_MACHINE == "x86_64":
#ctypedef long jsval
#ELSE:
#ctypedef int jsval
增加：
ctypedef long jsval
4)如果编译时出现
spidermonkey.c:1323: error: invalid lvalue in assignment,则修改spidermonkey.c程序：
注释：
/*((PyObject *)((struct __pyx_obj_12spidermonkey_Context *)__pyx_v_self)->rt) = ((PyObject *)__pyx_v_rt)*/
新增：
((PyObject *)((struct __pyx_obj_12spidermonkey_Context *)__pyx_v_self)->rt) = (PyObject *)__pyx_v_rt
如果还是报以上错误，则新增的这条语句也去掉
2.如何在python中调用js:
ECASE)
con=regex.search(content)
rt = Runtime()
cx = rt.new_context()
jsCode= "var acc = g1656.substr(3,3) + da2ef.substr(5,5) + 'abc'" #注意：以分号结束
cx.eval_script(jsCode)
acc = cx.get_global('acc')
参考：#include"time.h&quo；#include<iostream>；usingnamespacestd；//{:多边形相交判断Begin；#defineLINEINTERSECT_CRO；#defineMAX(a,b)(((a)>；#defineMIN(a,b)(((a)<；typedefst下面代码可直接执行。#include "time.h "#include <iostream>using namespace std //{:多边形相交判断 Begin#define LINEINTERSECT_CROSS(ps,pe,p ((pe->x-ps->x)*(p->y-ps->y)-(p->x-ps->x)*(pe->y-ps->y))#define MAX(a,b) ( ((a)>(b))?(a):(b) )#define MIN(a,b) ( ((a) <(b))?(a):(b) )typedef struct XPOINT32Ftag{float xfloat y}POINT32F//返回true 为相交，false为不相交bool cxLineIntersect32F(POINT32F *p1, POINT32F *p2 , POINT32F *p3, POINT32F *p4){if(MAX(p1->x,p2->x)>=MIN(p3->x,p4->x) &&MAX(p3->x,p4->x)>=MIN(p1->x,p2->x) &&MAX(p1->y,p2->y)>=MIN(p3->y,p4->y) &&MAX(p3->y,p4->y)>=MIN(p1->y,p2->y) &&LINEINTERSECT_CROSS(p1,p2,p3)*LINEINTERSECT_CROSS(p1,p2,p4) <=0 &&LINEINTERSECT_CROSS(p3,p4,p1)*LINEINTERSECT_CROSS(p3,p4,p2) <=0)return trueelsereturn false}//判断两个多边形是否交叉，返回值0,1//0为不相交,1为相交int cxPolyCross2_32F( POINT32F *p1,int nP1,POINT32F *p2,int nP2){int i,j POINT32F *ptr00,*ptr01,*ptr10,*ptr11 for ( ptr00=p1+nP1-1,ptr01=p1,i=0i <nP1i++,ptr00=ptr01,ptr01++ ){for ( ptr10=p2+nP2-1,ptr11=p2,j=0j <nP2j++,ptr10=ptr11,ptr11++ ){if( cxLineIntersect32F(ptr00,ptr01,ptr10,ptr11) ){return 1 }}}return 0 }//:}多边形相交判断 End//******************************************************///{:测试代码 Begin//随机产生点坐标,fmin为坐标的最小值，fmax为坐标的最大值POINT32F randPoint(float fmin,float fmax){POINT32F point int fd = (int)(fmax-fmin)point.x = (rand()%fd)+fmin point.y = (rand()%fd)+fmin return point }int main(){int nLines = 10000 POINT32F *rgn0 = new POINT32F[nLines]POINT32F *rgn1 = new POINT32F[nLines]for ( int i=0i <nLinesi++ ){rgn0[i] = randPoint(0,1000)//多边形1的坐标从0到1000rgn1[i] = randPoint(1200,10000)//多边形2的坐标从1200到10000，确保两个多边形不相交，这样运算的时间能够体现出来}//开始计时time_t tBegin = clock() //判断两多边形是否相交cxPolyCross2_32F(rgn0,nLines,rgn1,nLines) //结束计时time_t tEnd = clock() time_t tDif = tEnd-tBegin cout <<"A边数: " <<nLines <<" B边数: " <<nLines <<endl cout <<"用时: " <<tDif <<"毫秒 " <<endl return 0}
