ITPub博客

首页 > 应用开发 > IT综合 > 转载:记录python几个算法:

转载:记录python几个算法:

IT综合 作者:yarking207 时间:2017-09-28 16:24:46 0 删除 编辑
转载自:http://blog.csdn.net/laodengbaiwe0838/article/details/52373891
(一)插入排序

插入排序原址排序输入的数,算法在数组A中重排这些数,

在任何时候,最多只有常数个数字存储在数组外部。

插入排序是原地排序,基本无需外部空间。

从第二个元素开始,依次遍历全部数组。

其中,前半截为已排好的有序数组而后半截为待排序的无序数组。

每个元素从后向前依次对比,直到找到自己的位置。

插入排序是稳定排序。

def insert_sort(list1):
    for j in range(1,len(list1)): # 从第二个元素开始遍历,依次将元素放在指定位置
        key = list1[j] #记录当前值
        i = j -1 #将当前值从当前位置之前逆序依次比较
        while i>=0 and list1[i] >key:#如果当前值小于之前值,则说明当前值位于之前值的前面
            list1[i+1] = list1[i] #将大于当前值的元素依次后移一位,给当前值留位置
            i -=1
        list1[i+1] = key # 将当前值插入第一个小于它的值的后面
    return list1

if __name__ == "__main__":
    list1 = [380,22,64,75,327,98]
    list2 = ["wang","zhe","tian","jin","da","xue"]
    ordered_list1 = insert_sort(list1)
    ordered_list2 = insert_sort(list2)
    print(ordered_list1) #[2,3,4,5,6,7]
    print(ordered_list2) #['da']

(2)冒泡排序

冒泡排序原址排序输入的数,算法在数组A中重排这些数,

在任何时候,最多只有常数个数字存储在数组外部。

冒泡排序是原地排序,基本无需外部空间。

冒泡排序依次循环数组,每轮循环从前向后依次比较两个元素,排列使得后一个元素总是大于前一个元素。

因此,每轮循环可以保证当前未排序的列表中最大的元素放置在列表末尾。

即每轮循环后,可以使得未排序的列表长度减1。

重复直到列表仅剩唯一一个元素。

冒泡排序是稳定排序。

Python实现代码如下:

  1. # -*- coding: utf-8 -*-  
    def bubbleSort(bubbleList):  
        listLength = len(bubbleList)   #计算排序列表的长度  
        while listLength > 0:  
            for i in range(listLength - 1):  
                if bubbleList[i] > bubbleList[i+1]:  
                   temp = bubbleList[i+1]  
                   bubbleList[i+1] = bubbleList[i]  
                   bubbleList[i] = temp   #交换bubbleList[i]与bubbleList[i+1]的值  
            listLength -= 1   #每轮排序结束后,最后一个元素已经是最大的。因此只需要排前N-1个元素即可。  
        return bubbleList  
          
    if __name__ == '__main__':  
        list1 = [3,2,4,6,7,5]  
        list2 = ["wang", "zhe", "tian", "jin", "da", "xue"]  
        ordered_list1 = bubbleSort(list1)  
        ordered_list2 = bubbleSort(list2)  
        print(ordered_list1) #[2, 3, 4, 5, 6, 7]  
        print(ordered_list2) #['da', 'jin', 'tian', 'wang', 'xue', 'zhe'] 


(3)

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。

归并排序是通过递归和合并来实现的。

即首先将一个列表分为两个字列表,字列表长度为1。然后在依次合并,使得合成的列表有序。

归并排序的时间复杂度是nlogn。空间复杂度是n。

归并排序是稳定排序。

Python的实现代码如下:


# -*- coding: utf-8 -*-  
def mergeSort(lists):  
    if len(lists) <= 1:  #当数组长度为1时,则无需排序。  
        return lists  
    num = int(len(lists) / 2)  #将一个数组分为两个部分  
    left = mergeSort(lists[:num])  #分别对左右两个部分进行排序  
    right = mergeSort(lists[num:])  
    return merge(left, right)   #将左右两个有序数组合并为一个有序数组  
      
def merge(left, right):  
    r, l = 0, 0  #初始化左右索引为0  
    result = []   #初始化结果列表  
    while l < len(left) and r < len(right): #当左右索引都尚未达到列表长度时。  
        if left[l] < right[r]:               #如果左列表的值小于右列表的值  
            result.append(left[l])           #将左列表当前值存入结果列表中  
            l += 1                           #左列表索引加1  
        else:  
            result.append(right[r])          #否则将右列表当前值存入结果列表中  
            r += 1                          #右列表索引加1  
    result += right[r:]                     #将剩余元素存入结果列表中  
    result += left[l:]  
    return result  
      
