排序算法是计算机科学中最基础也是最重要的内容之一。不同的排序算法各有特点，适用于不同的场景。今天我们就来聊聊十种经典排序算法，并用MATLAB来实现它们。

1. 冒泡排序（Bubble Sort）

算法思想：重复遍历要排序的数列，一次比较两个元素，如果顺序错误就交换它们。

function arr = bubbleSort(arr)
    n = length(arr);
    for i = 1:n-1
        for j = 1:n-i
            if arr(j) > arr(j+1)
                % 交换元素
                temp = arr(j);
                arr(j) = arr(j+1);
                arr(j+1) = temp;
            end
        end
    end
end

2. 选择排序（Selection Sort）

算法思想：每次从未排序部分选择最小（或最大）元素，放到已排序部分的末尾。

function arr = selectionSort(arr)
    n = length(arr);
    for i = 1:n-1
        min_idx = i;
        for j = i+1:n
            if arr(j) < arr(min_idx)
                min_idx = j;
            end
        end
        % 交换元素
        temp = arr(i);
        arr(i) = arr(min_idx);
        arr(min_idx) = temp;
    end
end

3. 插入排序（Insertion Sort）

算法思想：构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

function arr = insertionSort(arr)
    n = length(arr);
    for i = 2:n
        key = arr(i);
        j = i - 1;
        while j >= 1 && arr(j) > key
            arr(j+1) = arr(j);
            j = j - 1;
        end
        arr(j+1) = key;
    end
end

4. 希尔排序（Shell Sort）

算法思想：是插入排序的改进版，通过将原始数组分解为多个子序列来改进插入排序。

function arr = shellSort(arr)
    n = length(arr);
    gap = floor(n/2);
    while gap > 0
        for i = gap+1:n
            temp = arr(i);
            j = i;
            while j > gap && arr(j-gap) > temp
                arr(j) = arr(j-gap);
                j = j - gap;
            end
            arr(j) = temp;
        end
        gap = floor(gap/2);
    end
end

5. 归并排序（Merge Sort）

算法思想：采用分治法，将数组分成两半，分别排序，然后合并。

function arr = mergeSort(arr)
    if length(arr) <= 1
        return;
    end
    
    % 分割数组
    mid = floor(length(arr)/2);
    left = mergeSort(arr(1:mid));
    right = mergeSort(arr(mid+1:end));
    
    % 合并
    arr = merge(left, right);
end

function merged = merge(left, right)
    merged = [];
    i = 1; j = 1;
    
    while i <= length(left) && j <= length(right)
        if left(i) <= right(j)
            merged = [merged, left(i)];
            i = i + 1;
        else
            merged = [merged, right(j)];
            j = j + 1;
        end
    end
    
    % 添加剩余元素
    if i <= length(left)
        merged = [merged, left(i:end)];
    end
    if j <= length(right)
        merged = [merged, right(j:end)];
    end
end

6. 快速排序（Quick Sort）

算法思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小。

function arr = quickSort(arr)
    if length(arr) <= 1
        return;
    end
    
    pivot = arr(1);
    less = [];
    equal = [];
    greater = [];
    
    for i = 1:length(arr)
        if arr(i) < pivot
            less = [less, arr(i)];
        elseif arr(i) == pivot
            equal = [equal, arr(i)];
        else
            greater = [greater, arr(i)];
        end
    end
    
    arr = [quickSort(less), equal, quickSort(greater)];
end

7. 堆排序（Heap Sort）

算法思想：利用堆这种数据结构所设计的一种排序算法。

function arr = heapSort(arr)
    n = length(arr);
    
    % 构建最大堆
    for i = floor(n/2):-1:1
        arr = heapify(arr, n, i);
    end
    
    % 一个个从堆顶取出元素
    for i = n:-1:2
        % 交换
        temp = arr(1);
        arr(1) = arr(i);
        arr(i) = temp;
        
        % 维护堆性质
        arr = heapify(arr, i-1, 1);
    end
end

function arr = heapify(arr, n, i)
    largest = i;
    left = 2*i;
    right = 2*i + 1;
    
    if left <= n && arr(left) > arr(largest)
        largest = left;
    end
    
    if right <= n && arr(right) > arr(largest)
        largest = right;
    end
    
    if largest ~= i
        temp = arr(i);
        arr(i) = arr(largest);
        arr(largest) = temp;
        
        arr = heapify(arr, n, largest);
    end
end

8. 计数排序（Counting Sort）

