데이터 구조: 정렬 알고리즘 총화
11731 단어 DataStruct
정렬 알고리즘
시간 복잡 도 평균 상황
시간 복잡 도 최 적 상황
시간 복잡 도 최 악의 경우
보조 공간
안정성
거품 정렬
O(n^2)
O(n)
O(n^2)
O(1)
안정시키다
정렬 선택
O(n^2)
O(n^2)
O(n^2)
O(1)
불안정
삽입 정렬
O(n^2)
O(n)
O(n^2)
O(1)
안정시키다
힐 정렬
O(n^2)~O(n*log(n))
O(n)
O(n^2)
O(1)
불안정
더미 정렬
O(n*log(n))
O(n*log(n))
O(n*log(n))
O(1)
불안정
정렬
O(n*log(n))
O(n*log(n))
O(n*log(n))
O(n)
안정시키다
빠 른 정렬
O(n*log(n))
O(n*log(n))
O(n^2)
O(log(n))~O(n)
불안정
거품 정렬:
선형 표 의 거품 정렬 은 이중 순환 으로 교체 하 는 방식 을 사용 하고 정렬 방식 은 큰 것 에서 작은 것 으로 내부 순환 은 매번 최대 수 에서 정렬 할 수 있 는 표 까지 나 오 며 외부 순환 은 현재 정렬 할 수 있 는 표 의 길 이 를 제어 합 니 다.이 과정 은 마치 물 속 의 기포 가 튀 어 나 오 는 과정 처럼 작은 기포 가 아래 에서 위로 튀 어 나 오 는 과정 에서 점점 커지 고 마지막 에 큰 기포 가 수면 위로 튀 어 나온다.
알고리즘 프로 세 스: (큰 것 에서 작은 것 으로 정렬 하고 뒤로 옮 겨 다 니 기)
1. 매번 앞 뒤 두 개의 수 를 옮 겨 다 니 며 앞의 수가 뒤의 수 보다 작은 두 개의 수 를 교환 하 는 위 치 를 만난다.
2. 한 번 순환 이 끝나 면 다음 순환 의 길 이 는 1 로 줄어든다.
3. 전체 배열 을 옮 겨 다 닐 때 까지.
#include "sort.h"
vector popSort(vector& src)
{
int n = src.size();
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n - i - 1; ++j)
{
if (src[j] < src[j + 1])
SWAP(src[j], src[j + 1]);
}
}
return src;
} 개 선 된 거품 정렬:
거품 이 발생 하 는 과정 에 대해 정렬 (큰 것 에서 작은 것 으로 정렬) 을 하고 표를 옮 겨 다 니 는 과정 에서 왼쪽 에서 오른쪽으로 옮 겨 다 니 는 과정 에서 최소 값 이 표 꼬리 까지 나 오고 오른쪽 끝 표 시 는 왼쪽으로 한 명 미 끄 러 지 며 오른쪽 에서 왼쪽으로 옮 겨 다 니 는 과정 에서 가장 큰 값 이 표 머리 까지 나 오고 왼쪽 표 시 는 오른쪽으로 한 명 미 끄 러 집 니 다.마지막 왼쪽 끝 에 표 시 된 것 이 오른쪽 끝 에 표 시 된 것 과 같 을 때 까지.
알고리즘 프로 세 스:
1. 왼쪽 에서 오른쪽으로 선형 표를 옮 겨 다 니 며 앞 뒤 데 이 터 를 비교 하고 왼쪽 데이터 가 오른쪽 시간 보다 두 개의 데 이 터 를 바 꾸 면 오른쪽 표지 가 끝 날 때 까지 오른쪽 표지 가 왼쪽으로 한 자 리 를 이동 합 니 다.
2. 오른쪽 표지 에서 왼쪽 표지 로 옮 겨 다 니 며 앞 뒤 데 이 터 를 비교 하고 왼쪽 데이터 가 오른쪽 시간 보다 두 개의 데 이 터 를 바 꾸 면 왼쪽 표지 가 끝 날 때 까지 왼쪽 표 시 는 오른쪽으로 한 자 리 를 이동 합 니 다.
3. 왼쪽 끝 표시 가 오른쪽 끝 표시 와 같 을 때 정렬 이 끝 납 니 다.
#include "sort.h"
vector advancePopSort(vector& src)
{
int left = 0, right = src.size() - 1;
while (left < right)
{
for (int i = left; i < right; ++i)
{
if (src[i] < src[i + 1])
SWAP(src[i], src[i + 1]);
}
right--;
for (int j = right; j > left; --j)
{
if (src[j] > src[j - 1])
SWAP(src[j], src[j - 1]);
}
left++;
}
return src;
} 정렬 선택:
데이터 배열 은 큰 것 부터 작은 것 까지 정렬 을 선택 하고 선형 표 에서 정렬 을 선택 하 는 기본 사상 은 한 무더기 의 데이터 에서 가장 큰 숫자 와 헤더 의 데 이 터 를 선택 하여 바 꾼 다음 에 나머지 숫자 에서 두 번 째 큰 숫자 와 헤더 에서 시작 하 는 두 번 째 수 를 선택 하여 바 꾸 는 것 이다. 이에 따라 전체 표를 옮 겨 다 닐 때 까지 아래로 내 려 가 는 것 이다.
알고리즘 프로 세 스:
1. 데 이 터 를 반복 해서 옮 겨 다 니 며 가장 큰 데이터 와 현재 헤더 위치의 수 를 찾 아 바 꿉 니 다.
2. 교환 이 완료 되면 표 머리 는 정렬 된 다음 숫자 로 표 시 됩 니 다.
3. 표 의 모든 데이터 가 질서 가 있 을 때 까지.
#include "sort.h"
// ：
vector seekSort(vector& src)
{
int n = src.size();
for (int i = 0; i < n - 1; ++i)
{
int pos = -1, max = src[i];
for (int j = i + 1; j < n; ++j)
{
if (max < src[j])
{
max = src[j];
pos = j;
}
}
if (pos != -1)
SWAP(src[i], src[pos]);
}
return src;
}
// ：
vector selectSort(vector& src)
{
int n = src.size();
for (int i = 0; i < n - 1; ++i)
{
int min = i;
for (int j = i + 1; j < n; ++j)
{
if (src[j] > src[min])
min = j;
}
if (min != i)
{
SWAP(src[i], src[min]);
}
}
return src;
} 삽입 정렬:
선형 표 의 삽입 정렬, (큰 것 에서 작은 것 까지) 정렬 을 삽입 하 는 기본 적 인 사 고 는 하나의 숫자 부터 질서 있 게 보고 다음 숫자 를 취한 다 는 것 이다. 만약 에 횟수 가 첫 번 째 숫자 보다 작 으 면 첫 번 째 수의 뒤에 횟수 를 꽂 고 반대로 첫 번 째 수 를 한 자리 뒤로 옮 기 고 첫 번 째 수 앞 에 횟수 를 꽂 으 면 두 개의 수 를 포함 하 는 서열 을 구성한다.그 다음 에 세 번 째 수 를 꺼 내 고 서열 이 있 는 위 치 를 옮 겨 다 니 며 적당 한 삽입 위 치 를 찾 아 삽입 한 후의 수 를 전체적으로 한 자리 뒤로 옮 깁 니 다.전체 표 의 데이터 가 다 취 소 될 때 까지 이렇게 숫자 를 삽입 합 니 다.
알고리즘 프로 세 스:
1. 숫자 를 취 하 는 과정 은 두 번 째 숫자 부터 시작한다.
2. 적당 한 위 치 를 찾 아 위 치 를 뒤로 이동 합 니 다.
3. 표 의 데 이 터 를 모두 꺼 낼 때 까지.
#include "sort.h"
vector insertSort(vector& src)
{
int n = src.size();
for (int i = 1; i < n; ++i)
{
int temp = src[i], pos = -1;
for (int j = i - 1; j >= 0; --j)
{
if (src[j] < temp)
{
pos = j;
}
}
if (pos != -1)
{
for (int k = i; k > pos; --k)
{
src[k] = src[k - 1];
}
src[pos] = temp;
}
}
return src;
} 힐 정렬:
선형 표 는 힐 정렬 을 한다. (큰 것 에서 작은 것 까지) 힐 정렬 은 그 라 데 이 션 보폭 의 삽입 정렬 이다. 처음에 보폭 이 크 면 첫 번 째 정렬 과정 에서 서열 이 상대 적 으로 질 서 를 확보 할 수 있다. 그 다음 에 걸음 길 이 를 줄 이 고 다음 순 서 는 부분 적 인 조정 만 하면 걸음 길이 가 1 이 될 때 약간 조정 하면 정렬 이 끝난다.
알고리즘 프로 세 스:
1. 보폭 을 선택 하고 정렬 을 삽입 합 니 다.
2. 보폭 을 줄 여 정렬 을 삽입 합 니 다.
#include "sort.h"
vector shellSort(vector& src)
{
int n = src.size();
for (int step = n / 2; step > 0; step /= 2)
{
for (int i = step; i < n; ++i)
{
for (int j = i - step; j + step < n; j += step)
{
if (src[j] > src[j + step])
SWAP(src[j], src[j + step]);
}
}
}
return src;
} 더미 정렬:
쌓 기 순 서 는 이 진 트 리 의 확률 을 이용 하여 큰 지붕 더미 와 작은 지붕 더 미 를 구성 하 는 것 이다. 큰 지붕 더미 에서 모든 나무 뿌리 노드 의 수 치 는 항상 좌우 노드 보다 크 거나 같 으 며 작은 지붕 더 미 는 반대로 뿌리 노드 의 수 치 는 모두 좌우 노드 보다 작다.그러나 선형 표를 쌓 아 정렬 할 때 쌓 아 올 릴 필요 가 없다. 즉, 이 진 트 리 를 구축 할 필요 가 없다.질 서 는 규칙 을 적용 해 야 한다.
/ / 아래 에 i 로 표 시 된 노드 는 왼쪽 잎 노드 의 아래 표 시 는 2i + 1 이 고 오른쪽 잎 노드 아래 표 시 는 2i + 2 / / 큰 지붕 더미: a [i] > = a [2 * i + 1] & a [i] > = a [2 * i + 2];
/ / 작은 지붕 더미: a [i] < = a [2 * i + 1] & & a [i] < = a [2 * i + 2];
따라서 매번 서열 에 대해 큰 지붕 더미 나 작은 지붕 더 미 를 조정 할 때마다 최대 수 나 최소 수 를 얻 을 수 있 고 횟수 를 더미 에서 선형 표 의 끝 을 분리 한 다음 에 나머지 수 를 조정 하여 모든 수 를 질서 있 게 조정 할 수 있다.
#include "sort.h"
// i 2i + 1, 2i + 2
// ：a[i] >= a[2 * i + 1] && a[i] >= a[2 * i + 2];
// ：a[i] <= a[2 * i + 1] && a[i] <= a[2 * i + 2];
void adjustHeep(vector& src, int end)
{
for (int i = end / 2; i >= 0; --i)
{
if (2 * i + 2 <= end && src[i] > src[2 * i + 2])
{
SWAP(src[i], src[2 * i + 2]);
}
if (2 * i + 1 <= end && src[i] > src[2 * i + 1])
{
SWAP(src[i], src[2 * i + 1]);
}
}
}
vector heepSort(vector& src)
{
for (int i = src.size() - 1; i > 0; --i)
{
adjustHeep(src, i);
SWAP(src[0], src[i]);
}
return src;
} 병합 정렬:
병합 정렬 사상 은 데이터 구 조 를 처음 배 웠 을 때 항상 하 는 데이터 구조 문제 와 유사 하 다. 두 개의 질서 있 는 서열 을 하나의 질서 있 는 서열 로 합 친다.따라서 무질서 한 서열 을 정리 하고 정렬 하면 그 과정 은 재 귀 작업 과 결합 하여 진행 하기 쉽다.재 귀적 으로 깊이 들 어 가 는 과정 에서 필요 하지 않 은 서열 을 하나의 단독 수 로 나 누고 단독 수 는 질서 있 는 것 으로 간주 하 며 재 귀적 으로 거 슬러 올 라 가 는 과정 에서 이런 단독 수 를 1 대 1 로 합 쳐 서열 로 만 들 고 최종 적 으로 큰 질서 있 는 서열 로 합 친다.
#include "sort.h"
vector& mergeStep(vector& src, int af, int at, int bf, int bt)
{
vector a(src.begin() + af, src.begin() + at + 1);
vector b(src.begin() + bf, src.begin() + bt + 1);
size_t i = 0, j = 0;
while (i < a.size() && j < b.size())
{
if (a[i] < b[j])
{
src[af] = a[i];
i++;
}
else
{
src[af] = b[j];
j++;
}
af++;
}
if (i < a.size())
{
for (; i < a.size(); ++i)
{
src[af++] = a[i];
}
}
if (j < b.size())
{
for (; j < b.size(); ++j)
{
src[af++] = b[j];
}
}
return src;
}
vector& mergerSort(vector& src, int left, int right)
{
if (left >= right)
return src;
int mid = (left + right) / 2;
mergerSort(src, left, mid);
mergerSort(src, mid + 1, right);
mergeStep(src, left, mid, mid + 1, right);
} 빠 른 정렬:
빠 른 정렬 사상 은 매번 무질서 한 서열 에서 하나의 기 수 를 찾 아 서열 을 구분 하고 기수 보다 큰 수 는 한쪽 에 두 고 기수 보다 작은 수 는 다른 쪽 에 두 는 것 이다.다음 에 기수 양쪽 의 무질서 한 수 를 나 누 어 그 중에서 기 수 를 찾 아 구분 하면 기 수 를 선택 한 후에 양쪽 에 숫자 가 없어 서 빠 른 정렬 이 끝 납 니 다.
그 공간 복잡 도 는 O (1) 이기 때문에 한 단위 의 보조 공간 이 기수 의 값 을 저장 해 야 하기 때문에 대 비 를 시작 하 는 방향 은 서열 에서 기수 에 비해 다른 쪽 이다. 예 를 들 어 왼쪽 에서 기 수 를 취하 면 비 교 를 시작 할 때 취 하 는 수 는 서열 의 오른쪽 에서 시작 하여 이렇게 교환 하 는 것 이다.
기수 정렬 을 선택 하 는 과정 에서 끝 나 는 표 지 는 왼쪽 위치 표시 가 오른쪽 위치 표시 와 같은 값 입 니 다.어 릴 때 부터 크게 정렬 하면 기수 보다 작은 것 은 왼쪽 에 놓 고 기수 보다 큰 것 은 오른쪽 에 놓는다.
#include "sort.h"
#include
//vector ，
vector& quickSort(vector& src, int left, int right)
{
if (left >= right)
return src;
int l = left;
int r = right;
int temp = src[left];
while (l < r)
{
while (l < r && src[r] >= temp)
{
r--;
}
src[l] = src[r];
while (l < r && src[l] <= temp)
{
l++;
}
src[r] = src[l];
}//r == l
src[l] = temp;
quickSort(src, left, l - 1);
quickSort(src, r + 1, right);
}
// ：
int seek(vector&src, int l, int r)
{
int index = l;
int temp = src[l];
while (l < r)
{
while (l < r && src[r] <= temp)
{
r--;
}
src[l] = src[r];
while (l < r && src[l] >= temp)
{
l++;
}
src[r] = src[l];
}//l == r
src[l] = temp;
index = l;
return index;
}
// ：
vector& quickSort(vector& src)
{
size_t index = seek(src, 0, src.size() - 1);
stack range;
if (index - 1 > 0)//
{
range.push(0);
range.push(index - 1);
}
if (index + 1 < src.size() - 1) //
{
range.push(index + 1);
range.push(src.size() - 1);
}
while (!range.empty())
{
size_t right = range.top();
range.pop();
size_t left = range.top();
range.pop();
index = seek(src, left, right);
if (index - 1 > left)
{
range.push(left);
range.push(index - 1);
}
if (index + 1 < right)
{
range.push(index + 1);
range.push(right);
}
}
return src;
} 관련 내용:
위 글 에 사 용 된 헤더 파일 sort. h
#pragma once
#include
#include
using namespace std;
#define SWAP(a, b) a^=b^=a^=b 위의 main 함수
#include "sort.h"
extern vector advancePopSort(vector&);
extern vector seekSort(vector&);
extern vector selectSort(vector&);
extern vector insertSort(vector& src);
extern vector& quickSort(vector& src, int left, int right);
extern vector shellSort(vector& src);
extern vector& mergerSort(vector& src, int left, int right);
extern vector heepSort(vector& src);
extern vector& quickSort(vector& src);
void showResult(const vector& src)
{
typedef vector::const_iterator vi_itr;
for (vi_itr itr = src.begin(); itr != src.end(); ++itr)
{
cout << *itr << " ";
}
cout << endl;
}
int main()
{
int buf[] = { 2, 3, 1, 7, 5, 8, 4, 3, 6 };
//vector sort_buff = insertSort(vector(buf, buf + 9));
/*vector sort_buff(buf, buf + 9);
quickSort(sort_buff, 0, 8);*/
//vector sort_buff = mergerSort(vector(buf, buf + 9), 0, 8);
vector sort_buff = shellSort(vector(buf, buf + 9));
showResult(sort_buff);
} C + + 용기 vector 에 사용 되 는 정렬 알고리즘 은 빠 른 정렬 알고리즘 이지 만 정렬 과 정렬 을 삽입 하여 이 루어 집 니 다.
알고리즘 의 안정성 이란 같은 수가 정렬 전후 에 상대 적 인 위 치 를 유지 하고 안정 적 인 정렬 알고리즘 을 위해 그렇지 않 으 면 불안정한 정렬 알고리즘 을 말한다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
데이터 구조 연습 문제 - 1 순서 표 의 삽입 연산description 알 고 있 는 순서 표 L 은 점점 질서 가 있 고 프로그램 을 작성 하 며 X 를 선형 표 의 적당 한 위치 에 삽입 하여 선형 표 의 질서 성 을 유지 합 니 다. input 첫 번 째 줄 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
