상용 정렬 알고리즘 소스 코드 (빠 른 정렬, 삽입 정렬, 쌓 기 정렬, 거품 등)
17055 단어 소 계산법
void swap(int &x, int &y)
{
x = x^y;
y = x^y;
x = x^y;
}O (N * N) 의 3 대 알고리즘 (1) 은 정렬 핵심 사상 을 선택 하고 매번 뒤의 m 개 요소 에서 가장 작은 것 을 찾 아 현재 m 개 요소 의 첫 번 째 위치 에 놓 습 니 다.
void selecttsort(int *a, int n)
{
for (int i = 0; i < n - 1; ++i)
{
int index = i;
int minv = a[i];
for (int j = i+1; j < n; ++j)
{
if (a[j] < minv)
{
minv = a[j];
index = j;
}
}
if (index != i)
swap(a[index], a[i]);
}
}(2) 정렬 핵심 사상 을 삽입 하고 카드 를 치 는 것 과 유사 하 며 모든 요 소 를 대상 으로 '적당 한' 위치 에 삽입 합 니 다.
void insertsort(int *a, int n)
{
for (int i = 1; i < n; ++i)
{
int j;
for (j = i - 1; j >= 0; --j)
if (a[j] < a[i])
break;
++j;// j++， j i， >=i ， j++ [j,x]
int tmp = a[i];
for (int k = i - 1; k >= j; --k)
a[k + 1] = a[k];
a[j] = tmp;
}
}
(3) 거품 서열 의 핵심 사상 은 위 에서 아래 까지 두 가 지 를 끊임없이 비교 하고 교환 하 는 것 이다.이것 은 기본 산법 으로 양 방향 거품 등 으로 수정 할 수 있다.
void popsort(int *a, int n)
{
for (int i = 0; i < n - 1; ++i)
{
for (int j = 0; j <= n - i - 2; ++j)
{
if (a[j] > a[j + 1])
swap(a[j], a[j + 1]);
}
}
}O (Nlog (N) 의 세 가지 방법 (4) 은 핵심 사상 을 신속하게 정렬 하고 닻 점 을 찾 은 다음 에 닻 점 의 양쪽 을 반복 해서 정렬 을 한다.
int getmidinQS(int *a, int b, int e)
{
//array in [b,e]
int base = a[b];
while (b < e)
{
while (b < e && a[e] >= base)
--e;
if (b < e)
swap(a[b], a[e]);
while (b < e && a[b] <= base)
++b;
if (b < e)
swap(a[b], a[e]);
}
return b;
}
void quicksort(int *a, int b, int e)
{
if (b < e)
{
// 1 get min
int mid = getmidinQS(a, b, e);
// 2 quick sort at left side and right side
quicksort(a, b, mid - 1);
quicksort(a, mid+1, e);
}
}
void quicksort(int *a, int n)
{
return quicksort(a, 0, n - 1);
}(5) 핵심 사상 을 정리 하고 정렬 하 며 먼저 양쪽 에서 각각 정렬 한 다음 에 병합 한다.관건 은 합병 이다.
// merge data [b,mid][mid+1,e] to [b,e]
void mergetwo(int *a, int b, int mid, int e)
{
//merge [b,mid] + [mid+1,e] -->[b,e]
int len1 = mid - b + 1;
int len2 = e - mid;
if (!len1 || !len2) return;
int * p = new int[len1];
int *q = new int[len2];
memcpy(p, a+b, sizeof(int)*len1);
memcpy(q, a + b+len1, sizeof(int)*len2);
int i = 0, j = 0,k=b;
while (i < len1&&j < len2)
{
if (p[i] < q[j])
{
a[k++] = p[i++];
}
else
{
a[k++] = q[j++];
}
}
while (i < len1)
{
a[k++] = p[i++];
}
while (j < len2)
{
a[k++] = q[j++];
}
delete[]p;
delete[]q;
}
void mergesort(int *a, int b,int e)
{
//1 merge sort two side
if (b < e)
{
int mid = (b + e) / 2;
mergesort(a, b, mid);
mergesort(a, mid+1, e);
//2 merge two side to one whole
mergetwo(a, b, mid, e);
}
}
void mergesort(int *a, int n)
{
return mergesort(a, 0, n - 1);
}(6) 쌓 기 정렬 관건 사상: 1: 쌓 기.작은 것 부터 큰 것 까지 정렬 하 는 것 은 큰 것 부터 작은 것 까지 정렬 하 는 것 이다.쌓 는 과정, 즉 쌓 기 (쌓 기, 여 기 는 완전 이 진 트 리 이 고 배열 도 완전 이 진 트 리 의 표현 매개체) 의 모든 비 잎 노드 를 조정 하 는 과정 이다.잎 노드 를 고려 하지 않 는 이 유 는 쌓 인 성질 때문에 우 리 는 비 잎 노드 에 만 관심 을 가 져 야 한다 고 생각 하기 때문이다.조정 과정 은 두 단계 로 나 뉜 다. 1) 비 잎 노드 와 두 아이 (적어도 한 아이 가 존재 한다) 는 최대 치 를 취한 다.2) 현재 잎 이 아 닌 노드 가 최대 치 를 가지 지 않 으 면 두 개의 값 을 교환 합 니 다. 이때 교환 되 는 아이 자체 도 아이 가 있 을 수 있 기 때문에 중복 조정 이 필요 합 니 다. 재 귀 중복 호출 을 사용 할 수 있 습 니 다.2: 쌓 아 올 리 기 정렬 은 N - 1 번 땅 입 니 다. 매번 쌓 아 올 리 기 요소 (횟수 는 i, i = 0, 1,,, N - 1) 와 현재 배열 의 N - 1 - i 개 요 소 를 교환 (교환 후 배열 의 마지막 요소 부터 육 로 는 계속 정렬 서열 을 얻 었 습 니 다) 한 다음 에 쌓 아 올 리 기 요 소 를 조정 합 니 다.그래서 쌓 기 정렬 과 쌓 기 는 쌓 기 를 조정 하 는 과정 에 사용 된다.
void modifyheap(int *a, int base, int len)
{
int lc = base * 2 + 1;// left child index
int rc = lc + 1;//right child index
int maxv = a[base];
int index = base;
if (lc >= len) return;
if (lc < len && maxv < a[lc])
{
index = lc;
maxv = a[lc];
}
if (rc < len && maxv < a[rc])
{
index = rc;
maxv = a[rc];
}
if (index != base)
{
swap(a[base], a[index]);
modifyheap(a, index, len);
}
}
void buildheap(int *a, int n)
{
for (int i = n / 2 - 1; i >= 0; --i)
{
modifyheap(a, i, n);
}
}
void heapsort(int *a, int n)
{
buildheap(a, n);
for (int i = 0; i 1 ; ++i)
{
swap(a[0], a[n - i - 1]);
modifyheap(a, 0, n - i - 1);
}
}(7) 힐 정렬
void shellsort(int *a, int n)
{
int gap = n / 2;
for (; gap > 0; gap /= 2)
for (int i = 0; i < gap; ++i)
{
// use select sort to sort data at,i,i+gap,i+2gap....
// use select sort internal
for (int j = i + gap; j < n; j += gap)
{
int data = a[j],k;
for (k = j - gap; k >= i; k -= gap)
{
if (a[k] < a[j])
break;
}
if (k < i)
k = i;
else
k += gap;// move data [k,,,j-gap] to the next one
for (int l = j - gap; l >= k; l -= gap)
a[l + gap] = a[l];
a[k] = data;
}
}
}
(8 ~ 10) (8) 계수 정렬
다음 프로그램 에서 보 듯 이 p 배열 은 데이터 i 보다 크 지 않 은 데이터 의 개 수 를 저장 합 니 다.
void countsort(int *a, int *b, int n, int k)
{
int *p = new int[k+1];
memset(p, 0, sizeof(int)*(k+1));
for (int i = 0; i < n; ++i)
p[a[i]]++;
for (int i = 1; i <= k; ++i)
p[i] += p[i - 1];
for (int i = 0; i < n; ++i)
{
b[p[a[i]] - 1] = a[i];
p[a[i]]--;
}
delete[]p;
}(9) 기수 정렬 (10) 통 정렬 개인 이해 통 정렬 은 실제 적 으로 hash 를 만 드 는 과정 이 고 hash 의 실현 이다.예 를 들 어 hash 의 길이 가 10 이면 통 개 수 는 10 이 고 모든 통 안의 데 이 터 는 유연 하 게 처리 할 수 있다 (예 를 들 어 hash 충돌 의 체인 법 에 따라 하나의 링크 를 형성 하거나 데이터 구 조 를 수정 하여 count 를 나타 내 는 필드 를 추가 하 는 등). 따라서 데이터 개 수 는 N 이 고 통 개 수 는 M 이 므 로 시간 복잡 도 는 O (N) + M * N / M (logN / M) = O (N) 이다.+ NLogN - NLogM 그래서 통 의 개수 와 데이터 의 개수 가 일치 할 때 시간 복잡 도 는 O (N) 이 고 이때 통 의 정렬 은 두 가지 유사 한 알고리즘 이 있 습 니 다. 1. 데이터 범위 에 따라 하나의 배열 을 직접 정의 합 니 다. 예 를 들 어 1000 개의 데이터 에 따라 1000 개의 길이 배열 을 정의 합 니 다. 2: 비트 맵 이라는 두 가지 방법 으로 모두 빈 칸 을 판단 하거나 정렬 할 수 있 습 니 다.그래서 전체적으로 말 하면 통 정렬 은 데 이 터 를 세그먼트 로 나 눈 다음 에 세그먼트 내 에서 정렬 하 는 것 이다.형 성 된 데이터 구 조 는 hash 표 일 수 있 습 니 다.
따라서 시간 복잡 도 에서 볼 때 N2 선택 정렬 + 삽입 정렬 + 거품 정렬 NLogN 빠 른 정렬 + 병합 정렬 + 쌓 기 정렬 + 유사 O (N) hash, bitmap, 통 정렬, 계수 정렬 등 을 간략하게 기억 할 수 있 습 니 다.
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(2) 데이터 가 무질서 할 때 특정한 데이터 의 존재 성 을 찾 으 면 데이터 정렬 을 고려 하여 찾 을 수 있 지만 이때 복잡 도 는 적어도 NlogN 일 수도 있 고 정렬 을 고려 하지 않 고 hash 를 직접 만 들 수 있 으 며 hash 값 에 따라 판단 하면 복잡 도가 더 낮 을 수 있다.(3) 수치 존재 성 을 판단 하고 데이터 범위 가 확정 되면 bitmap 를 사용 할 수도 있 으 며, 2bit 표징 을 사용 하면 '데이터 가 한 번 존재 한다', '데이터 가 두 번 존재 한다' 등 을 나 타 낼 수도 있다.범위 가 확실 하지 않 으 면 존재 성 을 판단 할 때 hash 를 사용 할 수 있 습 니 다. 아무튼 복잡 도 는 낮은 것 에서 높 은 것 으로 O (1), O (logN) O (N) 는 각각 hash, bitmap 입 니 다.
대량의 데이터 처 리 를 할 때 정렬 하 는 데 시간 이 많이 걸린다. 예 를 들 어http://www.bianceng.cn/Programming/sjjg/201412/47166_3. htm 는 500 만 개의 수 능 성적 에 대해 순 위 를 매 긴 다. 만약 에 빠 른 배열 등 복잡 도 를 500 만 log (500 만) 로 직접 사용 하고 hash 를 만 들 면 점수 가 같은 성적 (학생 이름, 성적 등 포함) 을 하나의 체인 에 걸 면 O (N) 의 응답 만 있 으 면 통 정렬 도 이런 효 과 를 얻 을 수 있다.계수 정렬 등 도 가능 합 니 다.
예 를 들 어 1 억 개의 QQ 번호 로그 인 정 보 는 로그 인 횟수 에 따라 QQ 번 호 를 정렬 해 야 한다.1: 먼저 QQ 번 호 를 대상 으로 hash 2: 파일 이나 메모리 데 이 터 를 순서대로 읽 고, 같은 QQ 번 호 는 로그 인 횟수 를 추가 하고, hash 값 이 같은 QQ 번 호 는 하나의 체인 에 걸 어 놓 습 니 다. 3: 파일 읽 기 가 끝 난 후, 각 hash 값 아래 의 QQ 번호 (즉 hash 값 이 같은 번호) 에 대해 로그 인 횟수 정렬 을 합 니 다. 4: 모든 hash 값 아래 의 정 보 를 정리 하고 정렬 합 니 다.
좋은 웹페이지 즐겨찾기
