C++의 정렬 알고리즘 을 자세히 정리 합 니 다.
나 는 억지로 외 우 는 것 을 좋아 하지 않 는 다.나 는 경 위 를 파악 하고 이해 적 으로 기억 하 는 편 이다.예 를 들 어 아래 의 이 시간 복잡 도 그림 을 보면 우 리 는 이 그림 을 중심 으로 분석 할 것 이다.
위의 이 그림 은 PPT 에서 왔 다.이 는 데이터 구조 에서 흔히 볼 수 있 는 정렬 알고리즘 을 요약 하여 다음 과 같이 요약 한다.
안정 과 불안정 구분:빠 르 고 힐,더미,선택 이 불안정 하 며 다른 정렬 알고리즘 이 모두 안정 적 입 니 다.
평균 시간 복잡 도:거품,선택,삽입 은 O(n2),기타 모두 O(n*log2n)
최 악의 시간 복잡 도:거품,선택,삽입,빠 른 줄 은 O(n2),기타 O(n*log2n)
평균 과 최 악의 시간 복잡 도:O(n2)와 O(n*log2n)두 가지 만 있 습 니 다.거품,선택,삽입 은 O(n2)이 고 최 악의 경우 빠 른 줄 을 추가 합 니 다.다른 것 은 모두 O(nlog2n)입 니 다.
1.정렬 을 직접 삽입 합 니 다(정렬 삽입).
1.알고리즘 의 위조 코드(이렇게 하면 이해 하기 쉽다):
INSERTION-SORT (A, n) A[1 . . n]
for j ←2 to n
do key ← A[ j]
i ← j C 1
while i > 0 and A[i] > key
do A[i+1] ← A[i]
i ← i C 1
A[i+1] = key
3.알고리즘 시간 복잡 도.
가장 좋 은 상황 에서:순서 가 질서정연 하 다(어 릴 때 부터).이렇게 하면 n 번 만 비교 하고 이동 할 필요 가 없다.따라서 시간 복잡 도 는 O(n)이다.
최 악의 경우:역순 이 질서 가 있다.그러면 모든 요 소 는 n 번 을 비교 해 야 하고 모두 n 개의 요소 가 있 기 때문에 실제 복잡 도 는 O(n)이다.2)
평균 상황:
O(n2)
4.안정성. 이해 성 기억 은 억지로 외 우 는 것 보다 낫다.그래서 분석 해 보 자.안정성 은 바로 두 개의 똑 같은 요소 가 있 는데 정렬 전후의 상대 적 인 위치 가 변화 하 는 지 여 부 는 주로 정렬 할 때 여러 개의 정렬 규칙 이 있 는 상황 에서 사용 된다.정렬 을 삽입 할 때 K1 은 정렬 된 부분 에 있 는 요소 입 니 다.K2 와 K1 을 비교 할 때 K1 뒤에 직접 꽂 습 니 다.(K1 앞 에 꽂 을 필요 가 없습니다.이렇게 하려 면 이동 이 필요 합 니 다!!)따라서 삽입 정렬 은 안정 적 이다.
2.힐 정렬(정렬 삽입)
1.사상:힐 정렬 도 정렬 방법 을 삽입 하 는 것 이 고 사실은 그룹 삽입 방법 이다.먼저 n 보다 작은 정수 d1 을 첫 번 째 증분 으로 정 하고 표 의 모든 기록 을 d1 개 그룹 으로 나 누 며 모든 거리 가 d1 인 배수 의 기록 을 같은 그룹 에 두 고 각 그룹 에서 직접 정렬 을 삽입 합 니 다.그 다음 에 두 번 째 증 가 량 d2(＜d1)를 취하 고 상기 조별 과 순 서 를 반복 하여 취 하 는 증 가 량 dt=1 까지 한다.
예 를 들 어 n 개의 기록 을 d 키 시퀀스 로 나 눕 니 다.
{ R[0]， R[d]， R[2d]，…， R[kd] }
{ R[1]， R[1+d]， R[1+2d]，…，R[1+kd] }
…
{ R[d-1]，R[2d-1]，R[3d-1]，…，R[(k+1)d-1] }
설명:d=5 시,먼저 A[d]부터 앞으로 삽입 하여 A[d-d]를 판단 한 다음 에 A[d+1]와 A[(d+1)-d]를 비교 하여 유추 합 니 다.이번 라운드 후에 원래 의 서열 을 d 개 조로 나 눕 니 다.<뒤에서 앞으로>
2.시간 복잡 도.
가장 좋 은 상황:힐 정렬 의 좋 고 나 쁨 은 보폭 d 의 선택 과 많은 관계 가 있 기 때문에 아직 가장 좋 은 보폭 을 어떻게 선택 하 는 지 알 수 없다(지금 은 비교적 좋 은 선택 이 있 지만 가장 좋 은 지 는 확실 하지 않다).그래서 가장 좋 은 상황 에서 의 알고리즘 시간 복잡 도 를 모른다.
최 악의 경우:O(N*logN),최 악의 경우 와 평균 적 으로 차이 가 많 지 않다.
평균 상황:O(N*logN)
3.안정성.
여러 번 정렬 을 삽입 하기 때문에 우 리 는 한 번 의 삽입 정렬 이 안정 적 이 고 같은 요소 의 상대 적 인 순 서 를 바 꾸 지 않 는 다 는 것 을 알 고 있 습 니 다.그러나 서로 다른 삽입 정렬 과정 에서 같은 요 소 는 각자 의 삽입 정렬 에서 이동 할 수 있 고 마지막 에 안정성 이 흐 트 러 지기 때문에 셸 정렬 은 불안정 합 니 다.(기억 하기 편 하 다 는 추측 이 있 습 니 다.일반적으로 인접 하지 않 은 요소 간 의 교환 이 존재 하면 불안정 한 정렬 일 수 있 습 니 다.)
3.거품 정렬(교환 정렬)
1.기본 사상:무질서 한 구역 에서 인접 한 기록 키워드 간 의 비교 와 위치 교환 을 통 해 키워드 의 최소 기록 을 기포 처럼'수면'까지 점차적으로 위로 떠 올 리 게 한다.
2.시간 복잡 도
가장 좋 은 상황 에서:순서 가 질서 가 있 으 면 n 번 만 비교 해 야 합 니 다.그러므로 O(n)
최 악의 경우: 역순 이 질서 가 있 으 면 비교(n-1)+(n-2)+...+1 이 필요 하기 때문에 O(N*N)입 니 다.
3.안정성
정렬 과정 에서 인접 한 두 요소 의 위치 만 교환 합 니 다.따라서 두 수가 같 을 때 두 수의 위 치 를 바 꿀 필요 가 없다.그래서 그들의 상대 적 인 위 치 는 변 하지 않 았 고 거품 정렬 알고리즘 은 안정 적 입 니 다!
4.빠 른 정렬(정렬 교환)
1.사상:거품 정렬 이 개선 되 었 습 니 다.정렬 을 기다 리 는 n 개의 기록 에서 하나의 기록(보통 첫 번 째 기록)을 취하 고 이 기록 을 적당 한 위치 에 두 면 데이터 서열 은 이 기록 에 의 해 두 부분 으로 나 뉜 다.모든 키 워드 는 이 기록 키워드 보다 작은 기록 을 앞부분 에 놓 고,모든 큰 기록 을 뒷부분 에 놓 고,이 기록 을 이 두 부분의 중간 에 놓 으 며,이 과정 을 빠 른 정렬 이 라 고 한다.
2.알고리즘 복잡 도
가장 좋 은 경우:매번 서열 을 두 부분 으로 나 누 기 때문에 O(N*logN)입 니 다.
최 악의 경우:기본적으로 질서 가 있 을 때 거품 정렬 으로 퇴화 되 고 거의 N*N 회 를 비교 해 야 하기 때문에 O(N*N)입 니 다.
3.안정성
매번 중축 원소 와 교환 해 야 하기 때문에 원래 의 순서 가 흐 트 러 질 수 있다.서열 이 5,3,4,3,8,9,10,11 이면 3 의 순 서 를 흐 트 러 뜨 린 다.그 러 니까 빠 른 정렬 은 불안정 하 다!
5.정렬 을 직접 선택(정렬 선택)
1.사상:먼저 정렬 되 지 않 은 서열 에서 최소 요 소 를 찾 아 정렬 서열 의 시작 위치 에 저장 한 다음 에 나머지 정렬 되 지 않 은 요소 에서 최소 요 소 를 계속 찾 은 다음 에 정렬 서열 의 끝 에 놓는다.모든 요소 가 정렬 될 때 까지 유추 합 니 다.구체 적 인 방법 은 최소 요소 와 정렬 되 지 않 은 부분의 첫 번 째 교환 을 선택 하여 서열 의 앞 을 질서 있 게 하 는 것 이다.
2.시간 복잡 도.
가장 좋 은 경우:0 번 교환 하지만 매번 가장 작은 요 소 를 찾 아야 하기 때문에 N*N 번 을 옮 겨 다 녀 야 하기 때문에 O(N*N)입 니 다.교환 횟수 감소!
최 악의 경우,평균 상황:O(N*N)
3.안정성
매번 정렬 되 지 않 은 시퀀스 A 의 최소 요소 x 와 A 의 첫 번 째 요 소 를 선택 하기 때문에 거 리 를 뛰 어 넘 으 면 요소 간 의 상대 적 인 위 치 를 파괴 할 수 있 기 때문에 정렬 을 선택 하 는 것 이 불안정 합 니 다!
여섯,더미 정렬
1.사상:완전 이 진 트 리 에서 부모 노드 와 아이 노드 간 의 내 적 관 계 를 이용 하여 현재 무질서 한 지역 에서 키워드 가 가장 크 거나 가장 작은 기록 을 선택한다.즉,최소 더 미 를 예 로 들 면 뿌리 노드 는 최소 원소 이 고 비교적 큰 노드 는 더 미 를 쌓 는 부근 에 분포 한다.
2.알고리즘 복잡 도
최 악의 경우 최 악의 경우 O(N*logN)에 가 깝 기 때문에 효과 가 좋 은 정렬 알고리즘 입 니 다.
3.안정성
쌓 기 정렬 은 쌓 기 를 계속 조정 해 야 하기 때문에 불안정 한 정렬 입 니 다!
7.병합 정렬
1.사상:두 개 또는 두 개 이상 의 질서 표를 여러 번 합 쳐 새로운 질서 표 로 만든다.
2.알고리즘 시간 복잡 도
가장 좋 은 경우:한 번 의 병합 은 n 번 이 필요 하고 모두 logN 번 이 필요 하기 때문에 O(N*logN)입 니 다.
최 악의 경우 평균 에 가 까 운 경우 O(N*logN)
설명:길이 가 n 인 파일 에 대해 logN 번 2 번 을 병합 해 야 합 니 다.모든 병합 시간 은 O(n)이기 때문에 그 시간 복잡 도 는 가장 좋 은 상황 에서 든 최 악의 상황 에서 든 모두 O(nlgn)입 니 다.
3.안정성
병합 정렬 의 가장 큰 특징 은 안정 적 인 정렬 알고리즘 이라는 것 이다.병합 과정 에서 원소 의 상대 적 인 위 치 를 바 꾸 지 않 을 것 이다.
4.단점 은 O(n)의 추가 공간 이 필요 하 다 는 것 이다.하지만 다 중 링크 정렬 에 적합 합 니 다.
5.C++정렬 알고리즘 코드 는 다음 과 같이 요약 합 니 다.
#include<iostream>
#include<vector>
#include<limits>
using namespace std;
// ， , ，
// ， ， ，
// ， ， ， ，
//
void InsertSort(vector<int> &data)
{
if(!data.empty())
return;
int size = data.size();
for(int j = 1;j < size; ++j)// data[0]
{
int temp = data[j];
int index = j-1;
while(index >= 0 && data[index] > temp)
{
data[index+1] = data[index];
index--;
}
data[index+1] = temp;
}
}
// ， ，
// sub1 sub2 ，result sub1 sub2
void Merge(vector<int> &result,vector<int> &sub1,vector<int> &sub2)
{
sub1.push_back(INT_MAX);
sub2.push_back(INT_MAX);
int number1 = sub1.size();
int number2 = sub2.size();
int sub1_i = 0,sub2_i = 0;
for(auto it = result.begin();it != result.end();++it)
{
if(sub1[sub1_i] <= sub2[sub2_i])
{
*it = sub1[sub1_i];
++sub1_i;
}
else
{
*it = sub2[sub2_i];
++sub2_i;
}
}
}
void MergeSort(vector<int>& coll)// ， ，
{
unsigned int number=coll.size();
if(number<=1)
return;
unsigned int mid=number/2;
vector<int> sub1;
vector<int> sub2;
for(unsigned int i=0;i<mid;++i)
{
sub1.push_back(coll[i]);
}
for(unsigned int j=0;j<number-mid;++j)
{
sub2.push_back(coll[mid+j]);
}
MergeSort(sub1);
MergeSort(sub2);
Merge(coll,sub1,sub2);
}
// , ，
// ， ， ， n ，
void BubleSort(vector<int> &data)
{
int size = data.size();
bool sort_flag = false;
for(int i = 0;i < size;++i)
{
if(sort_flag == true) // ， sort_flag = false; ，
return;
sort_flag = true;
for(int j = i;j < size;++j)// ， i
{
if(data[i] > data[j])
{
swap(data[i],data[j]);
sort_flag = false;
}
}
}
}
//---------------------------------- -------------------------
//
int Partition(int data[],int length,int start,int end)
{
if(data == NULL || length <= 0 || start < 0 || end >= length)
throw new exception(" Invalid Parameters");
int index = rand()%(start-end+1)+start;
swap(data[index],data[end]);
int left = start-1;// ， ， ，if ，
for(index = start;index < end;++index)
{
if(data[index] < data[end])
{
++left;
if(left != index)
swap(data[left],data[index]);
}
}
++left;
swap(data[left],data[end]);
return left;
}
void QuickSort(int data[],int length,int start,int end)
{
if(start == end)
return;
int index = Partition(data,length,start,end);
if(index > start)
QuickSort(data,length,start,index-1);
if(index < end)
QuickSort(data,length,index+1,end);
}
// 1. 2、 3、
void MaxHeapIFY(vector<int> &data,int local,int length)// ,local ,length
{
if(!data.empty())
return;
int left = local*2+1;// 0 ， 2i
int right = local*2;
int largest = local;
if(left < length && data[left] > data[local])
{
largest = left;
}
if(right < length && data[right] > data[local])
{
largest = right;
}
if(largest != local)
{
swap(data[largest],data[local]);
MaxHeapIFY(data,largest,length);//largest ， length ，
}
}
// , (length/2-1)
void BuileMaxHeap(vector<int> &data ,int length)
{
int root = length/2-1;
for(int i = root;i >= 0;--i)
{
MaxHeapIFY(data,i,length);
}
}
// ， ， n-1 ，
void HeapSort(vector<int> &data)
{
if(!data.empty())
return;
BuileMaxHeap(data,data.size());
int length = data.size();
for(int i = length-1;i >= 0;--i)
{
swap(data[0],data[i]);
--length;
MaxHeapIFY(data,0,length);
}
}
// , , ， ，
void SelectionSort(vector<int> &data)
{
int size = data.size();
--size;
for(int i = 0;i < size-1;++i)
{
int min = i;
for(int j = i+1;j < size;++j)
{
if(data[min] > data[j])
min = j;
}
swap(data[min],data[i]);
}
}
// ， ， d ( d )， ，
// d ， ， d=1 ， ， ， ， 1
void ShellSort(vector<int> &data)
{
int size = data.size();
size;
int separate = size / 2;
while(separate > 0)
{
for(int i = separate;i < size;++i)
{
int temp = data[i];
int j = i - separate;
while(j >=0 && data[j] > temp)
{
data[j+separate] = data[j];
j = j-separate;
}
data[j+separate] = temp;
}
separate /= 2;//
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU 원활 공사 & & 원활 공사 (차 트 법)모 성 은 도시 의 교통 상황 을 조사 하여 기 존의 도시 도로 통계 표를 얻 었 고 표 에는 모든 도로 가 직접 연 결 된 도시 가 열거 되 어 있다.성 정부의 '원활 한 공사' 목 표 는 성 전체의 어느 두 도시...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
