码力欧

import random


def find_max_crossing_subarray(A, low, mid, high):
    """
    求跨越两个数组的最大字数组
    :param A:
    :param low:
    :param mid:
    :param high:
    :return:
    """
    left_sum = A[mid]
    left_index = mid
    sum = 0
    for left in range(mid, low - 1, -1):
        sum = sum + A[left]
        if sum > left_sum:
            left_sum = sum
            left_index = left

    right_sum = A[mid + 1]
    right_index = mid + 1
    sum = 0
    for right in range(mid + 1, high + 1):
        sum = sum + A[right]
        if sum > right_sum:
            right_sum = sum
            right_index = right
    return left_index, right_index, left_sum + right_sum


def find_max_subarray(A, low, high):
    """
    寻找数组中的最大子数组
    :param A:
    :param low:
    :param high:
    :return:
    """
    if low == high:
        return low, high, A[low]
    else:
        # 求中值
        mid = (low + high) / 2
        # 求左子数组最大子数组
        left_low, left_high, left_sum = find_max_subarray(A, low, mid)
        # 求右子数组最大子数组
        right_low, right_high, right_sum = find_max_subarray(A, mid + 1, high)
        # 求跨两个子数组的最大子数组
        cross_low, cross_high, cross_sum = find_max_crossing_subarray(A, low, mid, high)
        # 选出最大子数组
        if left_sum >= right_sum and left_sum >= cross_sum:
            return left_low, left_high, left_sum
        elif right_sum >= left_sum and right_sum >= cross_sum:
            return right_low, right_high, right_sum
        elif cross_sum >= left_sum and cross_sum >= right_sum:
            return cross_low, cross_high, cross_sum


if __name__ == "__main__":
    random_list = [random.randint(-100, 100) for _ in range(100)]
    print random_list
    alow, ahigh, asum = find_max_subarray(random_list, 0, len(random_list) - 1)
    print random_list[alow: ahigh + 1], asum

# -*- coding:utf-8 -*-
# 插入排序，两层遍历，以一个位置为基准，不断向前遍历，将比基准位置大的数调整到基准位置。
def insertion_sort(sort_list):
    iter_len = len(sort_list)
    if iter_len < 2:
        return sort_list
    for i in range(1, iter_len):
        key = sort_list[i]
        j = i - 1
        while j>=0 and sort_list[j]>key:
            sort_list[j+1] = sort_list[j]
            j -= 1
        sort_list[j+1] = key
    return sort_list
if __name__ == "__main__":
    sort_list = [4,2,7,3,1,9,33,25,46,21,45,22]
    print sort_list
    print insertion_sort(sort_list)

def bubble_sort(sort_list):
    iter_len = len(sort_list)
    if iter_len < 2:
        return sort_list
    for i in range(iter_len-1):
        for j in range(iter_len-i-1):
            if sort_list[j] > sort_list[j+1]:
                sort_list[j], sort_list[j+1] = sort_list[j+1], sort_list[j]
    return sort_list
if __name__ == "__main__":
    sort_list = [4,2,7,3,1,9,33,25,46,21,45,22]
    print sort_list
    print bubble_sort(sort_list)

# -*- coding:utf-8 -*-
# 向后遍历，选择最小值进行交换。
def selection_sort(sort_list):
    iter_len = len(sort_list)
    if iter_len < 2:
        return sort_list
    for i in range(iter_len-1):
        smallest = sort_list[i]
        location = i
        for j in range(i, iter_len):
            if sort_list[j] < smallest:
                smallest = sort_list[j]
                location = j
        if i != location:
            sort_list[i], sort_list[location] = sort_list[location], sort_list[i]
    return sort_list
if __name__ == "__main__":
    sort_list = [4,2,7,3,1,9,33,25,46,21,45,22]
    print sort_list
    print selection_sort(sort_list)

