Windows平台下8线程C语言排序100万随机整数技术问询

Hey there! You’ve already knocked out the foundational parts of your multi-threaded sorting task on Windows with C—generating the binary file, loading the array, and spinning up 8 threads. Nice work! Let’s walk through the remaining steps to get this sorted (pun intended).

First, each thread needs to know which slice of the array to process. We’ll create a struct to pass thread-specific data, since Windows’ thread entry function only accepts a single LPVOID parameter:

typedef struct {
    int* start_ptr;  // Starting address of the subarray
    int element_count; // Number of elements to sort in this chunk
} ThreadSortData;

Thread Entry Function #

For sorting, you can use the standard library’s qsort (fast, good for random data) or implement your own merge sort. Here’s a thread function that uses qsort:

// Helper comparison function for qsort
int compareInts(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

// Thread entry point
DWORD WINAPI SortChunk(LPVOID param) {
    ThreadSortData* data = (ThreadSortData*)param;
    qsort(data->start_ptr, data->element_count, sizeof(int), compareInts);
    return 0;
}

When creating threads, assign each a chunk of the array. Since 1,000,000 is evenly divisible by 8, each chunk will have 125,000 elements:

HANDLE thread_handles[8];
ThreadSortData thread_data[8];
int* int_array = /* Your loaded array here */;
const int chunk_size = 1000000 / 8;

for (int i = 0; i < 8; i++) {
    thread_data[i].start_ptr = int_array + (i * chunk_size);
    thread_data[i].element_count = chunk_size;
    thread_handles[i] = CreateThread(
        NULL, 0, SortChunk, &thread_data[i], 0, NULL
    );
    if (thread_handles[i] == NULL) {
        // Handle thread creation failure (e.g., log error, clean up)
        fprintf(stderr, "Failed to create thread %d\n", i);
        exit(1);
    }
}

Before merging, we need to ensure every chunk is fully sorted. Use WaitForMultipleObjects to block until all threads complete:

// Wait for all 8 threads to finish (INFINITE = wait indefinitely)
WaitForMultipleObjects(8, thread_handles, TRUE, INFINITE);

// Clean up thread handles
for (int i = 0; i < 8; i++) {
    CloseHandle(thread_handles[i]);
}

Once all subarrays are sorted, we need to combine them into one fully ordered array. Two reliable methods are below:

Method 1: Pairwise Step-by-Step Merge #

This is the simplest to implement—merge chunks two at a time until only one remains. First, write a helper to merge two sorted arrays:

void mergeTwoSortedArrays(int* dest, const int* arr1, int len1, const int* arr2, int len2) {
    int i = 0, j = 0, k = 0;
    while (i < len1 && j < len2) {
        dest[k++] = (arr1[i] <= arr2[j]) ? arr1[i++] : arr2[j++];
    }
    // Copy remaining elements from either array
    while (i < len1) dest[k++] = arr1[i++];
    while (j < len2) dest[k++] = arr2[j++];
}

Then perform the sequential merges:

int* temp_array = malloc(1000000 * sizeof(int));
if (!temp_array) {
    fprintf(stderr, "Memory allocation failed for temp array\n");
    exit(1);
}

int* src = int_array;
int* dest = temp_array;
int current_merge_size = chunk_size;

// Merge 8 chunks down to 1
for (int i = 1; i < 8; i++) {
    mergeTwoSortedArrays(
        dest, src, current_merge_size * i,
        int_array + current_merge_size * i, chunk_size
    );
    // Swap src/dest pointers to avoid overwriting data
    int* swap = src;
    src = dest;
    dest = swap;
}

// If final result is in temp_array, copy back to original
if (src == temp_array) {
    memcpy(int_array, temp_array, 1000000 * sizeof(int));
}
free(temp_array);

Method 2: Min-Heap Multi-Way Merge #

For better efficiency (especially with more chunks), use a min-heap to track the smallest available element across all chunks. Here’s a simplified implementation:

First, define a heap node structure and heap helper functions:

typedef struct {
    int value;
    int chunk_index; // Which subarray this element comes from
    int element_index; // Position within the subarray
} HeapNode;

// Maintain min-heap property
void heapify(HeapNode heap[], int heap_size, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;

    if (left < heap_size && heap[left].value < heap[smallest].value)
        smallest = left;
    if (right < heap_size && heap[right].value < heap[smallest].value)
        smallest = right;

    if (smallest != idx) {
        HeapNode temp = heap[idx];
        heap[idx] = heap[smallest];
        heap[smallest] = temp;
        heapify(heap, heap_size, smallest);
    }
}

// Build initial min-heap
void buildMinHeap(HeapNode heap[], int size) {
    for (int i = size / 2 - 1; i >= 0; i--)
        heapify(heap, size, i);
}

Then perform the multi-way merge:

int* final_result = malloc(1000000 * sizeof(int));
if (!final_result) {
    fprintf(stderr, "Memory allocation failed for result array\n");
    exit(1);
}

HeapNode heap[8];
int result_idx = 0;
int heap_size = 8;

// Initialize heap with first element of each chunk
for (int i = 0; i < 8; i++) {
    heap[i].value = int_array[i * chunk_size];
    heap[i].chunk_index = i;
    heap[i].element_index = 0;
}
buildMinHeap(heap, heap_size);

while (result_idx < 1000000) {
    // Extract smallest element from heap
    HeapNode min_node = heap[0];
    final_result[result_idx++] = min_node.value;

    // Get next element from the same chunk (if available)
    int next_elem_idx = min_node.element_index + 1;
    if (next_elem_idx < chunk_size) {
        heap[0].value = int_array[min_node.chunk_index * chunk_size + next_elem_idx];
        heap[0].element_index = next_elem_idx;
        heapify(heap, heap_size, 0);
    } else {
        // Chunk is exhausted: replace heap top with last element, shrink heap size
        heap[0] = heap[heap_size - 1];
        heap_size--;
        heapify(heap, heap_size, 0);
    }
}

// Copy result back to original array if needed
memcpy(int_array, final_result, 1000000 * sizeof(int));
free(final_result);

• Thread Safety: Since each thread operates on a non-overlapping subarray, there’s no data race—no need for mutexes here.
• Error Handling: Always check return values for CreateThread, malloc, and other system calls to avoid silent failures.
• Sort Choice: qsort is fast for random data, but merge sort is stable (preserves order of equal elements) if you need that property.
• Edge Cases: If your array size wasn’t evenly divisible by 8, adjust the last chunk’s element count to account for the remainder.

内容的提问来源于stack exchange，提问作者xBaskerville