排序, since 2020-05-24

作者: Mc杰夫 | 来源:发表于2020-05-24 13:21 被阅读0次

2020-05-24
Insertion
复杂度 $O(n^2)$
part 1
part 2
某个未排序的indexed序列，从最后一个元素 $n_i$ 开始，与其前一个元素 $n_{i-1}$ 比较，如果 $n_i<n_{i-1}$ ，则将 $n_{i-1}$ 复制到位置 $i$ 。 $n_i$ 继续与 $n_{i-2}$ 比较，如果 $n_i<n_{i-2}$ ，则将 $n_{i-2}$ 复制到位置 $i-1$ 。重复这个过程直到 $n_i$ 不再小于 $n_{i-j}$ ，并将 $n_i$ 放在位置 $i-j+1$ 上。如果 $n_i<n_{i-j}$ ，则 $n_i$ 放在位置 $0$ 上。至此，完成了元素 $n_i$ 的排序。
有一个unsorted sequence A，A的前 $i$ 个元素组成子序列完成上面排序过程，从 $index=0$ 开始，则完成了A的insertion排序过程。

from copy import deepcopy as dc
def insertionSort2(n, arr):
    if not 0<= n <= 1000 or abs(max(arr)) > 10000 or abs(min(arr)) > 10000:
        return 'again'
    res = dc(arr)
    for i, ele in enumerate(res):
        if i == 0:
            continue
        narr = dc(res[:i+1])
        for ii in range(len(narr)-2,-1,-1):
            if narr[ii] > ele:
                narr[ii+1] = narr[ii]
                if ii == 0:
                    narr[ii] = ele
            else:
                narr[ii+1] = ele
                break
        res = narr+arr[i+1:] if i < len(arr)-1 else narr
        ress = [str(term) for term in res]
        print(' '.join(ress))

(2020.05.31 Sun)
Sorting with stack(s) 用栈排序 (面试题)
一个栈a保存了若干数字，1) 借用另一个栈b实现对栈a的降序排列，2) 不用其他数据结构，只用变量，实现对该栈数据的排序(JAVA版)。
思考: 对于问题1，可用recursion递归法实现。从a pop出数据k，并insert到b中，b中的顶元素如果大于k，或者b为空，则b.push(k)，否则设tmp = b.pop()，并对k和b的余下部分继续做insert操作。得到的b就是ascending sorted sequence。a.push(b.pop())的操作则实现了a中元素的descending sort。复杂度 $O(n^2)$ 。代码如下。

def insert(s, e):
    if s.is_empty() or s.top() >= e:
        s.push(e)
        return s
    tmp = s.pop()
    insert(s, e)
    s.push(tmp)
    return s
sa = stack()
sb = stack()
sa.push(1)
sa.push(8)
sa.push(2)
sa.push(5)
sa.push(0)
while not sa.is_empty():
    tmp = sa.pop()
    insert(sb, tmp)
while not sb.is_empty():
    sa.push(sb.pop())

问题2中，对栈a本身做insert操作，a pop出元素k，insert回到a'中，最好的情况是a'已经是ascending排好序的了，并且k比a'的top元素小，则直接push(k)就可以。可引入一个递归排序的函数。代码如下。

def sort_(s):
    if s.is_empty():
        return
    tmp = s.pop()
    s = sort_(s)
    s = insert(s, tmp)
    return s
sort_(sa)

Bubble sorting冒泡法排序
遍历序列a，其长度为n。相邻元素比较，如果前一个大于后一个，则交换两个位置。停止条件：遍历序列一次之后没有交换。复杂度 $O(n^2)$ 。下面代码实现该算法并输出swap次数。

    for j in range(len(a)):
        cntr1 = 0
        for i,e in enumerate(a[:-1]):
            if e>a[i+1]:
                a[i],a[i+1] = a[i+1],a[i]
                cntr1+=1
        cntr += cntr1
        if cntr1 == 0:
            break

(2020.06.04 Thur)
快速排序 Quick sort [2]
一种变形的冒泡排序。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
流程
快速排序算法通过多次比较和交换来实现排序，其排序流程如下：
(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

def quick_sort(data):
    # 来自百科，做了修改
    if len(data) >= 2:  # 递归入口及出口        
        mid = data[len(data)//2]  # 选取基准值，也可以选取第一个或最后一个元素        
        left, right = [], []      
        mid_arr = [mid] # 原代码中未考虑mid元素重复的情况
        # data.remove(mid)  # 从原始数组中移除基准值        
        for num in data:            
            if num > mid:                
                right.append(num)            
            elif num < mid:                
                left.append(num)        
            else:
                mid_arr.append(num)
            return quick_sort(left) + mid_arr + quick_sort(right)
            # return quick_sort(left) + [mid] + quick_sort(right)    
    else:        
        return data

性能分析：
从序列两头交替搜索，直到重合，所以时间复杂度是 $O(n)$ 。整个算法的复杂度与搜索的趟数有关。理想情况下是从中间分，故复杂度 $log_2 n$ 。
最坏情况是所选的pivot是最大或最小元素。复杂度 $O(n^2)$ 。
从空间性能上看，尽管快速排序只需要一个元素的辅助空间，但快速排序需要一个栈空间来实现递归。最好的情况下，即快速排序的每一趟排序都将元素序列均匀地分割成长度相近的两个子表，所需栈的最大深度为 $log2(n+1)$ ；但最坏的情况下，栈的最大深度为n。这样，快速排序的空间复杂度为 $O(log2n))$ 。