查看: 685|回复: 8|关注: 0

[未答复] 求助,如何分析我的排序算法优劣?

[复制链接]

新手

5 麦片

财富积分


050


3

主题

18

帖子

0

最佳答案
发表于 2019-1-10 13:01:06 | 显示全部楼层 |阅读模式
最近刚开始通过 Khan Academy 学习基本算法,其中有一个题目是对随机整数进行排序。我按照自己的想法编了一个算法,但和教程中采用的 Selection Sort 方法不同。我自己觉得我的算法好像更好一点,但不知道如何进行验证。麻烦大家帮忙分析一下,:handshake

我自己编的代码如下:
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------
% 数字排序,先随机生成20个0到100的整数,然后将其按大小排序。
% 这里的策略是从尾向前排:
% 首先,如果最后一个数比倒数第二个数小,则交换这两个数的位置;如果最后一个数比倒数第二个数大或相等,则保留原来顺序。
% 不管前面的两个数是否交换了位置,都接着比较倒数第二个数和倒数第三个数,如果后者比前者小,也进行交换,否则保留原来顺序。
% 一直比较和按上述原则确定是否交换顺序直到正序的第一个和第二个数的比较和交换操作完成,作为第一轮操作完成。
% 在这期间,每次比较如果有交换发生,则记录一次1,如果没有发生交换,则记录为0,将这一轮所有比较结果累加。
% 如果整个一轮操作下来都没有发生交换,则累加结果为0,意味着所有数字都已经按照大小顺序排列好了,整个排序操作就可以停止了。
% 如果累加结果大于0,则意味着排序可能还没有全部完成,需要再循环一轮来检查,直至不再发生数的顺序交换。

% 该排序算法的效率是 Big-O(n^2)
% Khan Academy Algorithm 教程中的 Selection Sort 算法是 Big-Theta(n^2)


arrayNum = randi(100, 1, 20);
lenNum = length(arrayNum);
needAnotherLoop = 1;
disp('Before sorting:');

disp(arrayNum);

while(needAnotherLoop > 0)    % 如果为零,则整个排序完成。
                              % 这里的迭代次数应该是小于或等于 n,因为假设每次循环某个数只发生了一次位置交换,则最糟糕的情况是当其到达其应该在的位置时需要 n 次循环,所有数都不可能需要超过 n 次循环才到达其应到位置,因此其算法适用 Big-O(n) notation
    i = lenNum;
    back2FrontSum = 0;  % 累加记录每一轮中是否有发生了顺序交换。
    while(i ~= 1)   % 这个也可以使用 for 循环,因此迭代次数是 n,其 running time 是 Big-Theta(n)
        [arrayNum(i), arrayNum(i-1), back2Front] = back2FrontSwapper(arrayNum(i), arrayNum(i-1));        
        back2FrontSum = back2FrontSum + back2Front;
        i = i - 1;
    end   
    needAnotherLoop = back2FrontSum;
end

disp('After sorting:');

disp(arrayNum);

function [arrNum1, arrNum2, switchOrNot] = back2FrontSwapper(backNum, frontNum)
    if backNum < frontNum
        switchNum = backNum;
        backNum = frontNum;
        frontNum = switchNum;
        switchOrNot = 1;
    else
        switchOrNot = 0;
    end
    arrNum1 = backNum;  % 需要用这两个变量来将值回传到函数的返回值中,而不是使用 return。
    arrNum2 = frontNum;
end


-----------------------------------


Before sorting:

    27    76    90    73    41    94    26    54    96    27    26    93     7    30    60    21    64    80    51    66

After sorting:

     7    21    26    26    27    27    30    41    51    54    60    64    66    73    76    80    90    93    94    96


------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

新手

5 麦片

财富积分


050


3

主题

18

帖子

0

最佳答案
 楼主| 发表于 2019-1-10 16:08:15 | 显示全部楼层
我按照 Selection Sort  编写的代码如下
--------------------------------------------------------------------------------------------------------------------------------