class Merge_sort(object):
    def _merge(self, alist, p, q, r):
        left = alist[p:q+1]
        right = alist[q+1:r+1]
        for i in range(p, r+1):
            if len(left)>0 and len(right)>0:
                if left[0]<=right[0]:
                    alist[i] = left.pop(0)
                else:
                    alist[i] = right.pop(0)
            elif len(right)==0:
                alist[i] = left.pop(0)
            elif len(left)==0:
                alist[i] = right.pop(0)
 
    def _merge_sort(self, alist, p, r):
        if p<r:
            q = int((p+r)/2)
            self._merge_sort(alist, p, q)
            self._merge_sort(alist, q+1, r)
            self._merge(alist, p, q, r)
 
    def __call__(self, sort_list):
        self._merge_sort(sort_list, 0, len(sort_list)-1)
        return sort_list
if __name__ == "__main__":
    sort_list = [4,2,7,3,1,9,33,25,46,21,45,22]
    print sort_list
    merge = Merge_sort()
    print merge(sort_list)

class Quick_sort(object):
    def _partition(self, alist, p, r):
        i = p-1
        x = alist[r]
        for j in range(p, r):
            if alist[j]<=x:
                i += 1
                alist[i], alist[j] = alist[j], alist[i]
        alist[i+1], alist[r] = alist[r], alist[i+1]
        return i+1
 
    def _quicksort(self, alist, p, r):
        if p<r:
            q = self._partition(alist, p, r)
            self._quicksort(alist, p, q-1)
            self._quicksort(alist, q+1, r)
 
    def __call__(self, sort_list):
        self._quicksort(sort_list, 0, len(sort_list)-1)
        return sort_list
if __name__ == "__main__":
    sort_list = [4,2,7,3,1,9,33,25,46,21,45,22]
    print sort_list
    quick = Quick_sort()
    print quick(sort_list)

import sys
sys.setrecursionlimit(99999)

import random
class Random_quick_sort(object):
    
    def _randomized_partition(self, alist, p, r):
        i = random.randint(p, r)
        alist[i], alist[r] = alist[r], alist[i]
        return self._partition(alist, p, r)
    def _partition(self, alist, p, r):
        i = p-1
        x = alist[r]
        for j in range(p, r):
            if alist[j]<=x:
                i += 1
                alist[i], alist[j] = alist[j], alist[i]
        alist[i+1], alist[r] = alist[r], alist[i+1]
        return i+1
    def _quicksort(self, alist, p, r):
        if p<r:
            q = self._randomized_partition(alist, p, r)
            self._quicksort(alist, p, q-1)
            self._quicksort(alist, q+1, r)
 
    def __call__(self, sort_list):
        self._quicksort(sort_list, 0, len(sort_list)-1)
        return sort_list
if __name__ == "__main__":
    sort_list = [4,2,7,3,1,9,33,25,46,21,45,22]
    print sort_list
    random_quick = Random_quick_sort()
    print random_quick(sort_list)

def quick_sort_2(sort_list):
    if len(sort_list)<=1:
        return sort_list
    return quick_sort_2([lt for lt in sort_list[1:] if lt<sort_list[0]]) + \
           sort_list[0:1] + \
           quick_sort_2([ge for ge in sort_list[1:] if ge>=sort_list[0]])
if __name__ == "__main__":
    sort_list = [4,2,7,3,1,9,33,25,46,21,45,22]
    print sort_list
    print quick_sort_2(sort_list)

class Counting_sort(object):
    def _counting_sort(self, alist, k):
        alist3 = [0 for i in range(k)]
        alist2 = [0 for i in range(len(alist))]
        for j in alist:
            alist3[j] += 1
        for i in range(1, k):
            alist3[i] = alist3[i-1] + alist3[i]
        for l in alist[::-1]:
            alist2[alist3[l]-1] = l
            alist3[l] -= 1
        return alist2
 
    def __call__(self, sort_list, k=None):
        if k is None:
            import heapq
            k = heapq.nlargest(1, sort_list)[0] + 1
        return self._counting_sort(sort_list, k)
if __name__ == "__main__":
    sort_list = [4,2,7,3,1,9,33,25,46,21,45,22]
    print sort_list
    counting = Counting_sort()
    print counting(sort_list)

