程序中摇排序（Shaker Sort）耗时超冒泡排序，求排查逻辑错误

Hey there! Let's dig into why your Shaker Sort is taking longer than your optimized Bubble Sort v2—this is a common gotcha with bidirectional sorts, so let's break it down step by step.

First, Your Provided Bubble Sort v2 Code #

public void bubble_sort_v2()// storing info where changes made 
{ 
    int handler_1; 
    bool swaped = false; 
    Console.WriteLine("\n Bubble Sorting v2 Algorithm \n"); 
    for (int lota = 0; lota < length_of_the_array.Length; lota++) 
    { 
        array_length = length_of_the_array[lota]; 
        algorithm = new int[array_length]; 
        Randomize_array(algorithm); 
        Stopwatch t...

Common Reasons Shaker Sort Might Be Underperforming #

1. Missing Boundary Optimization #

Your Bubble Sort v2 comment mentions "storing info where changes made"—I assume this means you're tracking the last index where a swap occurred, so each pass only runs up to that point (cutting out redundant checks on already sorted elements). If your Shaker Sort implementation doesn't do the same for both left-to-right and right-to-left passes, it's wasting cycles re-checking elements that are already in place. For example, if you don't shrink the right boundary after a left-to-right pass or the left boundary after a right-to-left pass, you'll end up comparing far more elements than necessary.

2. No Early Termination Check #

Optimized Bubble Sort stops early once a full pass completes with no swaps (since the array is sorted). If your Shaker Sort doesn't include this check for both directions, it might keep running unnecessary bidirectional passes even when the array is already fully sorted, adding extra overhead.

3. Inconsistent Test Conditions #

From your code snippet, it looks like you're generating random arrays for each test run. If you're not using a fixed random seed or testing the exact same array for both algorithms, runtime differences could just be due to array order (not the algorithm itself). Small arrays are especially prone to noisy timing results from randomness, so you should average runtimes over multiple tests with identical input arrays.

4. Buggy Shaker Sort Implementation #

Common bugs in Shaker Sort that cause slowdowns include:

• Forgetting to toggle the pass direction (left-to-right vs right-to-left) each iteration
• Incorrectly updating the left/right boundaries after each pass
• Running extra unnecessary passes (e.g., not stopping when no swaps occur in either direction)

What You Need to Share to Fix This #

To pinpoint the exact issue, please provide:

• The full implementation of your Shaker Sort code
• The complete Bubble Sort v2 code (including the full Stopwatch timing logic)
• Details about your test setup: array sizes you're using, whether you're testing with identical arrays for both algorithms, and how you're calculating average runtimes

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