个人中心
gpt4 book ai didi

algorithm - QuickSort 的迭代实现中的无限循环？

转载 作者：塔克拉玛干 更新时间：2023-11-03 05:52:55 24 4
gpt4 key购买 nike

<分区>

我正在尝试使用 Lomuto's Partitiong 实现迭代QuickSort方法，出于这个原因，我正在尝试实现一个堆栈，它包含一对定义要分区的子数组的索引，使用一个 struct 数组和两个 fields:iBeg、iEnd 和仅存储/访问 end 元素。

代码如下:

function [sorted] = iterativeQuickSort(A)
% Accepts 1xN unsorted integer array.
% Returns a sorted copy.   
% See also Partition.

  % Starting and ending indexes of unsorted array.
  iBeg = 1;
  iEnd = numel(A);

  % Struct holding A's subarrays star/end indexes resulting from partitioning.
  stack_elem = struct('iBeg', iBeg, 'iEnd', iEnd); 
  stack(end + 1) = stack_elem;  % push on stack

  while numel(stack) != 0

    % Extract last pair of indexes.
    iBeg = stack(end).iBeg;
    iEnd = stack(end).iEnd;
    stack(end) = [];            % pop from stack

    % Get pivot index and array after rearranging elements around the pivot.
    [B, pivotIndex] = Partition(A, iBeg, iEnd);
    A = B;

    % Store indexes of the next two subarrays defined by the pivot index,
    % if their sizes are > 0.
    if pivotIndex - 1 > iBeg 
      stack_elem = struct('iBeg', iBeg, 'iEnd', pivotIndex - 1);
      stack(end + 1) = stack_elem;
    end  

    if pivotIndex + 1 < iEnd
      stack_elem = struct('iBeg', pivotIndex + 1, 'iEnd', iEnd);
      stack(end + 1) = stack_elem;
    end   

  end  

  sorted = A;

end  

function [A, pivotIndex] = Partition (A, iBeg, iEnd)
% Accepts 1xN integer array.  
% Two integers - start and end indexes current subarray of A.
% Returns index of pivot element of current subarray partition
% and A after swaps.

  pivotValue = A(iEnd);      % Choose last element to be pivot.
  pivotIndex = iBeg;         % Initialize pivot index to start of subarray.

  for i = iBeg : iEnd        % Iterate over current subarray
    if A(i) <= pivotValue    % Push elements <= pivot in front of pivot index.   
      % Place element at i-th position before element with pivot index.
      [A(i), A(pivotIndex)] = swapElements(A(pivotIndex), A(i)); 
      % Account for the swap, go to next element.
      pivotIndex = pivotIndex + 1;
    end  
  end  

  % Bring the element used as pivot to its place
  [A(iEnd), A(pivotIndex)] = swapElements(A(pivotIndex), A(iEnd)); 
end  

function [elem2, elem1] = swapElements(elem1, elem2)
  [elem2, elem1] = deal(elem1, elem2);  
end

明显愚蠢的数组赋值 A = B 是为了指示由于 swap 引起的元素变化在函数 Partition(A, iBeg, iEnd).

目前的状态似乎是一个无限循环，其原因我无法确定，因此任何建议和建议将不胜感激!

输入:

A = [5,   4,   6,   2,   9,   1,   7,   3];
S = iterativeQuickSort(A)

预期输出:

[1, 2, 3, 4, 5, 6, 7, 9]

当前输出:永远不会从功能中返回，仅通过强制制动停止:ctrl + c。

注意:分区函数的实现和应用与指出可能重复的不同。

24 4 0
文章推荐： javascript - 如何将 (3n-1) 公式放入 JavaScript？
文章推荐： php嵌套包含行为
文章推荐： c++ - 数据结构 : insert(id, 值)、delete(id) 和 getMax()
文章推荐： php - ___ 编码为 UTF-8 - 是否有最终解决方案？
塔克拉玛干
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com