% Selection Sort 算法的基本思路是搜索整个数组,找到最小的那个数,并将其移到数组的最前面
% 然后找第二小的那个数,然后将其移到数组的第二位
% 循环上面的操作,直到完成整个数组的比较和排序
% 可以从第一个数开始,将其和第二个数比较,如果第二个数比第一个数小,则将当前操作数换为第二个数,然后将第二个数和后面的数比较
% 当和整个数组的数都比较完成后,当前操作数就是最小的那个数,将其和第一个数相交换
% 第二小的数可以从第二个数开始,其余操作一致。

arrayNum = randi(100, 1, 20);
lenNum = length(arrayNum);

disp('Before sorting:');
disp(arrayNum);

for i = 1:lenNum
    currNumIndex = i;
    for j = 1:(lenNum-i)
        nextNumIndex = i+j;
        currNumIndexSwitch = compareNum(arrayNum(currNumIndex), arrayNum(nextNumIndex));
        if currNumIndexSwitch == 1    % 如果返回值为1,则提示当前数比其后面的数大,因此将当前数改为后面的这个更小的数,直到比较完整个数组,得到第i小的数
            currNumIndex = nextNumIndex;
        end
    end
    tempNum = arrayNum(i);
    arrayNum(i) = arrayNum(currNumIndex);    % 将筛选比较后发现的第i小数排到第i位。
    arrayNum(currNumIndex) = tempNum;
    disp(arrayNum);
end

disp('After sorting:');
disp(arrayNum);


function currLessNumIndexSwitch = compareNum(num1, num2)   % 如果两数比较大小后需要交换,则返回1,否则返回0
    if num1 <= num2
        currLessNumIndexSwitch = 0;
    else
        currLessNumIndexSwitch = 1;
    end
end

------------------------------------------------------------------------------------------------------------------------------

Before sorting:
    52    37    74    53    81    82    19    13    83    64     2    90    52    55    61    77    86    39     9    74


     2    37    74    53    81    82    19    13    83    64    52    90    52    55    61    77    86    39     9    74

     2     9    74    53    81    82    19    13    83    64    52    90    52    55    61    77    86    39    37    74

     2     9    13    53    81    82    19    74    83    64    52    90    52    55    61    77    86    39    37    74

     2     9    13    19    81    82    53    74    83    64    52    90    52    55    61    77    86    39    37    74

     2     9    13    19    37    82    53    74    83    64    52    90    52    55    61    77    86    39    81    74

     2     9    13    19    37    39    53    74    83    64    52    90    52    55    61    77    86    82    81    74

     2     9    13    19    37    39    52    74    83    64    53    90    52    55    61    77    86    82    81    74

     2     9    13    19    37    39    52    52    83    64    53    90    74    55    61    77    86    82    81    74

     2     9    13    19    37    39    52    52    53    64    83    90    74    55    61    77    86    82    81    74

     2     9    13    19    37    39    52    52    53    55    83    90    74    64    61    77    86    82    81    74

     2     9    13    19    37    39    52    52    53    55    61    90    74    64    83    77    86    82    81    74

     2     9    13    19    37    39    52    52    53    55    61    64    74    90    83    77    86    82    81    74

     2     9    13    19    37    39    52    52    53    55    61    64    74    90    83    77    86    82    81    74

     2     9    13    19    37    39    52    52    53    55    61    64    74    74    83    77    86    82    81    90

     2     9    13    19    37    39    52    52    53    55    61    64    74    74    77    83    86    82    81    90

     2     9    13    19    37    39    52    52    53    55    61    64    74    74    77    81    86    82    83    90

     2     9    13    19    37    39    52    52    53    55    61    64    74    74    77    81    82    86    83    90

     2     9    13    19    37    39    52    52    53    55    61    64    74    74    77    81    82    83    86    90

     2     9    13    19    37    39    52    52    53    55    61    64    74    74    77    81    82    83    86    90

     2     9    13    19    37    39    52    52    53    55    61    64    74    74    77    81    82    83    86    90


After sorting:
     2     9    13    19    37    39    52    52    53    55    61    64    74    74    77    81    82    83    86    90

新手

5 麦片

财富积分


050


3

主题

18

帖子

0

最佳答案
 楼主| 发表于 2019-1-10 17:27:02 | 显示全部楼层