if __name__ == '__main__':  
    list1 = [3,2,4,6,7,5]  
    list2 = ["wang", "zhe", "tian", "jin", "da", "xue"]  
    ordered_list1 = mergeSort(list1)  
    ordered_list2 = mergeSort(list2)  
    print (ordered_list1) #[2, 3, 4, 5, 6, 7]  
    print (ordered_list2) #['da', 'jin', 'tian', 'wang', 'xue', 'zhe']

(4)

快速排序是指:

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

快速排序在平均情况下时间复杂度为nlogn。

但是在最坏情况(本身为正序或者逆序时),时间复杂度为n*n。

快速排序是不稳定排序。即对于本身值相同的元素,在经过快速排序后,元素的先后位置可能会发生变化。

一趟快速排序的算法是:

1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;

2)以第一个数组元素作为关键数据,赋值给key,即key=A[0];

3)从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j],将A[j]和A[i]互换;

4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]互换;

5)重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。

Python的实现方式如下:


# -*- coding: utf-8 -*-  
def quickSortFunction(L, low, high):  
    i = low     #i表示被排序列表的起点  
    j = high    #j表示被排序列表的终点  
    if i >= j: #若当起点和终点重合或起点在终点后时,则无需进一步排序  
        return L  
    key = L[i]       #将起点元素选为被对比元素  
    while i < j:                            #当起点与终点尚未重合时  
        while i < j and L[j] >= key:       #找到第一个小于key的元素的位置  
            j -= 1  
        L[i] = L[j]              #将第一个小于key元素的值放入key元素的位置  
        while i < j and L[i] <= key:   #找到第一个大于key元素值,放入刚才小于key元素的位置  
            i += 1  
        L[j] = L[i]  
    L[i] = key    #当i和j重合时,将key元素放置在重合位置。表示该位置前的元素都小于该元素,而该位置后的元素都大于该元素。  
    quickSortFunction(L, low, i-1)   #利用归并的方法继续对low到i-1和j+1到high的部分进行排序  
    quickSortFunction(L, j+1, high)  
    return L  
      
def quickSort(list1):              #调用quickSortFunction进行快速排序  
    return quickSortFunction(list1, 0, len(list1)-1)  #low和high分别为0和len-1,表示对列表整体进行快速排序  
      
if __name__ == '__main__':  
    list1 = [3,2,4,6,7,5,1,8,10,9]  
    list2 = ["wang", "zhe", "tian", "jin", "da", "xue"]  
    ordered_list1 = quickSort(list1)  
    ordered_list2 = quickSort(list2)  
    print (ordered_list1)             #[2, 3, 4, 5, 6, 7]  
    print (ordered_list2)             #['da', 'jin', 'tian', 'wang', 'xue', 'zhe']  


(5)堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。

可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆,是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值,即A[PARENT[i]] >= A[i]。

在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的要求可知,最大的值一定在堆顶。

堆排序首先将待排序的数组存入堆中,并将堆构造为最大/最小堆。再依次从堆中取出堆顶元素,从而得到有序数组。

构造堆时,所用的方法为从最底层有子节点的节点开始依次向上处理。

取出顶元素恢复堆时则是先将末尾元素与顶元素交换位置,在对顶元素进行下沉处理即可。

堆排序是不稳定排序。即相同的元素再经过堆排序后,其先后位置可能发生变化。

堆排序的时间复杂度为N*logN。

Python的代码实现如下:

