排序算法: 归并排序,快速排序,3趟快速排序

收藏到CSDN网摘

归并排序(Merge sort)是另外一个很有名的排序算法.其思想是: divide and conquer.将原序列分割为2个小序列,排序之后再merge到一起.分割部分可以递归完成,递归出口是序列长度为1,直接返回序列.
Bottom_Up归并排序是归并排序的非递归实现,从size=2开始,不断merge,直到所有元素排序完毕.

快速排序(Quick sort)是对随机打乱后的数组,用2个指针分别从左边和右边来扫描元素,在排序过程中保证:对某个元素j,a[j]已经被排好,其左边所有元素都不大于它,而右边所有元素都不小于它.j这个位置由分割函数partition()返回.具体实现(随机排序可以不用,用median-3来选择一个元素作为a[lo]即可):
(a) partition分割(设置j)
i, j = lo, hi, 当i<j时,repeat:
- i从左往右scan,只要a[i]<a[lo],扫描停止时,a[i]>=a[lo]
- j从右往左scan,只要a[j]>a[lo],扫描停止时,a[j]<=a[lo]
- 交换a[i]与a[j]
- 循环结束后交换a[lo]与a[j].
- 返回j
(b) 递归调用排序lo到j-1
(c) 递归调用排序j+1到hi

3-way快速排序是对快速排序的改进,因为快速排序算法的扫描方法在有多个与a[lo]相当的元素时,仍然需要交换元素(非必要交换),因此,可以引入lt和gt2个元素,来保证lt-gt之间的元素都等于v,lt左边不大于v,gt右边不小于v.具体实现:
(a): partition分割(同时设置lt与gt)
lt = lo, gt = hi, i = lo, v = a[lo]
选择v作为partitioning元素a[lo](可与快速排序选择方法相同)
i从左往右开始扫描:
- a[i]<v: 交换a[lt]与a[i], lt++, i++
- a[i]>v: 交换a[gt]与a[i], gt--
- a[i]==v: i++
(b) 递归调用排序lo到lt-1
(c) 递归调用gt+1到hi

python实现如下(包含上次写过的希尔排序,插入排序与选择排序):

排序算法:选择排序,插入排序与希尔排序

收藏到CSDN网摘
常用排序算法之:选择排序,插入排序与希尔排序

这是非常经典的3个排序算法,在各种acm题目和日常编程中时有使用.

栈的push、pop序列判定

收藏到CSDN网摘


ACM经常会碰到的一个题目: 给定一个输出序列,判断其是否可能是元素按顺序压栈后的push/pop序列.(假设没有相同元素)

其解法是构造一辅助栈,然后开始扫描输出序列的每一个元素(视为当前元素):

零钱兑换方法问题

收藏到CSDN网摘


ACM经常有换零钱的问题,例如将一元的纸币兑换成5角,2角,1角,5分,2分和1分的硬币,有多少种兑换方法?根据纸币面额和硬币种类,问题的复杂程度不同(例如欧拉工程就有一道类似题目,兑换英国的钱币),最简单的办法是暴力求解,可用多层循环求解,一般循环层数可以比硬币种类少1,因为最后一个1分的硬币可以用前面求和<=(小于等于)面额来化简.如果小于面额,说明有多个1分币,如果恰好等于面额,则没有1分币.不过如果硬币种类特别多,循环的方法将不是一个理想的方法(当然,只要硬币给定,循环的代码总是能写出来的,时间足够,计算机也的确可以运行得出结果).

这类问题经过变换可以变为"一个大数如何写成几个小数之和的形式"的问题,此类问题的通解应当是通过分析来递归求解.

com.sec.android.app.twlauncher error fix

收藏到CSDN网摘
手机要更新输入法,内存不够,就把samsung自带的几个东西给删除了.然后准备回退到桌面时开始报com.sec.android.app.twlauncher error,点了force stop还是死循环.搜索了一下基本解法都是reset factory settings,但是这样等于format系统了,app都会丢失.不值得.

仔细观察下,twlauncher难道是samsung的touchwiz UI的launcher?那说明是准备回到桌面时调用launcher出错了,可能没删除了.尝试解决办法如下:

Python Tips 之 下载网络文件

收藏到CSDN网摘

有时候需要爬虫去下载一些网络文件(图片,文档等),如果页面有来源验证,需要伪装成浏览器访问.保存就是很简单的一句话: