데이터 구조 - 정렬 알고리즘 소결

최근 에 카드 놀이 활동 에 참가 하여 데이터 구조 (입문 단계) 를 배우 고 학습 노트 (많은 매개 변수 책 에 있 는 코드, 뿌리 지 마 세 요) 를 기록 합 니 다.
(1) 거품 알고리즘

#     ：
def  bubbleSort(alist):
    for  i in range(len(alist)-1,0,-1):
        for j in range(i):
            if alist[j]>alist[j+1]:
                temp=alist[j]
                alist[j]=alist[j+1]
                alist[j+1]=temp

거품 정렬 은 최종 위치 가 알려 지기 전에 항목 을 교환 해 야 하기 때문에 가장 비효 율 적 인 정렬 방법 으로 여 겨 진다.이런 '낭비' 의 교환 조작 은 매우 비싸다.그러나 거품 정렬 이 목록 의 전체 정렬 되 지 않 은 부분 을 옮 겨 다 니 기 때문에 대부분의 정렬 알고리즘 이 할 수 없 는 일 을 할 수 있 습 니 다.특히 옮 겨 다 니 는 동안 교환 되 지 않 으 면 이 목록 이 정렬 되 어 있다 는 것 을 알 고 있 습 니 다.목록 이 정렬 되 어 있 는 것 을 발견 하면 거품 정렬 을 수정 하여 미리 멈 출 수 있 습 니 다.이것 은 효율 을 크게 높 일 것 이다.

def shortBubbleSort(alist):
    exchange=True
    passnum=len(alist)-1
    while passnum> 0 and exchange:
        exchange=False
        for i in range (passnum):
            if alist[i]>alist[i+1]:
                exchange=True
                temp=alist[i]
                alist[i]=alist[i+1]
                alist[i+1]=temp
        passnum=passnum-1

(2) 정렬 선택
 정렬 을 선택 하여 거품 정렬 을 개선 하 였 습 니 다. 목록 을 옮 겨 다 닐 때마다 한 번 만 교환 합 니 다.이 를 위해 하나의 선택 정렬 은 그 가 여러 번 겪 었 을 때 가장 큰 값 을 찾 고 옮 겨 다 니 기 를 마 친 후에 정확 한 위치 에 놓 습 니 다.거품 정렬 과 마찬가지 로 처음 옮 겨 다 닌 후 가장 큰 항목 은 정확 한 곳 에 있 습 니 다.두 번 째 후, 다음 가장 큰 자리.n - 1 차 정렬 n 개 항목 을 옮 겨 다 닙 니 다. 최종 항목 은 (n - 1) 차 로 옮 겨 다 녀 야 하기 때 문 입 니 다.

def  selectionSort(alist):
    for fillslot in range(len(alist)-1,0,-1):
        #    
        positionOfMax=0
        for location in range(1,fillslot+1):
            if alist[location]>alist[positionOfMax]:
                positionOfMax=location
        temp=alist[fillslot]
        alist[fillslot]=alist[positionOfMax]
        alist[positionOfMax]=temp

(3) 정렬 삽입
정렬 을 삽입 하 는 최대 비교 횟수 는 n - 1 개의 정수 의 합계 입 니 다.마찬가지 로 O (n ^ 2) 입 니 다.하지만 가장 좋 은 경우 통과 할 때마다 한 번 만 비교 해 야 한다.

def insertSort(alist):
    for index in range(1,len(alist)):
        currentvalue=alist[index]
        posistion=index
        while posistion>0 and alist[posistion-1]>currentvalue:
            alist[posistion]=alist[posistion-1]
            posistion=posistion-1
        alist[posistion]=currentvalue

(4) 힐 정렬
힐 정렬 (때로는 '체감 증가 정렬' 이 라 고도 함) 은 원본 목록 을 여러 개의 작은 하위 목록 으로 분해 하여 삽입 정렬 을 개선 하고 각 하위 목록 은 삽입 정렬 을 사용 하여 정렬 합 니 다.이 하위 목록 을 선택 하 는 방식 은 힐 정렬 의 관건 이다.목록 을 연속 항목 으로 나 누 는 하위 목록 이 아 닙 니 다. 힐 정렬 은 증분 i (때로는 gap) 를 사용 하여 i 항목 의 모든 항목 을 선택 하여 하위 목록 을 만 듭 니 다.

def shellSort(alist):
    sublistcount=len(alist)//2
    while sublistcount>0:
        for startposition in range(sublistcount):
            gapInsertionSort(alist,startposition,sublistcount)
        print("After increments of size",sublistcount,"The list is",alist)
        sublistcount=sublistcount//2
def gapInsertionSort(alist,start,gap):
    for i in range(start+gap,len(alist),gap):
        currentvalue=alist[i]
        position=i
        while position>=gap and alist[position-gap]>currentvalue:
            alist[position]=alist[position-gap]
            position=position-gap
        alist[position]=currentvalue

(5) 정렬
병합 정렬 은 재 귀 알고리즘 으로 목록 을 계속 반 으로 나 누 어 줍 니 다.목록 이 비어 있 거나 항목 이 있 으 면 정의 (기본 상황) 에 따라 정렬 합 니 다.목록 에 여러 항목 이 있다 면, 우 리 는 목록 을 분할 하고, 두 부분의 병합 정렬 을 재 귀적 으로 호출 합 니 다.이 두 개의 정렬 이 완료 되면 합병 이라는 기본 동작 을 수행 합 니 다.병합 은 두 개의 작은 정렬 목록 을 가 져 와 하나의 정렬 된 새 목록 으로 조합 하 는 과정 입 니 다.

def mergeSort(alist):
    print("Splitting ",alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]
        mergeSort(lefthalf)
        mergeSort(righthalf)
        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1
        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1
        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",alist)

(6) 빠 른 정렬

def quickSort(alist):
    quickSortHelper(alist,0,len(alist)-1)
def quickSortHelper(alist,first,last):
    if first= pivotvalue and rightmark >= leftmark:
            rightmark = rightmark -1
        if rightmark < leftmark:
            done = True
        else:
            temp = alist[leftmark]
            alist[leftmark] = alist[rightmark]
            alist[rightmark] = temp
    temp = alist[first]
    alist[first] = alist[rightmark]
    alist[rightmark] = temp
    return rightmark