정렬 (408)

408 중 기초 전공 과목 의 정렬 알고리즘 을 대상 으로 학습 합 니 다.학습 하 는 과정 에서 현재 학습 의 목표 와 과정 에서 추상 적 인 요 소 는 어떤 것들 이 있 습 니까?구체 적 인 원 소 는 어떤 것들 이 있 습 니까?추상 적 인 부분 은 반드시 철저하게 흡수 해 야 하고 구체 적 인 부분 은 경험 으로 삼 아야 하 며 쌓 인 경험 은 미래 에 분류 하여 정리 한 후에 최종 적 으로 추상 화 될 것 이다.정렬 알고리즘 은 내부 정렬 과 외부 정렬 으로 나 뉜 다.내부 정렬 은 데이터 양 이 상대 적 으로 적다.데이터 가 모두 메모리 에 있 는 정렬 알고리즘.이런 알고리즘 은 시간의 복잡성 이 낮 고 공간의 복잡성 이 높 을 수 있 도록 요구한다.외부 정렬 은 하 드 디스크 에 저 장 된 데 이 터 를 대상 으로 합 니 다. 이러한 데 이 터 는 양 이 많아 서 메모리 가 한 번 에 놓 일 수 없습니다.시간의 복잡성 에 대한 요구 가 높 지 않다.공간의 복잡성 에 대한 요구 가 높다.
원 시퀀스 Ri = Rj, ii 는 여전히 < Rj.정렬 알고리즘 이 안정 적 이 라 고 합 니 다. 그렇지 않 으 면 불안정 이 라 고 합 니 다.
내부 정렬
크게 다섯 가지 로 나 뉘 는데 삽입 정렬, 교환 정렬, 선택 정렬, 병합 정렬 과 기수 정렬 은 내부 알고리즘 작업량 에서 세 가지 로 나 눌 수 있다.

간단 한 정렬 알고리즘 으로 그 시간 복잡 도 는 O (n 2 n ^ 2 n2)

이다.

선진 적 인 정렬 알고리즘 으로 그 시간 복잡 도 는 O (nlogn)

이다.

기수 정렬, 그 시간 복잡 도 는 O (d * n)

일반적으로 정렬 과정 에서 두 가지 기본 적 인 조작 을 해 야 한다.

두 키워드 의 크기 비교

기록 이 한 위치 에서 다른 위치 로 이동 하 는 것 을 말한다

이전 작업 은 대부분의 정렬 알고리즘 에 필요 한 것 이 고, 다음 작업 은 기록 의 저장 방식 을 바 꾸 어 피 할 수 있다.
배열 이 있 는 기록 서열 은 다음 과 같은 세 가지 저장 방식 이 있 을 수 있다.

주소 가 연 속 된 저장 장치 에서 선형 표 와 유사 한 순서 저장 구조.

이런 저장 방식 에서 기록 간 의 순서 관 계 는 저장 위치 에 의 해 결정 되 고 정렬 을 실현 하려 면 반드시 이동 기록 을 빌려 야 한다.

정렬 대기 기록 은 정적 링크 에 저 장 됩 니 다.기록 간 의 순서 관 계 는 지침 에 의 해 표시 된다.

정렬 을 실현 하려 면 이동 기록 이 필요 없고 지침 만 수정 하면 됩 니 다.

정렬 대기 기록 자체 가 한 그룹의 주소 연속 저장 장치 에 저장 되 는 동시에 각 기록 저장 위 치 를 표시 하 는 주소 벡터 를 설정 합 니 다.

정렬 과정 에서 기록 자 체 를 이동 하지 않 고 주소 벡터 를 이동 하 는 '주소' 입 니 다. 정렬 이 끝 난 후에 주소 벡터 의 값 에 따라 기록 의 저장 위 치 를 조정 합 니 다.
두 번 째 저장 방식 에서 이 루어 진 정렬 은 표 정렬 이 라 고 합 니 다.세 번 째 저장 방식 에서 이 루어 진 정렬 을 주소 정렬 이 라 고 합 니 다.
삽입 정렬
정렬 (Straight Insertion Sort) 을 직접 삽입 하 는 것 은 가장 간단 한 정렬 방법 입 니 다. 기본 적 인 작업 은 정렬 된 순서 표 에 기록 을 삽입 하여 새로운 기록 1 의 질서 표를 얻 는 것 입 니 다.