算法思想：使用一个额外的数组，其中第i个元素是待排序数组中值等于i的元素的个数。

function arr = countingSort(arr)
    if isempty(arr)
        return;
    end
    
    max_val = max(arr);
    min_val = min(arr);
    
    count = zeros(1, max_val - min_val + 1);
    
    % 计数
    for i = 1:length(arr)
        count(arr(i) - min_val + 1) = count(arr(i) - min_val + 1) + 1;
    end
    
    % 重建数组
    idx = 1;
    for i = 1:length(count)
        for j = 1:count(i)
            arr(idx) = min_val + i - 1;
            idx = idx + 1;
        end
    end
end

9. 桶排序（Bucket Sort）

算法思想：将数组分到有限数量的桶里，每个桶再个别排序。

function arr = bucketSort(arr)
    if length(arr) <= 1
        return;
    end
    
    max_val = max(arr);
    min_val = min(arr);
    
    % 创建桶
    bucket_size = 10;
    bucket_count = floor((max_val - min_val) / bucket_size) + 1;
    buckets = cell(1, bucket_count);
    
    % 分配元素到桶中
    for i = 1:length(arr)
        bucket_idx = floor((arr(i) - min_val) / bucket_size) + 1;
        buckets{bucket_idx} = [buckets{bucket_idx}, arr(i)];
    end
    
    % 对每个桶排序并合并
    arr = [];
    for i = 1:bucket_count
        if ~isempty(buckets{i})
            buckets{i} = insertionSort(buckets{i});
            arr = [arr, buckets{i}];
        end
    end
end

10. 基数排序（Radix Sort）

算法思想：按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。

function arr = radixSort(arr)
    if isempty(arr)
        return;
    end
    
    max_val = max(arr);
    exp = 1;
    
    while floor(max_val/exp) > 0
        arr = countingSortForRadix(arr, exp);
        exp = exp * 10;
    end
end

function arr = countingSortForRadix(arr, exp)
    n = length(arr);
    output = zeros(1, n);
    count = zeros(1, 10);
    
    % 计数
    for i = 1:n
        index = mod(floor(arr(i)/exp), 10) + 1;
        count(index) = count(index) + 1;
    end
    
    % 累加计数
    for i = 2:10
        count(i) = count(i) + count(i-1);
    end
    
    % 构建输出数组
    for i = n:-1:1
        index = mod(floor(arr(i)/exp), 10) + 1;
        output(count(index)) = arr(i);
        count(index) = count(index) - 1;
    end
    
    arr = output;
end

测试与可视化

% 生成测试数据
rng(1); % 设置随机种子保证结果可重复
test_data = randi([1, 100], 1, 20);

fprintf('原始数据:\n');
disp(test_data);

% 定义排序算法名称和函数句柄
algorithms = {
    {'冒泡排序', @bubbleSort},
    {'选择排序', @selectionSort},
    {'插入排序', @insertionSort},
    {'希尔排序', @shellSort},
    {'归并排序', @mergeSort},
    {'快速排序', @quickSort},
    {'堆排序', @heapSort},
    {'计数排序', @countingSort},
    {'桶排序', @bucketSort},
    {'基数排序', @radixSort}
};

% 创建图形窗口
figure('Position', [100, 100, 1200, 800]);

% 测试每个算法
for i = 1:length(algorithms)
    name = algorithms{i}{1};
    func = algorithms{i}{2};
    
    % 复制测试数据（避免原地修改）
    data_to_sort = test_data;
    
    % 计时并排序
    tic;
    sorted_data = func(data_to_sort);
    time_taken = toc;
    
    % 显示结果
    fprintf('%s - 耗时: %.6f秒\n', name, time_taken);
    
    % 绘制结果
    subplot(4, 3, i);
    
    % 绘制原始数据和排序后数据的对比
    hold on;
    bar(1:length(test_data), test_data, 'FaceColor', [0.7 0.7 0.7], 'EdgeColor', 'none');
    bar(1:length(sorted_data), sorted_data, 'FaceColor', [0.2 0.6 0.8], 'EdgeColor', 'none', 'FaceAlpha', 0.7);
    hold off;
    
    title(sprintf('%s\n%.6f秒', name, time_taken));
    xlabel('索引');
    ylabel('值');
    legend('原始数据', '排序后', 'Location', 'northeast');
    grid on;
end

% 添加总标题
sgtitle('十大经典排序算法比较', 'FontSize', 16, 'FontWeight', 'bold');

fprintf('\n所有排序算法测试完成！\n');

算法复杂度比较