[python] view plain copy
  1. # -*- coding: utf-8 -*-  
  2. #用列表表示一个堆,其中列表中索引为0的位置为空。从索引1开始存放元素。  
  3. def parent(i):    #在堆中,某个节点的父节点为其索引值整除2。例如索引为4的父节点的索引为2。索引为9的父节点的索引为4。  
  4.     return i/2  
  5.   
  6. def left(i):     #某个节点的左子节点的索引为i*2  
  7.     return i*2  
  8.   
  9. def right(i):    #某个节点的右子节点的索引为i*2+1  
  10.     return i*2+1  
  11.   
  12. class Heap:     #堆的数据结构类  
  13.     def __init__(self, heapList=[None]):   #对堆进行初始化。没有给堆初始列表时,初始化为仅包含一个None元素的列表。  
  14.         self.heapList = [None] + heapList    #有初始化列表时,堆列表为初始化列表前插入None元素  
  15.   
  16.     def max_heapfy(self, i):   #表明对i节点进行最大堆恢复  
  17.         if (i*2) > self.length-1:   #该元素没有子节点时  
  18.             maxIndex = i  
  19.         elif (i*2+1) > self.length-1:   #该元素只有左节点时  
  20.             maxIndex = left(i)  
  21.         elif self.heapList[left(i)] > self.heapList[right(i)]:   #该元素同时有左右节点,且左节点的值大于右节点时  
  22.             maxIndex = left(i)  
  23.         else:    #该元素同时有左右节点,且左节点的值小于右节点时  
  24.             maxIndex = right(i)  
  25.         if self.heapList[i] < self.heapList[maxIndex]:   #当其子节点值大于其节点值时:  
  26.             self.heapList[i], self.heapList[maxIndex] = self.heapList[maxIndex], self.heapList[i]  
  27.             #交换其子节点的值和其值  
  28.             self.max_heapfy(maxIndex)  #并对其子节点进行最大堆化  
  29.   
  30.     def build_max_heap(self):      #构建最大堆  
  31.         self.length = len(self.heapList)    #计算堆的大小(包含第一个空元素)  
  32.         for i in range(self.length/20, -1):  #从包含子节点的节点开始依次向上遍历  
  33.             self.max_heapfy(i)  
  34.   
  35.     def insert(self, k):   #向堆内插入元素  
  36.         self.length += 1    #堆的规模加1  
  37.         self.heapList.append(float("-inf"))   #向堆内插入一个负无穷的数  
  38.         self.increase_key(self.length, k)   #增加元素  
  39.   
  40.     def maxinum(self):    #查询堆内最大元素,即为索引为1的元素值。  
  41.         return self.heapList[1]  
  42.   
  43.     def extract_max(self):    #弹出堆内最大元素。  
  44.         maxValue = self.heapList[1]    #取得最大元素值  
  45.         self.heapList[1] = self.heapList[self.length]   #将末尾元素移至堆头  
  46.         del self.heapList[self.length]  #删除末尾元素  
  47.         self.length -= 1  #将堆的规模减1  
  48.         self.max_heapfy(1)   #对堆顶元素最大堆化  
  49.         return maxValue  
  50.   
  51.     def increase_key(self, x, k):   #增加元素  
  52.         self.heapList[x] = k   #将新增的负无穷位置赋予插入值  
  53.         while x > 1 and self.heapList[parent(x)] < self.heapList[x]: #当元素索引大于1且其值大于其父节点值  
  54.             self.heapList[parent(x)], self.heapList[x] = self.heapList[x], self.heapList[parent(x)]  
  55.             #交换其值和其父节点的值  
  56.             x = parent(x)  #继续对其父节点进行判断  
  57.   
  58.     def show(self):  #展示堆  
  59.         print "the length of queue is"self.length - 1  
  60.         print "the heapList is"self.heapList[1:]  
  61.   
  62. def heapSort(unsortedList):  
  63.     heap = Heap(unsortedList)   #将乱序列表转换为堆  
  64.     heap.build_max_heap()       #将堆构建为最大堆  
  65.     print heap.heapList  
  66.     print "*************heap has been build up*********"  
  67.     for i in range(len(unsortedList), 1, -1):  
  68.         heap.heapList[i], heap.heapList[1] = heap.heapList[1], heap.heapList[i]  #将末尾节点与根节点进行交换,  
  69.         #交换完成后,i位置的节点为当前堆中最大的元素。即每次循环中得到的i索引的元素为已有序的列表。  
  70.         heap.length -= 1   #未排序的堆的规模减小1  
  71.         heap.max_heapfy(1)    #此时,根节点不满足最大堆的要求,需要对堆进行最大堆恢复  
  72.     return heap.heapList[1:]  
  73.   
  74. if __name__ == '__main__':  
  75.     list1 = [3,2,4,6,7,5,1,8,10,9]  
  76.     list2 = ["wang""zhe""tian""jin""da""xue"]  
  77.     ordered_list1 = heapSort(list1)  
  78.     ordered_list2 = heapSort(list2)  
  79.     print ordered_list1             #[2, 3, 4, 5, 6, 7]  
  80.     print ordered_list2             #['da', 'jin', 'tian', 'wang', 'xue', 'zhe'] 


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/220205/viewspace-2145573/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2011-08-03

  • 博文量
    65
  • 访问量
    82056