关于数字排序,教程还介绍了第二种排序算法 Insertion Sort,我也自己编写了代码如下,这种算法应该和我的自建算法的效率类似,不知道对不对:
-------------------------------------------------------------------------------------------------------------------------------

% Insertion Sort 算法的基本思路是从整个数组中“抽扑克牌”
% 最初手上只有一张扑克牌,抽第二次的时候,手上将有两张扑克牌
% 抽出的扑克牌加到手上已有的扑克牌中,并按大小顺序依次排列,因此手上的扑克牌始终是排好顺序的。
% 在加一张新的牌到手上已有的扑克牌时,需要和已有的牌进行比较,可以采用从后向前比较的方法,这样只要比较的牌比要加的牌小,就不需要继续比较
% 当整个数组的“牌”抽完之后,手上的牌也就完全排好了。
% 整个数组为全集,手上的牌和剩下的牌都是其子集,两者互为补集。

arrayNum = randi(100, 1, 20);
lenNum = length(arrayNum);
currArray = [arrayNum(1)];    % 相当于手上的牌,刚开始只有一张牌

disp('Before sorting:');
disp(arrayNum);

for i = 2:lenNum
    newNum2Add = arrayNum(i);    % 相当于抽出一张新牌
    currArray = [currArray, newNum2Add];    % 要将新抽出的牌加到手上的牌中
    currArray = sortedCurrArray(currArray, i);     % 将手上的牌进行排序
end

disp('After sorting:');
disp(currArray);

function sortedArray = sortedCurrArray(unsortedArray, lenArray)    % 函数用于将手上的牌进行排序,
    while(lenArray > 1)
        if unsortedArray(lenArray) < unsortedArray(lenArray-1)     % 由后向前比较,如果最后面的牌比前面的牌小,则交换之,并继续向前比较,
            temp = unsortedArray(lenArray-1);
            unsortedArray(lenArray-1) = unsortedArray(lenArray);
            unsortedArray(lenArray) = temp;
            lenArray = lenArray - 1;
        else            
            lenArray = 1;     % 一旦后面的牌比前面的牌大,则不需要继续比较
        end
    end
    sortedArray = unsortedArray;     % 将排序好的牌返回。
end

------------------------------------------------------------------------------------------------------------------------------

Before sorting:
    25     1    82    15    88    10    36    60    59    67    65    44    14    76    25    66    86     9    98     4


currArray = 1×2   
     1    25

currArray = 1×3   
     1    25    82

currArray = 1×4   
     1    15    25    82

currArray = 1×5   
     1    15    25    82    88

currArray = 1×6   
     1    10    15    25    82    88

currArray = 1×7   
     1    10    15    25    36    82    88

currArray = 1×8   
     1    10    15    25    36    60    82    88

currArray = 1×9   
     1    10    15    25    36    59    60    82    88

currArray = 1×10   
     1    10    15    25    36    59    60    67    82    88

currArray = 1×11   
     1    10    15    25    36    59    60    65    67    82    88

currArray = 1×12   
     1    10    15    25    36    44    59    60    65    67    82    88

currArray = 1×13   
     1    10    14    15    25    36    44    59    60    65    67    82    88

currArray = 1×14   
     1    10    14    15    25    36    44    59    60    65    67    76    82    88

currArray = 1×15   
     1    10    14    15    25    25    36    44    59    60    65    67    76    82    88

currArray = 1×16   
     1    10    14    15    25    25    36    44    59    60    65    66    67    76    82    88

currArray = 1×17   
     1    10    14    15    25    25    36    44    59    60    65    66    67    76    82    86    88

currArray = 1×18   
     1     9    10    14    15    25    25    36    44    59    60    65    66    67    76    82    86    88

currArray = 1×19   
     1     9    10    14    15    25    25    36    44    59    60    65    66    67    76    82    86    88    98

currArray = 1×20   
     1     4     9    10    14    15    25    25    36    44    59    60    65    66    67    76    82    86    88    98


After sorting:
     1     4     9    10    14    15    25    25    36    44    59    60    65    66    67    76    82    86    88    98

新手

5 麦片

财富积分


050


3

主题

18

帖子

0

