人よ、幸福に生きよ

1
def sequentialSearch(alist,item):
2
    pos = 0
3
    found = False
4

5
    while pos < len(alist) and not found:
6
        if alist[pos] == item:
7
            found = True
8
        else:
9
            pos = pos + 1
10
    return found

1
def orderedSequentialSearch(alist,item):
2
    pos = 0
3
    found = False
4
    stop = False
5

6
    while pos < len(alist) and not found and not stop:
7
        if alist[pos] == item:
8
            found = True
9
        else:
10
            if alist[pos] > item:
11
                stop = True
12
            else:
13
                pos = pos + 1
14
    return found

1
def binarySearch(alist,item):
2
    first = 0
3
    last = len(alist) - 1
4
    found = False
5

6
    while first <= last and not found:
7
        midpoint = (first + last)//2
8
        if alist[midpoint] == item:
9
            found = True
10
        else:
11
            if item < alist[midpoint]:
12
                last = midpoint - 1
13
            else:
14
                first = midpoint + 1
15
    return found

1
def binarySearch(alist,item):
2
    if len(alist) == 0:
3
        return False
4
    else:
5
        midpoint = len(alist)//2
6
        if alist[midpoint] == item:
7
            return True
8
        else:
9
            if item < alist[midpoint]:
10
                return binarySearch(alist[:midpoint],item)
11
            else:
12
                return binarySearch(alist[midpoint+1:],item)

1
def bubbleSort(alist):
2
    for passnum in range(len(alist)-1,0,-1):
3
        for i in range(passnum):
4
            if alist[i]>alist[i+1]:
5
                temp = alist[i]
6
                alist[i] = alist[i+1]
7
                alist[i+1] = temp

1
nums = [5,3,6,4,1,2,8,7]
2
for i in range(1,len(nums)):
3
    for j in range(i):
4
        if nums[i] < nums[j]:
5
            ins = nums[i]
6
            nums.pop(i)
7
            nums.insert(j,ins)
8
            break
9
print(nums)

1
def shellSort(alist):
2
    sublistcount = len(alist) // 2
3
    while sublistcount > 0:
4

5
        for startposition in range(sublistcount):
6
            gapInsertionSort(alist,startposition,sublistcount)
7

8
        print("After increments of size",sublistcount,"The list is",alist)
9

10
        sublistcount = sublistcount // 2
11

12
def gapInsertionSort(alist,start,gap):
13
    for i in range(start+gap,len(alist),gap):
14

15
        currentvalue = alist[i]
16
        position = i
17

18
        while position >= gap and alist[position-gap] > currentvalue:
19
            alist[position] = alist[position-gap]
20
            position = position - gap
21

22
        alist[position] = currentvalue

1
nums = [5,3,6,4,1,2,8,7]
2
res = []
3
while len(nums):
4
    minInd = 0
5
    for i in range(1,len(nums)):
6
        if nums[i] < nums[minInd]:
7
            minInd = i
8
    temp = nums[minInd]
9
    nums.pop(minInd)
10
    res.append(temp)
11
print(res)

1
def mergeSort(alist):
2
    print("Splitting",alist)
3
    if len(alist) > 1:  #基本结束条件
4
        mid = len(alist) // 2
5
        leftHalf = alist[:mid]
6
        rightHalf = alist[mid:]
7

8
        mergeSort(leftHalf) #递归调用自身
9
        mergeSort(rightHalf)
10

11
        i = j = k = 0
12
        while i < len(leftHalf) and j < len(rightHalf): #归并过程
13
            if leftHalf[i] < rightHalf[j]:
14
                alist[k] = leftHalf[i]
15
                i = i + 1
16
            else:
17
                alist[k] = rightHalf[j]
18
                j = j + 1
19
            k = k + 1
20

21
        while i < len(leftHalf): #归并左半部剩余项
22
            alist[k] = leftHalf[i]
23
            i = i + 1
24
            k = k + 1
25

26
        while j < len(rightHalf): #归并右半部剩余项
27
            alist[k] = rightHalf[j]
28
            j = j + 1
29
            k = k + 1
30

31
        print("Merging",alist)

1
def merge_sort(lst):
2
    #递归结束条件
3
    if len(lst) <= 1:
4
        return lst
5

6
    #递归调用自身
7
    middle = len(lst) // 2
8
    left = merge_sort(lst[:middle])
9
    right = merge_sort(lst[middle:])
10

11
    #合并左右半部，完成排序
12
    merged = []
13
    while left and right:
14
        if left[0] < right[0]:
15
            merged.append(left.pop(0))
16
        else:
17
            merged.append(right.pop(0))
18
    merged.extend(right if right else left)
19
    return merged

1
def partition(alist,first,last):
2
    # 选取“首元素”为基准值（pivot）。这种选法实现简单，但在近乎有序数据上可能退化较明显
3
    pivotvalue = alist[first]
4

5
    # leftmark 从左向右找“> pivot”的元素；rightmark 从右向左找“< pivot”的元素
6
    leftmark = first + 1
7
    rightmark = last
8

9
    done = False
10
    while not done:
11
        # 左指针跳过所有 <= pivot 的元素
12
        while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
13
            leftmark = leftmark + 1
14

15
        # 右指针跳过所有 >= pivot 的元素
16
        while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
17
            rightmark = rightmark - 1
18

19
        # 指针交错，说明分区扫描完成
20
        if rightmark < leftmark:
21
            done = True
22
        else:
23
            # 交换两侧“放错边”的元素，让小的去左边、大的去右边
24
            temp = alist[leftmark]
25
            alist[leftmark] = alist[rightmark]
26
            alist[rightmark] = temp
27

28
    # 把 pivot 放到最终位置：其左侧都 <= pivot，右侧都 >= pivot
29
    temp = alist[first]
30
    alist[first] = alist[rightmark]
31
    alist[rightmark] = temp
32

33
    return rightmark
34

35
def quickSortHelper(alist,first,last):
36
    # 递归终止条件：子区间长度为 0 或 1 时天然有序
37
    if first < last:
38
        splitpoint = partition(alist,first,last)
39
        # 分别对 pivot 左右两侧递归排序
40
        quickSortHelper(alist,first,splitpoint-1)
41
        quickSortHelper(alist,splitpoint+1,last)
42

43
def quickSort(alist):
44
    # 原地排序：直接在 alist 上操作，不额外返回新列表
45
    quickSortHelper(alist,0,len(alist)-1)
46

47
alist = [54,26,93,17,77,31,44,55,20]
48
quickSort(alist)
49
print(alist)