def makeblod(fn):
    def wrapped():
        return '<b>'+fn()+'</b>'
    return wrapped

def makeitalic(fn):
    def wrapped():
        return '<i>'+fn()+'</i>'
    return wrapped

@makeblod
@makeitalic
def hello():
    return 'hello world'

print hello()

def deco(arg):
    def _deco(func):
        def __deco():
            print "before %s called [%s]." % (func.__name__, arg)
            func()
            print "after %s called [%s]." % (func.__name__, arg)
        return __deco
    return _deco

@deco("mymodule")
def myfunc():
    print "myfunc() called."
myfunc()

#region 伪彩色图像处理

/// <summary>
/// 伪彩色图像处理
/// 博客园-初行 http://www.cnblogs.com/zxlovenet
/// 日期：2014.2.14
/// </summary>
/// <param name="bmp">传入的灰度图像</param>
/// <param name="method">使用何种方法，false强度分层法,true灰度级-彩色变换法</param>
/// <param name="seg">强度分层中的分层数</param>
/// <returns>返回伪彩色图像</returns>
private Bitmap gcTrans(Bitmap bmp, bool method, byte seg)
{
    if (bmp != null)
    {
        if (System.Drawing.Imaging.PixelFormat.Format24bppRgb == bmp.PixelFormat)
        {
            Rectangle rect = new Rectangle(0, 0, bmp.Width, bmp.Height);
            System.Drawing.Imaging.BitmapData bmpData = bmp.LockBits(rect, System.Drawing.Imaging.ImageLockMode.ReadWrite, bmp.PixelFormat);
            IntPtr ptr = bmpData.Scan0;
            int bytes = bmp.Width * bmp.Height * 3;
            byte[] grayValues = new byte[bytes];
            System.Runtime.InteropServices.Marshal.Copy(ptr, grayValues, 0, bytes);
            bmp.UnlockBits(bmpData);

            byte[] rgbValues = new byte[bytes];
            //清零
            Array.Clear(rgbValues, 0, bytes);
            byte tempB;

            if (method == false)
            {
                //强度分层法
                for (int i = 0; i < bytes; i += 3)
                {
                    byte ser = (byte)(256 / seg);
                    tempB = (byte)(grayValues[i] / ser);
                    //分配任意一种颜色
                    rgbValues[i + 1] = (byte)(tempB * ser);
                    rgbValues[i] = (byte)((seg - 1 - tempB) * ser);
                    rgbValues[i + 2] = 0;
                }
            }
            else
            {
                //灰度级-彩色变换法
                for (int i = 0; i < bytes; i += 3)
                {
                    if (grayValues[i] < 64)
                    {
                        rgbValues[i + 2] = 0;
                        rgbValues[i + 1] = (byte)(4 * grayValues[i]);
                        rgbValues[i] = 255;
                    }
                    else if (grayValues[i] < 128)
                    {
                        rgbValues[i + 2] = 0;
                        rgbValues[i + 1] = 255;
                        rgbValues[i] = (byte)(-4 * grayValues[i] + 2 * 255);
                    }
                    else if (grayValues[i] < 192)
                    {
                        rgbValues[i + 2] = (byte)(4 * grayValues[i] - 2 * 255);
                        rgbValues[i + 1] = 255;
                        rgbValues[i] = 0;
                    }
                    else
                    {
                        rgbValues[i + 2] = 255;
                        rgbValues[i + 1] = (byte)(-4 * grayValues[i] + 4 * 255);
                        rgbValues[i] = 0;
                    }
                }

            }

            bmp = new Bitmap(bmp.Width, bmp.Height, System.Drawing.Imaging.PixelFormat.Format24bppRgb);
            bmpData = bmp.LockBits(rect, System.Drawing.Imaging.ImageLockMode.ReadWrite, bmp.PixelFormat);
            ptr = bmpData.Scan0;

            System.Runtime.InteropServices.Marshal.Copy(rgbValues, 0, ptr, bytes);
            bmp.UnlockBits(bmpData);

            return bmp;
        }
        else
        {
            return null;
        }
    }
    else
    {
        return null;
    }
}
#endregion