最佳答案
 楼主| 发表于 2019-1-11 09:13:47 | 显示全部楼层
今天查了一下资料,原来我第一个算法叫做 Bubble Sort,是入门者最容易想到的算法,哈哈,:lol:lol

新手

5 麦片

财富积分


050


3

主题

18

帖子

0

最佳答案
 楼主| 发表于 2019-1-11 09:16:44 | 显示全部楼层
今天又学了一个递归算法,刚开始用 MATLAB,大家帮看看写法上有什么可以提高的没有

--------------------------------------------------------------------------------------------------------------------------------

% Recursive Factorial 递归算法(类似于俄罗斯套娃)不使用 for 循环,而是递归其本身,直到其最初值,
% 其最初值是确定的,不需要计算,也不能再递归。
% 其特点是(1)递归是收敛的;(2)最终必须递归到某个确定值作为终点。
% 下面递归计算 n!

n = 5;
recurFactorialN = recurFunc(n);
str = ['n! equals ' num2str(recurFactorialN)];
disp(str);


function recurFactorial = recurFunc(n)
    if n == 1
        recurFactorial = 1;    % 最初值是确定的,同时也不能再递归。
    else
        recurFactorial = n * recurFunc(n-1);   % 递归调用函数自身。
    end
end

------------------------------------------------------------------------------------------------------------------------------

n! equals 120

------------------------------------------------------------------------------------------------------------------------------

新手

5 麦片

财富积分


050


3

主题

18

帖子

0

最佳答案
 楼主| 发表于 2019-1-11 09:20:36 | 显示全部楼层
判断是否回文也可以使用递归算法,一开始不习惯这种思维,不自然地又用了 for 语句,睡了一觉再琢磨才改过来,这种写法确实比 for 语句简练。

-------------------------------------------------------------------------------------------------------------------------------

% Palindrome 回文判断使用递归算法

str2Check = 'abdccdba';
result = endCharPairMatch(str2Check);
txt2Disp = [str2Check, ' ', result];
disp(txt2Disp);

function isPalindrome = endCharPairMatch(str)
    if (length(str) == 1) | (isempty(str))
        isPalindrome = 'is a palindrome.';
    elseif (length(str) > 1) & (str(1) ~= str(end))
        isPalindrome = 'is not a palindrome.';
    else
        str = str(2:(end-1));
        isPalindrome = endCharPairMatch(str);
    end
end

-----------------------------------------------------------------------------------------------------------------------------

abdccdba is a palindrome.

新手

5 麦片

财富积分


050


3

主题

18

帖子

0

最佳答案
 楼主| 发表于 2019-1-11 10:04:06 | 显示全部楼层
% 计算实数 x 的整数次幂 n 也可以采用递归算法

x = 2;
n = -10;

if n < 0
    result = 1/nPowerX(x, abs(n));
else
    result = nPowerX(x, n);
end

