정렬 2 분 거품 찾기 정렬 선택 정렬 삽입 정렬 힐 정렬 빠 른 정렬

이분 찾기
질서 있 는 집합 에 기반 한 검색 이 분명 합 니 다.

def find(alist,item):
    find = False
    first = 0
    mid_index = 0
    last = len(alist)-1
    
    while first <= last:
        mid_index = (last + first)//2
        if alist[mid_index] < item:
            #           ，     
            first = mid_index + 1
        elif alist[mid_index] > item:
            last = mid_index - 1
        else:
            find = True
            break
    return find
        

alist = [1,3,4,5,7,9,10]
print(find(alist,6))

거품 정렬
사상: 서열 중의 두 개 를 비교 하고 순서대로 위 치 를 교환 하 며 순환 하여 질서 있 는 서열 을 얻 을 수 있다.

def sort(alist):
    for j in range(len(alist)-1):
        for i in range(len(alist)-j-1):
            if alist[i] > alist[i+1]:
                alist[i],alist[i+1] = alist[i+1],alist[i]  
    return alist

alist = [3,6,5,8,4]
print(sort(alist))

정렬 선택
사상: 먼저 하나의 최대 치 요소 의 아래 표 시 를 0 으로 가정 하고 이 요 소 를 다른 요소 와 비교 하 며 작 으 면 아래 표 시 를 대응 하 는 요소 의 아래 표 로 바 꿀 수 있다. 마지막 으로 최대 요소 의 진실 한 아래 표 시 를 얻어 마지막 요소 와 교환 할 수 있다. 두 번 째 는 상기 순환 을 계속 하여 두 번 째 요소 의 아래 표 시 를 얻어 마지막 두 번 째 요소 와 교환 할 수 있다.질서 있 는 서열 이 나 올 때 까지 n 회 순환

def sort(alist):
    for j in range(0,len(alist)-1):
        max_index = 0  #       
        for i in range(1,len(alist)-j):
            if alist[max_index] < alist[i]:
                max_index = i
        alist[len(alist)-1-j],alist[max_index] = alist[max_index],alist[len(alist)-j-1]
    return alist

alist = [3,6,5,8,4]
print(sort(alist))

삽입 정렬
사상: 하나의 서열 을 두 개의 부분 집합 으로 나 누 었 다. (나 누 는 것 이 아니 라 두 개의 부분 집합 으로 만 보 았 다. 왼쪽 은 질서 있 는 부분 집합 이 고 오른쪽 은 무질서 한 부분 집합 이다) 먼저 원래 서열 의 첫 번 째 수 를 질서 있 는 부분 집합 으로 하고 뒤의 요 소 는 무질서 한 부분 집합 으로 하 며 무질서 한 부분 에서 하나의 요 소 를 집중 적 으로 꺼 내 질서 있 는 부분 집합 의 마지막 요소 와 비교 했다.크 면 질서 있 는 부분 집합 마지막 요소 의 오른쪽 에 놓 고 작 으 면 마지막 엄숙 한 교환 위치 와 비교 한 다음 에 앞의 요소 와 비교 하여 성공 적 으로 삽입 할 때 까지 순환 한 다음 에 어 지 러 운 부분 집중 요 소 를 상기 절 차 를 점차적으로 순환 시 켜 질서 있 는 목록 을 삽입 하고 len (alist) - 1 회 순환 하면 된다.

def sort(alist):
#           ，       
    for i in range(1,len(alist)):
        while i > 0:
            # alist[i]            
            # alist[i-1]            
            if alist[i] < alist[i-1]:
                #                         
                alist[i],alist[i-1] = alist[i-1],alist[i]
                i -= 1
            else:
                break
    return alist


alist = [3,4,8,6,2]
print(sort(alist))

힐 정렬
gap: 증분 의 값 을 마지막 으로 나 눈 그룹 수
삽입 정렬 은 증 량 이 1 인 힐 정렬 입 니 다.
사상: 먼저 gap (gap = len (alist) / / 2) 를 얻어 야 한다. 모두 주관적 으로 gap 그룹 으로 나 누 어 각 그룹 에 대해 순 서 를 삽입 한 다음 에 gap (gap = gap / / 2) 를 얻어 그룹 을 나 누 어 순 서 를 삽입 할 수 있다. gap = 1 시 까지 마지막 으로 전체 그룹 에 순 서 를 삽입 하면 질서 있 는 순 서 를 얻 을 수 있다.

def sort(alist):
    gap = len(alist)//2
#           ，       
    while gap >= 1:
        for i in range(gap,len(alist)):
            while i > 0:
                # alist[i]            
                # alist[i-1]            
                if alist[i] < alist[i-gap]:
                    #                         
                    alist[i],alist[i-gap] = alist[i-gap],alist[i]
                    i -= gap
                else:
                    break
        gap = gap // 2
    return alist


alist = [3,4,8,6,2]
print(sort(alist))

빠 른 정렬
기수 지정 (난서 의 첫 번 째 데이터 값)
기수 보다 작은 데 이 터 를 기수 왼쪽 에 놓 고 기수 보다 큰 데 이 터 를 기수 오른쪽 에 놓 습 니 다.
사상: 목록 의 첫 번 째 요 소 를 기준 숫자 로 설정 하고 mid 변수 에 값 을 부여 한 다음 에 전체 목록 에서 기준 보다 작은 것 을 기준 왼쪽 에 놓 고 기준 보다 큰 것 을 기준 오른쪽 에 놓 은 다음 에 기준 숫자 좌우 양쪽 의 서열 을 이 방법 에 따라 배출 합 니 다.
두 개의 지침 을 정의 합 니 다. low 는 가장 왼쪽 을 가리 키 고 high 는 가장 오른쪽 을 가리 키 며 가장 오른쪽 지침 을 왼쪽으로 이동 합 니 다. 법칙 은 지침 이 가리 키 는 수치 가 기준 보다 작 으 면 지침 위치의 숫자 를 기준 디지털 의 원시 위치 로 이동 합 니 다. 그렇지 않 으 면 지침 을 계속 이동 합 니 다. 만약 에 가장 오른쪽 지침 이 가리 키 는 수치 가 기준 위치 로 이동 하면맨 왼쪽 포인 터 를 이동 하여 오른쪽으로 이동 합 니 다. 이 포인 터 가 가리 키 는 수치 가 기준 수치 보다 크 면 이 수 치 를 맨 오른쪽 포인 터 가 가리 키 는 위치 로 이동 한 다음 이동 을 중단 합 니 다.
좌우 사 이 드 포인터 가 중복 되면 기준 을 포인터 가 중복 되 는 위치 에 넣 으 면 기준 왼쪽 은 기준 보다 작은 수 이 고 오른쪽 은 기준 보다 큰 수 이다.

def sort(alist,start,end):
    low = start
    high = end
    
    if low > high:
        return
    
    #       
    mid = alist[start]
    while low < high:
        #   high
        while low < high:
            if alist[high] > mid:
                high -= 1
            else:
                alist[low] = alist[high]
                break
        
        #   low
        while low < high:
            if alist[low] < mid:
                low += 1
            else:
                alist[high] = alist[low]
                break
        
        if low == high:
            alist[low] = mid
            break
        
    sort(alist,start,high - 1)  
    sort(alist,low+1,end)
        
    return alist
        
alist = [6,1,2,7,9,3,4,5,10,8]
print(sort(alist,0,len(alist)-1))