visuAlgo-排序算法

不念不忘少年蓝@ 2022-11-20 02:00 196阅读 0赞

# 前言 #

[visuAlgo][]是个算法相关的网站，里面有很多算法的演示动画，可以方便理解算法的流程，下面看看经典的排序算法。本文用mathematica（`索引从1开始`）代码来演示这些算法。

# 冒泡 #

每次在`未排序部分`中比较相邻两个元素，并把较大的元素放在右边，一趟循环过后，最大的元素放在最右边；所有循环结束后，所有的元素都已经排序。

ClearAll[bubble];
    bubble[list_Symbol] := Module[
       { i, j, temp},
       For[i = Length[list], i >= 2, i--,
        For[j = 1, j < i, j++,
         If[list[[j]] > list[[j + 1]],
          temp = list[[j]];
          list[[j]] = list[[j + 1]];
          list[[j + 1]] = temp;
          ]
         ];
        Print[list];
        ];
       list
       ];
    SetAttributes[bubble, HoldAll];

其中，`i`表示`未排序部分`的最大索引，最小值是`2`，最大值是`整个列表的最后一个索引`；`j`表示`未排序部分`中`除最后一个索引`的其余索引，最小值是`1`，最大值是`i-1`；`temp`表示临时赋值变量，用于交换相邻两个数据。

# 选择 #

每趟循环，找出`未排序部分`的`最小值`的索引，并把`最小值`和`未排序部分`的`第一个值`交换位置；所有循环结束后，所有的元素都排序。

ClearAll[select];
    select[list_Symbol] := Module[
       { i, j, minIndex, temp},
       For[i = 1, i < Length[list], i++,
        minIndex = i;
        For[j = i + 1, j <= Length[list], j++,
         If[list[[j]] < list[[minIndex]], minIndex = j]
         ];
        temp = list[[i]];
        list[[i]] = list[[minIndex]];
        list[[minIndex]] = temp;
        Print[list];
        ];
       list
       ];
    SetAttributes[select, HoldAll];

其中，`i`表示`未排序部分`的第一个索引，最小值是`整个列表`第一个索引，最大值是整个列表`倒数第二个索引`；`j`表示`未排序部分`中`除第一个索引以外`的其余索引，最小值是`i+1`，最大值是`整个列表的最后一个索引`；`minIndex`表示每次循环`未排序部分`的最小值索引；`temp`是临时变量，用于交换`未排序部分`第一个值和最小值。

# 插入 #

每趟循环从`未排序部分`中取出`第一个`，从后往前逐一与`排序部分`的元素比较，如果比前面的元素小，就和这个较小的元素交换位置，直到没有比它小的元素为止。

ClearAll[insert];
    insert[list_Symbol] := Module[
       { i, j, temp},
       For[i = 2, i <= Length[list], i++,
        For[j = i - 1, j >= 1, j--,
         If[list[[j + 1]] < list[[j]],
           temp = list[[j + 1]];
           list[[j + 1]] = list[[j]];
           list[[j]] = temp;
           ];
         ];
        
        Print[list];
        ];
       list
       ];
    SetAttributes[insert, HoldAll];

其中，`i`代表`未排序部分`的索引，最小值是`2`，最大值是`len`；`j`代表`已排序部分`索引，最大值是`i-1`，最小值是`1`；`temp`是中间变量，用于交换数据。

# 归并 #

[visuAlgo]: https://visualgo.net/zh