常见排序算法学习总结

作者: 投篮手型差 | 来源:发表于2018-11-26 17:18 被阅读0次

算法学习(1)-排序算法
数据结构与算法
7大经典的排序算法总结实现
常见排序算法学习总结
LeetCode大全
常见排序算法总结 -- java实现
算法总结--常见排序算法
希尔排序
排序算法
iOS算法总结-堆排序

我也不知道算法能干什么，但是好像很厉害的样子。非计算机专业小白，从基础的算法开始看起，征途是星辰大海……，学习了几种常见的算法，会持续更新，从简单的开始介绍吧，每个算法我也没有照抄书上或者网上的代码，而是自己写一遍，虽然不知道能带给我什么，以此记录我的学习路程。

排序

稳定性：Ai=Aj,排序前Ai在Aj前，排序后Ai仍在Aj前，称为稳定算法。

即保证前后两个相等的数的相对顺序不变。

内排序：记录全在内存中
外排序：过程中使用到了外部存储
内排序性能影响因素：

时间复杂性：比较次数和移动次数。
空间复杂性：执行算法的辅助空间
算法复杂性：代码复杂程度

冒泡排序(Bubble sort)

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

冒泡排序.gif

简单排序：bubble_sort_simple
冒泡排序：bubble_sort
改进的冒泡排序：bubble_sort_advance

以a = [5,4,3,2,1]为例

round1 = [4,3,2,1,5] -5

round2= [3,2,1,4,5] -4

round3= [2,1,3,4,5] -3

round4 = [1,2,3,4,5] -2

round5不需要排序

算法的基本方法：
i和i+1项比较，i+1和i+2比较，后项<前项，交换位置,一共有n-1对，比较n-1次。将比完的大数置于队尾；

重复上述操作，共n-2对，比较n-2次。
每一轮排序都使得列表内最大的数被置于队尾，每次比较都列表长度都减1。

用python代码实现简单的一次排序方法：

a = [5,4,3,2,1] 
#第一次排序
length = len(a)
for i in range(0,length-1):
    if a[i] > a[i+1]:
        a[i],a[i+1] = a[i+1],a[I]

>>>a
[4, 3, 2, 1, 5]

第二次排序：

#第二次排序，列表长度-1
length = len(a)-1
for i in range(0,length-1):
    if a[i] > a[i+1]:
        a[i],a[i+1] = a[i+1],a[I]

>>>a
[3, 2, 1, 4, 5]

可以发现规律，每一轮排序，列表长度都-1，改变的只有列表长度length和length-1。

而需要排序的轮数是列表长度-1，所以冒泡排序可以这样表示：

def BubbleSort(lists):
    length = len(lists)
    #外循环是冒泡的轮数，每一轮结果都能将序列中最大值置于队尾。
    for t in range(0,length-1):
        #内循环是一轮中前后项比较的次数，随外循环次数递减。
        for i in range(0,length-t-1):
            if lists[i] > lists[i+1]:
                lists[i],lists[i+1] = lists[i+1],lists[I]
        print("第"+str(t+1)+"轮冒泡排序:"+repr(lists))
    return lists

>>>a = [5,4,3,2,1]
>>>BubbleSort(a)
第1轮冒泡排序:[4, 3, 2, 1, 5]
第2轮冒泡排序:[3, 2, 1, 4, 5]
第3轮冒泡排序:[2, 1, 3, 4, 5]
第4轮冒泡排序:[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]

选择排序(select sort)

选择排序是每次从序列中选择最大值或者最小值，置于序列第一个位置。(~~个人觉得下面代码写的有问题，并非严格意义上的选择排序，因为引入了另一个list空间~~)，书上也是将最小值加入一个新列表。

选择排序.gif

#example
#先写一个查找最小元素的函数
def findSmallest(arr): 
    #分别用于存放最小值和最小值索引
    smallest = arr[0] 
    smallest_index = 0
    for i in range(1, len(arr)):
        if arr[i] < smallest: 
            smallest = arr[i] 
            smallest_index = I
    return smallest_index

#选择排序函数
def selectionSort(arr): 
    newArr = []
    for i in range(len(arr)):
            #找到最小元素，加入新的数组
            smallest = findSmallest(arr) 
            newArr.append(arr.pop(smallest))
    return newArr

对比两种代码，觉得书上的例子思路更清晰，值得学习。

def select_sort(a):
    print("原序列:\n"+repr(a))
    b = []
    i = 0
    length = len(a)
    n = length
    while (i < length):
        min_value = min(a)
        b.append(min_value)
        i +=1
        n -=1
        print('round:'+str(i-1)+'-'+repr(a))
        if n >0:
            a.remove(min_value)    
    return print("排序后:\n"+repr(b))
>>>a = [1, 7, 4, 9, 5, 0, 3, 6]
原序列:
[1, 7, 4, 9, 5, 0, 3, 6]
round:0-[1, 7, 4, 9, 5, 0, 3, 6]
round:1-[1, 7, 4, 9, 5, 3, 6]
round:2-[7, 4, 9, 5, 3, 6]
round:3-[7, 4, 9, 5, 6]
round:4-[7, 9, 5, 6]
round:5-[7, 9, 6]
round:6-[7, 9]
round:7-[9]
排序后:
[0, 1, 3, 4, 5, 6, 7, 9]

我又尝试了不调用python自带的函数，仅通过交换位置可以得到的一种选择排序的方法，更符合定义，而且不会另外引出空间:

