python算法总结

排序的相关概念

排序的稳定性

经过某种排序后，如果两个记录序号同等，且两者在原无序记录中的先后秩序依然保持不变，
则称所使用的排序方法是稳定的，反之是不稳定的。

内排序

排序过程中，待排序的所有记录全部放在内存中

外排序

排序过程中，使用到了外部存储。

影响内排序算法性能的三个因素

时间复杂度：即时间性能，高效率的排序算法应该是具有尽可能少的关键字比较次数和记录的移动次数

空间复杂度：主要是执行算法所需要的辅助空间，越少越好。

算法复杂性。主要是指代码的复杂性。

排序主要操作

插入排序
交换排序
选择排序
归并排序

1 冒泡排序 （交换排序）

冒泡排序（Bubble sort） 时间复杂度 O(n^2)

其核心思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序记录为止。

class SortList:
    def __init__(self, list=None):
        self.list = list


    def change(self, l, r):
        temp = self.list[l]
        self.list[l] = self.list[r]
        self.list[r] = temp

    def simple_buble(self):
        list = self.list
        length = len(self.list)
        for i in range(length):
            for j in range(i+1, length):
                if list[i] > list[j]:
                    self.change(i, j)

选择排序

简单选择排序（simple selection sort）:时间复杂度O(n^2)

其效率之处在于，每一轮中比较了很多次，但只交换一次。因此虽然它的时间复杂度也是O(n^2)，但比冒泡算法还是要好一点。

# encoding : utf-8



class SortList:
    def __init__(self, list=None):
        self.list = list


    def change(self, l, r):
        temp = self.list[l]
        self.list[l] = self.list[r]
        self.list[r] = temp

    def simple_select(self):
        list = self.list
        length = len(self.list)
        for i in range(length):
            min = i
            for j in range(i+1, length):
                if list[min] > list[j]:
                    min = j
            if i != min:
                self.change(i, min)

    def __str__(self):
        ret = ""
        for i in self.list:
            ret += " %s" % i
        return ret

if __name__ == '__main__':
    sort_list = SortList([4,1,7,3,8,5,9,2,6])
    sort_list.simple_select()
    print(sort_list)

快排

冒泡排序的升级版， 快速排序的 时间复杂度为O(nlog(n))

快速排序算法的核心思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小， 然后分别对这两部分继续进行排序，以达到整个记录集合的排序目的。