Index:

1) Insertion sort
2) Quick Sort
3) Merge Sort
4) Heap Sort
5) Radix Sort

Sorting:

ソートされていないデータを比較する場合、Θ(n)比較演算を実行する.

データの位置合わせを比較すると、Θ(lg(n))比較演算を実行します.

1. Insertion Sort:

ソースリンク

def insertSort(arr):
    for i in range(1,len(arr)):
        j = i-1
        while(j>=0 and arr[i]<arr[j]):
            j-=1
        
        arr.insert((j+1),arr[i])
        del arr[i+1]
    
    return arr


def main():
    arr = [2,1,5,4,3,8,10]
    arr = insertSort(arr)
    print(arr)

if __name__ == "__main__":
    main()

2. Quick sort

クイックソートは不安定なソートに属し、他の要素との比較のみでソートを実行する比較ソートに属します.

分割征服アルゴリズムの1つであり,lg(n)を平均的に実行する時間的複雑さである.

分割征服とは何ですか.
大所に着目する

切り裂いて、軸をつかんで、左から右へ折り返して->切り裂いて、軸をつかんで、左から右へ繰り返して、それから切り裂いて、1格は終わりました.

def partition(arr,start,end):
    pivot = arr[start]
    left = start+1
    right = end
    while True:
        while left <= end and arr[left] < pivot:
            if left == end:
                break
            left += 1
        
        while right >= 0 and arr[right] > pivot:
            if right == 0:
                break
            right -= 1

        if left >= right:
            break
        else:
            arr[left], arr[right] = arr[right] , arr[left]

    arr[start],arr[right] = arr[right] , arr[start]
    return right

def quickSort(arr,start,end):
    if start < end:
        pivot = partition(arr,start,end)
        quickSort(arr,start,pivot-1)
        quickSort(arr,pivot+1,end)
    
    return arr

a = list(map(int,input().split()))
print(quickSort(a,0,len(a)-1))
        

output:

[20, 74, 35, 84, 20, 50, 83, 15]
[15, 20, 20, 35, 50, 74, 83, 84]

3. MergeSort:

コメントリンク

def merge(left,right):
    result = []
    while (len(left) > 0 or len(right)> 0) :
        if  (len(left) > 0 and len(right) > 0) :
            if  left[0] <= right[0]:
                result.append(left[0])
                left = left[1:]
            else :
                result.append(right[0])
                right = right[1:]
        elif len(left) > 0 :
            result.append(left[0])
            left = left[1:]
        elif len(right) > 0 :
            result.append(right[0])
            right = right[1:] 

    return result

def merge_sort(list):
    if  len(list) <= 1:
        return list
    
    mid = len(list) // 2
    leftList = list[:mid]
    rightList = list[mid:]
    leftList = merge_sort(leftList)
    rightList = merge_sort(rightList)
    return merge(leftList,rightList)




list = [5,3,2,1,6,9,8,7]
list = merge_sort(list)
print(list)

output:

[1, 2, 3, 5, 6, 7, 8, 9]

4. HeapSort

注意: