用乙太坊對整數數組進行排序

我正在嘗試在 Solidity 中排序一個簡單的整數數組，但我找不到任何真正的資源，所以我試圖“以艱難的方式”做到這一點，但到目前為止收效甚微。

有人知道有什麼可以幫助的嗎？

這是我迄今為止嘗試過的，但沒有運氣。每當我嘗試它時，我都會出現記憶體不足的錯誤。

 function quickSort(uint[] arr, uint left, uint right) private returns(uint[] _arr){
     uint i = left;
     uint j = right;
     uint tmp;
     uint pivot = arr[(left + right) / 2];
     while (i <= j) {
           while (arr[i] < pivot)
                 i++;
           while (arr[j] > pivot)
                 j--;
           if (i <= j) {
                 tmp = arr[i];
                 arr[i] = arr[j];
                 arr[j] = tmp;
                 i++;
                 j--;
           }
     }
     if (left < j)
           quickSort(arr, left, j);
     if (i < right)
           quickSort(arr, i, right);
}

有人有什麼要分享的嗎？

錯誤往往是“ERROR: invalid jump destination (PUSH1)”

編輯 ：

與：

function insertionSort(uint[] a){
for (uint i = 1;i < a.length;i++){
 uint temp = a[i];
 uint j;
 for (j = i -1; j >= 0 && temp < a[j]; j--)
   a[j+1] = a[j];
 a[j + 1] = temp;
}
}

編輯 2：

也固定

 function insertionSort(uint[] a)internal {
  for (uint i = 1;i < a.length;i++){
   uint temp = a[i];
   uint j;
   for (j = i -1; j >= 0 && temp < a[j]; j--)
     a[j+1] = a[j];
   a[j + 1] = temp;
  }
 }

當您越界訪問數組時，會生成“無效的跳轉目標”。您是否嘗試在mix中調試它？

以下程式碼似乎有效。通過storage在參數類型中使用關鍵字，您可以傳遞儲存引用（僅適用於內部函式和庫），否則儲存數據將被複製到記憶體中。作為一種優化，您可能會考慮將儲存數組複製到記憶體，檢查它是否已排序，如果沒有，則對其進行排序並將其複制回儲存。關於瀏覽器可靠性的另一個潛在陷阱：您必須將數組參數輸入為[1,7,4,5].

哦，最好的優化當然是對鏈下數組進行排序，只檢查鏈上是否排序。

// SPDX-License-Identifier: MIT
pragma solidity ^0.7.0;


function quickSort(uint[] memory arr, int left, int right) pure {
   int i = left;
   int j = right;
   if (i == j) return;
   uint pivot = arr[uint(left + (right - left) / 2)];
   while (i <= j) {
       while (arr[uint(i)] < pivot) i++;
       while (pivot < arr[uint(j)]) j--;
       if (i <= j) {
           (arr[uint(i)], arr[uint(j)]) = (arr[uint(j)], arr[uint(i)]);
           i++;
           j--;
       }
   }
   if (left < j)
       quickSort(arr, left, j);
   if (i < right)
       quickSort(arr, i, right);
}

contract QuickSort {
   function sort(uint[] memory data) public pure returns (uint[] memory) {
       quickSort(data, int(0), int(data.length - 1));
       return data;
   }
}

編輯（2020-10）：@subhodi 修復了下溢問題並更新到最新的 Solidity 版本。

引用自：https://ethereum.stackexchange.com/questions/1517