算法思路是：通过将第一个元素定义为最小值，分别和后面的值进行两两比较，将最小的值置换到第一个位置，来实现。每轮过后集合长度都会-1，而每轮元素放置到位置也是由轮数决定的，比如第一轮最小值位于List[0],第二轮则位于List[1],轮数是集合长度的n-1，每轮比较次数是由剩下元素个数决定的。有多少个元素就和List[i]比较多少次。

def SelectSort(arr):
    Round = len(arr)
    #排序轮数
    for i in range(Round-1):
        #比较次数
        for j in range(i+1,Round):
            if arr[j]<arr[I]:
                arr[i],arr[j] = arr[j],arr[i]
        print('round'+str(i+1)+repr(arr))
    return arr

>>>SelectSort([5,4,3,2,1])
round1[1, 5, 4, 3, 2]
round2[1, 2, 5, 4, 3]
round3[1, 2, 3, 5, 4]
round4[1, 2, 3, 4, 5]

补充

二分法

从一个序列的中间开始查找，每次比较需要查找的目标数字和序列中间数字的大小，从而缩小序列范围，确定目标数字的位置。

def binary_search(list,item):
    low = 0
    high = len(list)-1
    while low <=high:
        #此处存在问题，会导致每次只猜序列的最大索引，并非二分法
        mid = (low + high)
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid -1
        else:
            low = mid +1
    return None

算法图解中的例子，mid = (low+high)由于上下边界的index和始终相等，导致每次猜的数字都是序列的最大值，这段代码是有问题的；应该将其改为mid = (low+high)//2

#二分查找,list-序列，item-元素
def binary_search(lists,item):
    #low和high都是index
    low = 0
    high = len(lists)-1
    while low <=high:
        mid = (low + high)//2
        print('mid index is:'+str(mid))
        guess = lists[mid]
        print('round:'+str(count)+' '+'guess number:'+str(guess))
        if guess == item:
            return mid
        if guess > item:
            high = mid -1
            print('hight index :'+str(high)+'|'+'list value:'+str(lists[high]))
        else:
            low = mid +1
    return None

>>>my_list = random.sample(range(0,100),20)
>>>my_list.sort()
[3, 9, 12, 21, 25, 26, 34, 35, 44, 46, 49, 56, 65, 75, 79, 80, 85, 87, 90, 97]
>>>binary_search(my_list,97)
mid index is:9
round:1 guess number:46
mid index is:14
round:2 guess number:79
mid index is:17
round:3 guess number:87
mid index is:18
round:4 guess number:90
mid index is:19
round:5 guess number:97

以下是按自己的理解写的算法，虽然比书里复杂了一点，但毕竟初学者，更容易理解。100个程序员有100种编程的方法。

a = [3, 9, 12, 21, 25, 26, 34, 35, 44, 46, 49, 56, 65, 75, 79, 80, 85, 87, 90, 97]
def guess_number(List,target):
    low = 0
    high = len(List)-1
    #这一步判断目标值是否在序列中，加大了代码运行时间，但是去掉这个判断会导致当目标值不在其中时也会运行代码。
    if target in a:
        while low<=high:
            mid = (low+high)//2
            guess = List[mid]
            if guess > target:
                high = mid
                print('high index:'+str(high)+'|'+'guess:'+str(List[high]))
            if guess < target:
                low = mid +1
                print('low index:'+str(low)+'|'+'guess:'+str(List[low]))
            elif guess == target:
                low = mid
                print('return target index:'+str(mid)+'|'+'guess:'+str(List[mid]))
                return mid
    else:
        print('this number is out of range!')

>>>my_list
[3, 9, 12, 21, 25, 26, 34, 35, 44, 46, 49, 56, 65, 75, 79, 80, 85, 87, 90, 97]
>>>guess_number(my_list,97)
low index:10|guess:49
low index:15|guess:80
low index:18|guess:90
low index:19|guess:97
return target index:19|guess:97

同书上的二分查找算法比较可以发现，自己写的算法和例子区别在于算法的查找步骤，例子是每次比较guess和item的大小，从而每次迭代guess的index作为边界；而自己写的二分查找则是每次取序列的中值来比较，从而用中值的index作为上下边界，迭代步长不一定是1。
从运行结果也可以看出区别:

example:迭代5轮，每次index差值为1
自己的代码：每次index为中值的索引，只需要迭代4轮。

此外，自己写的二分查找如果不用判断，则无法反映在列表之外的元素，会产生报错或者死循环，而用了条件判断则代码显得不够简洁而且增加了运行时间和复杂度，仍需要改进。

介于《算法图解》这本书的错误百出，有些时候真的看书需要更仔细，对于算法的理解也不能仅仅停留在理论层面上，自己敲一遍代码来实现远比看别人的代码和记住别人的代码的成就感更大！

其他算法，下次再补充。
update 18.11.27

快速排序

快速排序(Quicksort)运用了D&C思想，即分而治之。

原理：

1.空列表和一个元素的列表根本不需要排序
2.定一个基准值，将列表分成两部分子集，一个所有值都小于基准，另一个所有值都大于基准
3.分别对前后子集进行快速排序(递归条件)
4.将排序结果拼接：quicksort(less)+[pivot]+quicksort(greater)

def quicksort(arr):
    #基线条件，[]和一个元素的列表无需排序
    if len(arr)<2:
        return arr
    else:
        #给一个基准值，用于划分子集
        pivot = arr[0]
        less = [i for i in arr[1:] if i < pivot]
        greater = [i for i in arr[1:] if i>pivot]
        return quicksort(less)+[pivot]+quicksort(greater)

学习了快速排序以及D&C的思想，觉得运用递归实在是太优雅了。