void InsertSort(SqList &L){
	//     L       
	for(i = 2; i<= L.length; ++i)
		if(LT(L.r[i].key, L.r[i-1].key)){ 	// “
			L.r[0] = L.r[i];				//      
			L.r[i] = L.r[i-1];
			for(j = i-2; LT(L.r[0].key, L.r[j].key); ++j)
				L.r[j+1] = L.r[j];			//     
			L.r[j+1] = L.r[0];				//        
		}
} // InsertSort

반절 기 삽입 정렬
힐 정렬

void ShellSort(ElemType A[], int n){
	// A[0]     ，    ， j < 0       
	for(dk = n/2, dk>=1;dk=dk/2) 	//     
		for(i = dk+1; i<n;++1)	
}

빠 른 정렬 (교환)
교환 으로 정렬 하 는 방법.가장 쉬 운 것 은 거품 정렬 이다.
빠 른 정렬 (Quick Sort) 은 기포 정렬 을 개선 하 는 것 입 니 다. 기본 적 인 사상 은 한 번 의 정렬 을 통 해 정렬 대기 기록 을 독립 된 두 부분 으로 나 누 는 것 입 니 다. 그 중에서 일부 기록 의 키 워드 는 다른 부분 에 기 록 된 키워드 보다 작 으 면 각각 두 부분 에 대한 기록 을 계속 정렬 하여 전체 서열 의 질 서 를 달성 할 수 있 습 니 다.
빠 른 정렬 사상 은 분 치 법 을 바탕 으로 하 는 것 이다. 정렬 대기 표 L [1... n] 에서 하나의 요소 pivot 를 중심 축 (또는 기준, 보통 첫 번 째 요소) 으로 하고 한 번 의 정렬 을 통 해 정렬 대기 표를 독립 된 두 부분 L [1. k - 1] 과 L [k + 1... n] 으로 나 누 어 L [1. k - 1] 에 있 는 요 소 를 pivot 보다 작 게 하고 L [k + 1.. n] 에서 모든 요 소 는 pivot 와 같다.pivot 는 최종 위치 L [K] 에 놓 여 있 습 니 다. 이 과정 은 빠 른 정렬 (또는 한 번 구분) 입 니 다.그 다음 에 두 개의 서브 시트 에 대해 상기 과정 을 반복 하고 모든 부분 에 하나의 요소 만 있 거나 비어 있 을 때 까지 모든 요 소 를 최종 위치 에 두 었 다.

void QuickSort(ElemType A[ ], int low, int high){
	if(low < high){				//        
	// partition()      ，  [LOW..HIGH]              
		int pivotpos = partition(A, low, high);	//   
		QuickSort(A, low, pivotpos-1);		//         。
		QuickSort(A, pivotpos, high);
	}
}

int Partition(ElemType A[], int low, int high){	//     
	ElemType pivot = A[low];		//               ，      
	while(low < high){ 				//       
		while(low<high && A[high] >= pivot)	--high;	
		A[low] = A[high];			//              
		while(low<high && A[low] <= pivot) ++low;
		A[high] = A[low];			//              
	}
	A[low] = pivot;					//           
	return low;						//            
}

정렬 선택
최대 (최소) 를 앞 이나 뒤에 놓 으 세 요.
정렬
전송 주소:https://www.cnblogs.com/lanhaicode/p/11284230.html

//            1，      
void MergeSort_UptoDowm(int* num, int start, int end){
    int mid = start +(end - start)/2;

    if(start >= end)        return ;
    
    MergeSort_UptoDowm(num, start, mid);    //   
    MergeSort_UptoDowm(num, mid+1, end);    //   

    merge(num, start, mid, end);            //   
}

void Merge(int *num, int start, int mid, int end){
    int *temp = (int *)malloc(sizof(int)*(end - start+1));
    //                     
    int i = start;
    int j = mid+i;
    int k = 0;

    while(i <=mid && j<=end){		//          
        if(num[i] <=num[j]){
            temp[k++] = num[i++];
        }
        else{
            temp[k++] = num[j++]; 
        }   
    }
    while(i <= mid){	//           
        temp[k++] = num[i++];
    }
    while(j < =end){	
        temp[k++] = num[j++];
    }

    //             ，       
    for(i = 0;i < k; i++)
    {
        num[start+i] = temp[i];
    }
    
    free(temp);	
}

기수 정렬
각종 내부 정렬 방법의 비교 토론
빨강
외부 정렬

정렬 (408)

좋은 웹페이지 즐겨찾기