귀속을 사용하지 않고 귀속 정렬을 실현하다
직접 인접 2개, 4개, 8개...정렬, 마지막 마무리 어떻게 하는지 주의해야 한다
#include<stdlib.h>
#include<stdio.h>
#include"fatal.h"
int RandInt(int i, int j) {
int temp;
temp = (int)(i + (1.0*rand() / RAND_MAX)*(j - i));
return temp;
}
void getRandomInt(int *A, int n) {
for (int i = 0; i < n; i++) {
A[i] = i + 1;
}
for (int i = 1; i < n; i++) {
//std::swap(A[i], A[RandInt(0, i)]);
int randAdrr = RandInt(0, i);
int t = A[i];
A[i] = A[randAdrr];
A[randAdrr] = t;
}
}
int a[99999999];
void merge(int a[], int tempArray[], int left, int right, int rightEnd) {
int i, j, k;
int leftEnd;
for (i = left, j = right, k = left, leftEnd = right - 1; i <= leftEnd && j <= rightEnd; k++) {
if (a[i] < a[j]) {
tempArray[k] = a[i];
i++;
}
else {
tempArray[k] = a[j];
j++;
}
}
while (i <= leftEnd) {
tempArray[k++] = a[i++];
}
while (j <= rightEnd) {
tempArray[k++] = a[j++];
}
for (int i = left; i <= rightEnd; i++)
a[i] = tempArray[i];
}
void mSort(int a[], int tempArray[], int left, int right) {
if (left < right) {
int center = (left + right) / 2;
mSort(a, tempArray, left, center);
mSort(a, tempArray, center + 1, right);
merge(a, tempArray, left, center + 1, right);
}
}
void mergeSort(int a[], int n) {
int *tempArray = malloc(sizeof(int)*n);
if (tempArray == NULL)
Error("OUT OF MEMORY");
//mSort(a, tempArray, 0, n - 1);
for (int len = 1; len < n; len *= 2) {
for (int beg_pos = 0; beg_pos < n; beg_pos += (2 * len)) {
{
int i, j, k;
int leftEnd, rightEnd;
for (i = beg_pos, j = beg_pos + len, k = beg_pos, leftEnd = min(j - 1, n - 1), rightEnd = min(j + len - 1, n - 1); i <= leftEnd && j <= rightEnd; k++) {
if (a[i] < a[j]) {
tempArray[k] = a[i];
i++;
}
else {
tempArray[k] = a[j];
j++;
}
}
while (i <= leftEnd) {
tempArray[k++] = a[i++];
}
while (j <= rightEnd) {
tempArray[k++] = a[j++];
}
for (int i = beg_pos; i <= rightEnd; i++)
a[i] = tempArray[i];
}
}
}
free(tempArray);
}
#define N 2222
int main() {
getRandomInt(a, N);
mergeSort(a, N);
int cnt = 1;
for (int i = 0; i < N; i++)
if (cnt == a[i])
cnt++;
else
Error("error");
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.