在数组的 2/3 上调用自身的排序算法

Sorting algorithm that is calling itself on 2/3 of an array

本文关键字：排序 调用 算法 数组      更新时间：2023-09-26

我尝试实现一种排序算法，其工作原理如下：给定一个长度为 n 的数组，算法应该在数组的前 2/3 上递归调用自己，然后在最后 2/3 上递归调用自己，然后在数组的前 2/3 上再次调用自己。在每次调用时，算法应在查看两个或更少元素时对当前数组进行排序并退出。该方法应将数组 A 和两个索引作为参数。

因此，这里的主要困难是创建表示数组 2/3 的索引。我的想法是做x = Math.floor((i-j)/3)，x是第一个 1/3 和第二个 1/3 中的元素数量。所以前 2/3 可以以 [i,x*2] 为界，后 2/3 以 [x+1,j] 为界。你认为这个想法有什么错误吗？

我想出了以下算法，该算法无法正确排序。因此，无论是算法还是上述想法都是有缺陷的。你看到什么问题了吗？

var threeSort = function(A,i,j) {
  var diff = j-i;
  if (diff <= 2) {
        if (A[j] < A[i]) {
        var tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
      }
      return;
  }
  var x = Math.floor(diff/3);
  threeSort(A,i,x*2);
  threeSort(A,x+1,j);
  threeSort(A,i,x*2);
};
var arr = [3,4,1,4,2];
threeSort(arr, 0, arr.length-1);

https://jsfiddle.net/jyqyhxko/2/

var diff = j-i;
if (diff <= 2) {

假设 i = 0，j = 2。范围 0..2 包含 3 个项目，

进行

此更正以避免对双元素片段进行递归排序：

if (diff < 2) {

下一个问题：你的x是相对偏移。要获取递归调用的绝对索引，您可以像 

if (j-i < 2){
  if (A[j] < A[i]) {
    var tmp = A[i];
    A[i] = A[j];
    A[j] = tmp; 
  };
  return;
};
var d = Math.floor((j - i + 1) / 3);
threeSort(A,i,j-d);
threeSort(A,i+d,j);
threeSort(A,i,j-d);

小提琴

相关文章：