如何高效实现无序数组去重并排序？现有方案存效率问题求助

Hey there! Let's work through your problem step by step—your current approach has some efficiency bottlenecks, and I'll show you how to fix them while getting the sorted, deduplicated array you need.

First, let's break down the limitations of your existing code:

• Your deduplication logic uses nested loops and shifts elements every time a duplicate is found, which runs in O(n²) time—this gets really slow as your array grows.
• You mentioned bubble sort being inefficient, which makes total sense: bubble sort is also O(n²). On top of that, your current code doesn't even include a sorting function, so that's why your two-function approach wasn't hitting your expected results.

The key to efficiency here is to sort first, then deduplicate. Using a fast sorting algorithm (like quicksort) brings the time complexity down to O(n log n), and deduplicating a sorted array is a linear O(n) operation—way better than the combined O(n²) of your original approach.

Solution 1: Use qsort + Linear Deduplication #

The C standard library includes qsort, a built-in quicksort implementation that's far more efficient than bubble sort. Once your array is sorted, duplicates will be adjacent, making deduplication trivial.

Here's the revised code:

#include <stdio.h>
#include <stdlib.h> // Required for qsort

// Comparison function for qsort (sorts in ascending order)
int compare(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

// Removes duplicates from a SORTED array, returns the new length of unique elements
int removeDuplicates(int arr[], int originalLength) {
    if (originalLength == 0) return 0;
    
    int uniqueIndex = 0; // Tracks the position of the last unique element
    for (int i = 1; i < originalLength; i++) {
        // Keep the element if it's different from the last unique one
        if (arr[i] != arr[uniqueIndex]) {
            uniqueIndex++;
            arr[uniqueIndex] = arr[i];
        }
    }
    return uniqueIndex + 1; // +1 because array indices start at 0
}

// Prints the array up to the given length
void printArray(int arr[], int length) {
    for (int i = 0; i < length; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[100];
    int n;
    
    printf("Enter n: ");
    scanf("%d", &n);
    
    printf("Enter %d elements: ", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    // Step 1: Sort the array with qsort (O(n log n) time)
    qsort(arr, n, sizeof(int), compare);
    
    // Step 2: Remove duplicates from the sorted array (O(n) time)
    int uniqueLength = removeDuplicates(arr, n);
    
    // Print the final sorted, unique array
    printf("Sorted & unique array: ");
    printArray(arr, uniqueLength);
    
    return 0;
}

Why this works better: #

• qsort efficiency: Unlike bubble sort, qsort runs in O(n log n) time. For an array of 100 elements, that's thousands of fewer operations than bubble sort would require.
• Linear deduplication: After sorting, duplicates are grouped together. We only need one pass through the array to keep track of unique elements—no nested loops or expensive element shifting.
• No global variables: I removed the global n and arr since passing parameters makes the code more modular and avoids unexpected side effects.

Solution 2: Hash Table Approach (For Small Element Ranges) #

If your array elements fall within a known, small range (e.g., 0 to 1000), you can use a hash table (or boolean array) to track seen elements. This gives you O(n) time for both deduplication and sorting, but uses extra space.

Example code:

#include <stdio.h>
#include <string.h>

void printSortedUnique(int arr[], int n) {
    // Find the maximum element to size our tracking array
    int maxVal = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > maxVal) maxVal = arr[i];
    }
    
    // Initialize array to mark which elements we've seen
    int seen[maxVal + 1];
    memset(seen, 0, sizeof(seen));
    
    // Mark elements we encounter
    for (int i = 0; i < n; i++) {
        seen[arr[i]] = 1;
    }
    
    // Print elements in order (automatically sorted!)
    printf("Sorted & unique array: ");
    for (int i = 0; i <= maxVal; i++) {
        if (seen[i]) {
            printf("%d ", i);
        }
    }
    printf("\n");
}

int main() {
    int arr[100];
    int n;
    
    printf("Enter n: ");
    scanf("%d", &n);
    
    printf("Enter %d elements: ", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    printSortedUnique(arr, n);
    
    return 0;
}

When to use this: #

• Perfect for non-negative elements with a small upper bound (like test scores, ages, or small IDs).
• Tradeoff: Uses O(maxVal) extra space, so it's not ideal if your elements can be extremely large (like 1e9).

Final Notes #

• If you were set on using bubble sort (though I don't recommend it), you'd still want to sort first before deduplicating—this would at least speed up the deduplication step. But qsort is always the better choice for performance.
• Avoid global variables where possible—they make code harder to debug and reuse.

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