데이터 구조 정렬 알고리즘 - 거품 정렬, 삽입 정렬, 힐 정렬, 쌓 기 정렬, 병합 정렬
43922 단어 알고리즘 과 데이터 구조
#include
#include
#include
using namespace std;
typedef int ElementType;
//
//N
void baboSort(ElementType A[], int N) {
for (int i = 0; i <N; i++) {
int flag = 0;
for (int j = i; j < N; j++) {
if (A[i] > A[j]) {
swap(A[i], A[j]);
flag = 1;
}
}
if (flag == 0) break; // ,
}
}
//
void InsertionSort(ElementType A[], int N){
int P, i;
ElementType Tmp;
for (P = 1; P < N; P++) {
Tmp = A[P]; /* */
for (i = P; i > 0 && A[i - 1] > Tmp; i--)
A[i] = A[i - 1]; /* */
A[i] = Tmp; /* */
}
}
/* - Sedgewick */
void ShellSort(ElementType A[], int N)
{
int Si, D, P, i;
ElementType Tmp;
/* */
int Sedgewick[] = { 929, 505, 209, 109, 41, 19, 5, 1, 0 };
//
for (Si = 0; Sedgewick[Si] >= N; Si++); /* Sedgewick[Si] */
for (D = Sedgewick[Si]; D > 0; D = Sedgewick[++Si])
for (P = D; P < N; P++) { /* */
Tmp = A[P];
for (i = P; i >= D && A[i - D] > Tmp; i -= D)
A[i] = A[i - D];
A[i] = Tmp;
}
}
void Swap(ElementType* a, ElementType* b)
{
ElementType t = *a; *a = *b; *b = t;
}
void PercDown(ElementType A[], int p, int N)
{ /* 4.24 PercDown( MaxHeap H, int p ) */
/* N A[p] */
int Parent, Child;
ElementType X;
X = A[p]; /* */
for (Parent = p; (Parent * 2 + 1) < N; Parent = Child) {
Child = Parent * 2 + 1;
if ((Child != N - 1) && (A[Child] < A[Child + 1]))
Child++; /* Child */
if (X >= A[Child]) break; /* */
else /* X */
A[Parent] = A[Child];
}
A[Parent] = X;
}
void HeapSort(ElementType A[], int N)
{ /* */
int i;
for (i = N / 2 - 1; i >= 0; i--)/* */
PercDown(A, i, N);
for (i = N - 1; i > 0; i--) {
/* */
Swap(&A[0], &A[i]); /* 7.1 */
PercDown(A, 0, i);
}
}
/* - */
/* L = , R = , RightEnd = */
void Merge(ElementType A[], ElementType TmpA[], int L, int R, int RightEnd)
{ /* A[L]~A[R-1] A[R]~A[RightEnd] */
int LeftEnd, NumElements, Tmp;
int i;
LeftEnd = R - 1; /* */
Tmp = L; /* */
NumElements = RightEnd - L + 1;
while (L <= LeftEnd && R <= RightEnd) {
if (A[L] <= A[R])
TmpA[Tmp++] = A[L++]; /* TmpA */
else
TmpA[Tmp++] = A[R++]; /* TmpA */
}
while (L <= LeftEnd)
TmpA[Tmp++] = A[L++]; /* */
while (R <= RightEnd)
TmpA[Tmp++] = A[R++]; /* */
for (i = 0; i < NumElements; i++, RightEnd--)
A[RightEnd] = TmpA[RightEnd]; /* TmpA[] A[] */
}
void Msort(ElementType A[], ElementType TmpA[], int L, int RightEnd)
{ /* */
int Center;
if (L < RightEnd) {
Center = (L + RightEnd) / 2;
Msort(A, TmpA, L, Center); /* */
Msort(A, TmpA, Center + 1, RightEnd); /* */
Merge(A, TmpA, L, Center + 1, RightEnd); /* */
}
}
void MergeSort(ElementType A[], int N)
{ /* */
ElementType* TmpA;
TmpA = (ElementType*)malloc(N * sizeof(ElementType));
if (TmpA != NULL) {
Msort(A, TmpA, 0, N - 1);
free(TmpA);
}
else printf(" ");
}
/* - */
/* Merge */
/* length = */
void Merge_pass(ElementType A[], ElementType TmpA[], int N, int length)
{ /* */
int i, j;
for (i = 0; i <= N - 2 * length; i += 2 * length)
Merge(A, TmpA, i, i + length, i + 2 * length - 1);
if (i + length < N) /* 2 */
Merge(A, TmpA, i, i + length, N - 1);
else /* 1 */
for (j = i; j < N; j++) TmpA[j] = A[j];
}
void Merge_Sort(ElementType A[], int N)
{
int length;
ElementType* TmpA;
length = 1; /* */
TmpA =(ElementType*) malloc(N * sizeof(ElementType));
if (TmpA != NULL) {
while (length < N) {
Merge_pass(A, TmpA, N, length);
length *= 2;
Merge_pass(TmpA, A, N, length);
length *= 2;
}
free(TmpA);
}
else printf("Space is not enough");
}
int main() {
int N=5;
ElementType A[100]={10,8,5,9,2};
/*
cout<>N;
for(int i=0;i>A[i];
}
*/
cout<<" :"<<endl;
baboSort(A,N);
for(int i=0;i<N;i++){
cout<<A[i]<<' ';
}
cout<<endl;
cout<<" :"<<endl;
InsertionSort(A,N);
for(int i=0;i<N;i++){
cout<<A[i]<<' ';
}
cout<<endl;
cout<<" :"<<endl;
ShellSort(A,N);
for(int i=0;i<N;i++){
cout<<A[i]<<' ';
}
cout<<endl;
cout<<" :"<<endl;
HeapSort(A,N);
for(int i=0;i<N;i++){
cout<<A[i]<<' ';
}
cout<<endl;
cout<<" :"<<endl;
MergeSort(A,N);
for(int i=0;i<N;i++){
cout<<A[i]<<' ';
}
cout<<endl;
cout<<" :"<<endl;
Merge_Sort(A,N);
for(int i=0;i<N;i++){
cout<<A[i]<<' ';
}
cout<<endl;
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
데이터 구조의 링크 의 실현글 목록 소개 실현 1. 프로필 동적 배열, 스 택 과 대열 의 바 텀 은 모두 정적 배열 에 의존 하고 resize 로 고정 용량 문 제 를 해결한다.그리고 링크 는 진정한 동적 데이터 구조 이다 2. 실현...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.