資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究帶 C++ 示例的外排序
外部排序是一種分類排序演算法，能夠對海量資料進行排序。此類排序應用於需要佔用超大記憶體且無法儲存在主記憶體（RAM）中並存儲在輔助記憶體（硬碟）中的資料集。
外部排序中使用的排序理念與歸併排序類似。它也像歸併排序一樣具有兩個階段，
在排序階段，對小記憶體大小資料集進行排序，然後在合併階段，將這些合併成一個數據集。
外部排序
對於無法一次處理的大型資料集，將資料分成小塊。對這些小塊進行排序，然後儲存在資料檔案中。
演算法：
步驟 1：從檔案中讀取輸入資料並將其輸入為記憶體大小的資料集。
步驟 2：對每個小資料集使用歸併排序對其進行排序。
步驟 3：將排序後的資料儲存到一個檔案中。
步驟 4：合併每個排序後的資料檔案。
演示演算法工作原理的程式：
示例
#include <bits/stdc++.h>
using namespace std;
struct MinHeapNode {
int element;
int i;
};
void swap(MinHeapNode* x, MinHeapNode* y);
class MinHeap {
MinHeapNode* harr;
int heap_size;
public:
MinHeap(MinHeapNode a[], int size);
void MinHeapify(int);
int left(int i) {
return (2 * i + 1);
}
int right(int i) {
return (2 * i + 2);
}
MinHeapNode getMin() {
return harr[0];
}
void replaceMin(MinHeapNode x) {
harr[0] = x;
MinHeapify(0);
}
};
MinHeap::MinHeap(MinHeapNode a[], int size) {
heap_size = size;
harr = a;
int i = (heap_size - 1) / 2;
while (i >= 0) {
MinHeapify(i);
i--;
}
}
void MinHeap::MinHeapify(int i) {
int l = left(i);
int r = right(i);
int smallest = i;
if (l < heap_size && harr[l].element < harr[i].element)
smallest = l;
if (r < heap_size && harr[r].element < harr[smallest].element)
smallest = r;
if (smallest != i) {
swap(&harr[i], &harr[smallest]);
MinHeapify(smallest);
}
}
void swap(MinHeapNode* x, MinHeapNode* y)
{
MinHeapNode temp = *x;
*x = *y;
*y = temp;
}
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j])
arr[k++] = L[i++];
else
arr[k++] = R[j++];
}
while (i < n1)
arr[k++] = L[i++];
while (j < n2)
arr[k++] = R[j++];
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
FILE* openFile(char* fileName, char* mode)
{
FILE* fp = fopen(fileName, mode);
if (fp == NULL) {
perror("Error while opening the file.\n");
exit(EXIT_FAILURE);
}
return fp;
}
void mergeData(char* opFile, int n, int k) {
FILE* in[k];
for (int i = 0; i < k; i++) {
char fileName[2];
snprintf(fileName, sizeof(fileName), "%d", i);
in[i] = openFile(fileName, "r");
}
FILE* out = openFile(opFile, "w");
MinHeapNode* harr = new MinHeapNode[k];
int i;
for (i = 0; i < k; i++) {
if (fscanf(in[i], "%d ", &harr[i].element) != 1)
break;
harr[i].i = i;
}
MinHeap hp(harr, i);
int count = 0;
while (count != i) {
MinHeapNode root = hp.getMin();
fprintf(out, "%d ", root.element);
if (fscanf(in[root.i], "%d ",
&root.element)
!= 1) {
root.element = INT_MAX;
count++;
}
hp.replaceMin(root);
}
for (int i = 0; i < k; i++)
fclose(in[i]);
fclose(out);
}
void initialiseData( char* ipFile, int memory, int num_ways) {
FILE* in = openFile(ipFile, "r");
FILE* out[num_ways];
char fileName[2];
for (int i = 0; i < num_ways; i++) {
snprintf(fileName, sizeof(fileName), "%d", i);
out[i] = openFile(fileName, "w");
}
int* arr = (int*)malloc( memory * sizeof(int));
bool more_input = true;
int next_opFile = 0;
int i;
while (more_input) {
for (i = 0; i < memory; i++) {
if (fscanf(in, "%d ", &arr[i]) != 1) {
more_input = false;
break;
}
}
mergeSort(arr, 0, i - 1);
for (int j = 0; j < i; j++)
fprintf(out[next_opFile], "%d ", arr[j]);
next_opFile++;
}
for (int i = 0; i < num_ways; i++)
fclose(out[i]);
fclose(in);
}
void externalSort( char* ipFile, char* opFile, int num_ways, int memory) {
initialiseData(ipFile, memory, num_ways);
mergeData(opFile, memory, num_ways);
}
int main() {
int num_ways = 10;
int memory = 1000;
char ipFile[] = "inputFile.txt";
char opFile[] = "outputFile.txt";
FILE* in = openFile(ipFile, "w");
srand(time(NULL));
for (int i = 0; i < num_ways * memory; i++)
fprintf(in, "%d ", rand());
fclose(in);
externalSort(ipFile, opFile, num_ways, memory);
return 0;
}輸入資料是一個無序資料檔案，而輸出將是排序後的陣列。
更新時間：2021 年 1 月 22 日
2K+ 瀏覽量
廣告