txt2Disp = ['Number ', num2str(x), '''', 's ', num2str(n), ' power is ', num2str(result), '.'];    % 要用两个单引号来构造一个单引号的显示,同时还加上外套的一对单引号
disp(txt2Disp);

function f = nPowerX(x, n)  % n 必须是0或正整数。
    if n ~= 0
        f = x * nPowerX(x, n-1);
    else
        f = 1;
    end   
end

----------------------------------------------------------------------------------------------------------------------------

Number 2's -10 power is 0.00097656.

-----------------------------------------------------------------------------------------------------------------------------

新手

5 麦片

财富积分


050


3

主题

18

帖子

0

最佳答案
 楼主| 发表于 2019-1-11 12:47:23 | 显示全部楼层
% 计算实数 x 的整数次幂采用递归算法还可以进一步优化

x = 2;
n = -2;

result = nPowerX(x, n);

txt2Disp = ['Number ', num2str(x), '''', 's ', num2str(n), ' power is ', num2str(result), '.'];    % 要用两个单引号来构造一个单引号的显示,同时还加上外套的一对单引号
disp(txt2Disp);

function f = nPowerX(x, n)  % n 必须是整数。
    if n > 0 & mod(n, 2) == 1
        f = x .* nPowerX(x, n-1);
    elseif n > 0 & mod(n, 2) == 0    % 当 n 为正偶整数的时候,可以先求 x^(n/2), 然后将其平方得到 x^n,这样使得运算增快,而且如果 n/2 也是偶整数的话,还可以进一步递归,则运算进一步简化
        f = nPowerX(x, n/2).^2;
    elseif n < 0
        f = 1/(x .* nPowerX(x, abs(n)-1));
    else
        f = 1;
    end   
end

---------------------------------------------------------------------------------------------------------------------------

Number 2's -2 power is 0.25.

---------------------------------------------------------------------------------------------------------------------------

新手

5 麦片

财富积分


050


3

主题

18

帖子

0

最佳答案
 楼主| 发表于 2019-1-11 16:52:52 | 显示全部楼层
又尝试了一个新算法

----------------------------------------------------------------------------------------------------------------------------------------------------------------------

% Sierpinskin Gasket 谢尔宾斯基三角形使用了函数一次循环内多次自身递归
% 谢尔宾斯基三角形的绘制方法是将一个正方形分割成四个象限
% 左下象限留空,其余三个象限各自进一步分割成四个象限
% 进一步细分的左下象限也留空,其余三个象限继续分割,直至最后分割到正方形的边长为设定的单位长度
% 当正方形不能被进一步分割的时候,将左下象限外的三个象限填充,完成绘图。

scale = 1;    % 最小分割单位
n = 7;     % 分割次数

lowerVertexX = 0;     % 待分割的正方形的左下顶点坐标
lowerVertexY = 0;     
upperVertexX = scale*2^n;    % 待分割的正方形的右上顶点坐标,正方形的边长(upperVertexX - lowerVertexX)为最小分割单位的 2^n 倍,因此可以进行 n 次 2 分。
upperVertexY = scale*2^n;

upperHalfDevideSquare(lowerVertexX, lowerVertexY, upperVertexX, upperVertexY, scale);


function upperHalfDevideSquare(lowerVertexX, lowerVertexY, upperVertexX, upperVertexY, scale)
    if (upperVertexX - lowerVertexX)/scale == 1    % 当正方形分割至边长为预设的最小分割单位时,不再继续分割,而是开始绘图。
        axis equal;
        plot([lowerVertexX, upperVertexX], [lowerVertexY, upperVertexY], 'rs');
        hold on;
   
    elseif (upperVertexX - lowerVertexX)/scale > 1
        lowerVertexX1 = lowerVertexX;    % 确定分割出的左上象限的正方形的左下顶点和右上顶点坐标
        lowerVertexY1 = (upperVertexY + lowerVertexY)/2;
        upperVertexX1 = (upperVertexX + lowerVertexX)/2;
        upperVertexY1 = upperVertexY;
        upperHalfDevideSquare(lowerVertexX1, lowerVertexY1, upperVertexX1, upperVertexY1, scale);    % 调用函数自身进一步分割左上象限的正方形
        
        lowerVertexX2 = (upperVertexX + lowerVertexX)/2;    % 确定分割出的右上象限的正方形的左下顶点和右上顶点坐标
        lowerVertexY2 = (upperVertexY + lowerVertexY)/2;
        upperVertexX2 = upperVertexX;
        upperVertexY2 = upperVertexY;
        upperHalfDevideSquare(lowerVertexX2, lowerVertexY2, upperVertexX2, upperVertexY2, scale);
        
        lowerVertexX3 = (upperVertexX + lowerVertexX)/2;    % 确定分割出的右下象限的正方形的左下顶点和右上顶点坐标
        lowerVertexY3 = lowerVertexY;
        upperVertexX3 = upperVertexX;
        upperVertexY3 = (upperVertexY + lowerVertexY)/2;
        upperHalfDevideSquare(lowerVertexX3, lowerVertexY3, upperVertexX3, upperVertexY3, scale);
    end   
end

--------------------------------------------------------------------------------------------------------------------------------------------------------------------

谢尔宾斯基三角形

谢尔宾斯基三角形
您需要登录后才可以回帖 登录 | 注册

本版积分规则

关闭

站长推荐上一条 /3 下一条

快速回复 返回顶部 返回列表