如何实现ListViewItems列表排序？快速排序是否适用于数千条数据场景？

Is Quicksort the Right Choice? #

Absolutely. For datasets of a few thousand items, quicksort’s average O(n log n) time complexity is way more efficient than O(n²) algorithms like bubble or insertion sort. Since Virtual List Views work by rendering only visible items (pulling from a backend data source), you won’t be sorting UI elements directly—just your underlying List<ListViewItem> (listOfLVI), which keeps the process fast and avoids UI lag.

The only caveat is quicksort’s worst-case O(n²) performance, but that’s easily mitigated by randomizing your pivot selection (more on that below). Unless your data is already perfectly sorted (in either direction) and you pick a bad pivot, you’ll never hit that worst case in practice.

Key Implementation Tips #

Here’s what to keep in mind to make this smooth:

• Sort the data source, not the UI: Virtual List Views don’t store all items in memory—your listOfLVI is the single source of truth. Sort this collection first, then tell the ListView to refresh its virtual size and redraw.
• Pick a random pivot: Avoid selecting the first/last element as your pivot. Instead, pick a random index, swap it with the first element, then proceed with partitioning. This eliminates the worst-case scenario for sorted data.
• Optimize comparison logic: Extract your sort key (e.g., a subitem’s text or numeric value) once per item, and handle edge cases like empty values or mixed data types (strings vs numbers) gracefully.
• Offload to a background thread: Even with thousands of items, sorting might block the UI for a split second. Wrap the sort in a Task.Run() to keep your app responsive, then refresh the ListView on the UI thread.
• Handle nulls/special cases: Add checks for empty subitems or non-numeric values if you’re sorting numerically—don’t let bad data crash your sort.

Code Example (C# WinForms) #

Let’s put this into practice with a complete implementation. First, we’ll create a comparison method, then the quicksort logic, and finally hook it up to a ColumnClick event for user-driven sorting.

1. Comparison Logic #

This method compares two ListViewItems based on a specified column, supporting both string and numeric sorting:

private int CompareListViewItems(ListViewItem item1, ListViewItem item2, int sortColumn, bool ascending)
{
    string text1 = item1.SubItems[sortColumn].Text;
    string text2 = item2.SubItems[sortColumn].Text;

    // Try numeric sorting first if possible
    if (double.TryParse(text1, out double num1) && double.TryParse(text2, out double num2))
    {
        return ascending ? num1.CompareTo(num2) : num2.CompareTo(num1);
    }
    // Fall back to case-insensitive string sorting
    else
    {
        return ascending 
            ? string.Compare(text1, text2, StringComparison.OrdinalIgnoreCase) 
            : string.Compare(text2, text1, StringComparison.OrdinalIgnoreCase);
    }
}

2. Quicksort Implementation #

Recursive quicksort with random pivot selection to avoid worst-case performance:

private void QuickSortListViewItems(List<ListViewItem> items, int left, int right, int sortColumn, bool ascending)
{
    if (left >= right) return;

    // Randomize pivot to avoid worst-case sorted data
    Random rand = new Random();
    int pivotIndex = rand.Next(left, right + 1);
    // Swap pivot with first element
    (items[left], items[pivotIndex]) = (items[pivotIndex], items[left]);
    ListViewItem pivot = items[left];

    int i = left + 1;
    int j = right;

    while (i <= j)
    {
        // Find first item >= pivot (ascending)
        while (i <= j && CompareListViewItems(items[i], pivot, sortColumn, ascending) < 0)
        {
            i++;
        }
        // Find first item <= pivot (ascending)
        while (i <= j && CompareListViewItems(items[j], pivot, sortColumn, ascending) > 0)
        {
            j--;
        }
        if (i <= j)
        {
            // Swap elements
            (items[i], items[j]) = (items[j], items[i]);
            i++;
            j--;
        }
    }
    // Place pivot in its correct position
    (items[left], items[j]) = (items[j], items[left]);

    // Recursively sort left and right partitions
    QuickSortListViewItems(items, left, j - 1, sortColumn, ascending);
    QuickSortListViewItems(items, j + 1, right, sortColumn, ascending);
}

3. Hook Up to Column Click #

Let users sort by clicking column headers, with background sorting to keep UI responsive:

private void listView_ColumnClick(object sender, ColumnClickEventArgs e)
{
    // Toggle sort direction if clicking the same column
    bool ascending = true;
    if (listView.Sorting == SortOrder.Ascending && listView.SortedColumn == e.Column)
    {
        ascending = false;
        listView.Sorting = SortOrder.Descending;
    }
    else
    {
        listView.Sorting = SortOrder.Ascending;
        listView.SortedColumn = e.Column;
    }

    // Run sort in background to avoid UI freeze
    Task.Run(() =>
    {
        QuickSortListViewItems(listOfLVI, 0, listOfLVI.Count - 1, e.Column, ascending);

        // Refresh ListView on UI thread
        this.Invoke((MethodInvoker)delegate
        {
            listView.VirtualListSize = listOfLVI.Count;
            listView.Refresh();
        });
    });
}

4. Virtual Item Retrieval #

Don’t forget the RetrieveVirtualItem event to feed sorted data to the ListView:

private void listView_RetrieveVirtualItem(object sender, RetrieveVirtualItemEventArgs e)
{
    if (e.ItemIndex >= 0 && e.ItemIndex < listOfLVI.Count)
    {
        e.Item = listOfLVI[e.ItemIndex];
    }
}

Final Notes #

• If you’re working with extremely large datasets (100k+ items), you might consider merge sort for its stability, but for thousands of items, quicksort is more than sufficient.
• Test edge cases: empty lists, all identical items, mixed data types, and null subitems to ensure your sort logic holds up.
• Make sure your ListView is configured for virtual mode (listView.VirtualMode = true) before using this code.

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