如何更快地对 HTML 表格进行排序？

Question

我是 Javascript 新手。在尝试了许多 Javascript 和 Jquery 插件对我的 HTML 表进行排序并最终感到失望之后，我决定实现自己的 Javascript 代码来对 HTML 表进行排序。我写的代码是 W3Schools 的更新。

function sortFunctionNumeric(n) {
  var table, rows, switching, i, x, y, shouldSwitch, dir, switchcount = 0;
  table = document.getElementById("reportingTable");
  switching = true;
  //Set the sorting direction to ascending:
  dir = "asc";
  /*Make a loop that will continue until
  no switching has been done:*/
  while (switching) {
    //start by saying: no switching is done:
    switching = false;
    rows = table.rows;
    /*Loop through all table rows (except the
    first, which contains table headers):*/
    for (i = 1; i < (rows.length - 1); i++) {
      //start by saying there should be no switching:
      shouldSwitch = false;
      /*Get the two elements you want to compare,
      one from current row and one from the next:*/
      x = rows[i].getElementsByTagName("TD")[n];
      y = rows[i + 1].getElementsByTagName("TD")[n];
      /*check if the two rows should switch place,
      based on the direction, asc or desc:*/
      if (dir == "asc") {
        if (Number(x.innerHTML) > Number(y.innerHTML)) {
          //if so, mark as a switch and break the loop:
          shouldSwitch = true;
          break;
        }
      } else if (dir == "desc") {
        if (Number(x.innerHTML) < Number(y.innerHTML)) {
          //if so, mark as a switch and break the loop:
          shouldSwitch = true;
          break;
        }
      }
    }
    if (shouldSwitch) {
      /*If a switch has been marked, make the switch
      and mark that a switch has been done:*/
      rows[i].parentNode.insertBefore(rows[i + 1], rows[i]);
      switching = true;
      //Each time a switch is done, increase this count by 1:
      switchcount++;
    } else {
      /*If no switching has been done AND the direction is "asc",
      set the direction to "desc" and run the while loop again.*/
      if (switchcount == 0 && dir == "asc") {
        dir = "desc";
        switching = true;
      }
    }
  }
}

现在排序工作得很好。但是，速度非常慢！

我处理了很多行 daqta（取决于项目，它可以达到 9000 行）。有没有办法加速我的 Javascript 代码？

Answer 1

它有助于避免在浏览器 JavaScript 中实现排序算法，因为Array.prototype.sort即使您最终实现相同的排序算法，JavaScript 的内置方法也会快得多（IIRC 大多数 JS 引擎可能无论如何都会使用QuickSort）。

这是我的做法：

• 获取<tr>JavaScript 中的所有元素Array。
  • 您需要querySelectorAll与 with 结合使用，Array.from因为querySelectorAll 不返回数组，它实际上返回一个NodeListOf<T>- 但您可以Array.from将其传递给以将其转换为一个Array。
• 获得 后Array，您可以使用Array.prototype.sort(comparison)自定义回调从正在比较<td>的两个<tr>元素的子元素中提取数据，然后比较数据（x - y在比较数值时使用该技巧。对于string您想要使用的值String.prototype.localeCompare，例如return x.localeCompare( y ).
• 在之后Array的排序（这不应该采取更比甚至与行数以万计的表几毫秒，因为快速排序是真快！）重新添加每个<tr>使用appendChild父<tbody>。

我在 TypeScript 中的实现如下，以及位于下方的脚本运行器中带有有效 JavaScript 的工作示例：

// This code has TypeScript type annotations, but can be used directly as pure JavaScript by just removing the type annotations first.

function sortTableRowsByColumn( table: HTMLTableElement, columnIndex: number, ascending: boolean ): void {

    const rows = Array.from( table.querySelectorAll( ':scope > tbody > tr' ) );

    rows.sort( ( x: HTMLtableRowElement, y: HTMLtableRowElement ) => {
        const xValue: string = x.cells[columnIndex].textContent;
        const yValue: string = y.cells[columnIndex].textContent;

        // Assuming values are numeric (use parseInt or parseFloat):
        const xNum = parseFloat( xValue );
        const yNum = parseFloat( yValue );

        return ascending ? ( xNum - yNum ) : ( yNum - xNum ); // <-- Neat comparison trick.
    } );

    // There is no need to remove the rows prior to adding them in-order because `.appendChild` will relocate existing nodes.
    for( let row of rows ) {
        table.tBodies[0].appendChild( row );
    }
}

function onColumnHeaderClicked( ev: Event ): void {

    const th = ev.currentTarget as HTMLTableCellElement;
    const table = th.closest( 'table' );
    const thIndex: number = Array.from( th.parentElement.children ).indexOf( th );

    const ascending = ( th.dataset as any ).sort != 'asc';

    sortTableRowsByColumn( table, thIndex, ascending );

    const allTh = table.querySelectorAll( ':scope > thead > tr > th' );
    for( let th2 of allTh ) {
        delete th2.dataset['sort'];
    }

    th.dataset['sort'] = ascending ? 'asc' : 'desc';
}

我的sortTableRowsByColumn函数假设如下：

• 您的<table>元素使用<thead>并有一个<tbody>
• 您使用的是最新的浏览器支持=>，Array.from，for( x of y )，:scope，.closest()，和.remove()（即不是Internet Explorer 11）。
• 您的数据作为元素的#text( .textContent)存在<td>。
• 表中没有colspan或没有rowspan单元格。

这是一个可运行的示例。只需单击列标题即可按升序或降序排序：

// This code has TypeScript type annotations, but can be used directly as pure JavaScript by just removing the type annotations first.

function sortTableRowsByColumn( table: HTMLTableElement, columnIndex: number, ascending: boolean ): void {

    const rows = Array.from( table.querySelectorAll( ':scope > tbody > tr' ) );

    rows.sort( ( x: HTMLtableRowElement, y: HTMLtableRowElement ) => {
        const xValue: string = x.cells[columnIndex].textContent;
        const yValue: string = y.cells[columnIndex].textContent;

        // Assuming values are numeric (use parseInt or parseFloat):
        const xNum = parseFloat( xValue );
        const yNum = parseFloat( yValue );

        return ascending ? ( xNum - yNum ) : ( yNum - xNum ); // <-- Neat comparison trick.
    } );

    // There is no need to remove the rows prior to adding them in-order because `.appendChild` will relocate existing nodes.
    for( let row of rows ) {
        table.tBodies[0].appendChild( row );
    }
}

function onColumnHeaderClicked( ev: Event ): void {

    const th = ev.currentTarget as HTMLTableCellElement;
    const table = th.closest( 'table' );
    const thIndex: number = Array.from( th.parentElement.children ).indexOf( th );

    const ascending = ( th.dataset as any ).sort != 'asc';

    sortTableRowsByColumn( table, thIndex, ascending );

    const allTh = table.querySelectorAll( ':scope > thead > tr > th' );
    for( let th2 of allTh ) {
        delete th2.dataset['sort'];
    }

    th.dataset['sort'] = ascending ? 'asc' : 'desc';
}

function sortTableRowsByColumn( table, columnIndex, ascending ) {

    const rows = Array.from( table.querySelectorAll( ':scope > tbody > tr' ) );
    
    rows.sort( ( x, y ) => {
    
        const xValue = x.cells[columnIndex].textContent;
        const yValue = y.cells[columnIndex].textContent;
        
        const xNum = parseFloat( xValue );
        const yNum = parseFloat( yValue );

        return ascending ? ( xNum - yNum ) : ( yNum - xNum );
    } );

    for( let row of rows ) {
        table.tBodies[0].appendChild( row );
    }
}

function onColumnHeaderClicked( ev ) {
    
    const th = ev.currentTarget;
    const table = th.closest( 'table' );
    const thIndex = Array.from( th.parentElement.children ).indexOf( th );

    const ascending = !( 'sort' in th.dataset ) || th.dataset.sort != 'asc';
    
    const start = performance.now();

    sortTableRowsByColumn( table, thIndex, ascending );

    const end = performance.now();
    console.log( "Sorted table rows in %d ms.",  end - start );

    const allTh = table.querySelectorAll( ':scope > thead > tr > th' );
    for( let th2 of allTh ) {
        delete th2.dataset['sort'];
    }
 
    th.dataset['sort'] = ascending ? 'asc' : 'desc';
}

window.addEventListener( 'DOMContentLoaded', function() {
    
    const table = document.querySelector( 'table' );
    const tb = table.tBodies[0];

    const start = performance.now();

    for( let i = 0; i < 9000; i++ ) {
        
        let row = table.insertRow( -1 );
        row.insertCell( -1 ).textContent = Math.ceil( Math.random() * 1000 );
        row.insertCell( -1 ).textContent = Math.ceil( Math.random() * 1000 );
        row.insertCell( -1 ).textContent = Math.ceil( Math.random() * 1000 );
    }

    const end = performance.now();
    console.log( "IT'S OVER 9000 ROWS added in %d ms.", end - start );
    
} );

html { font-family: sans-serif; }

table {
    border-collapse: collapse;
    border: 1px solid #ccc;
}
    table > thead > tr > th {
        cursor: pointer;
    }
    table > thead > tr > th[data-sort=asc] {
        background-color: blue;
        color: white;
    }
    table > thead > tr > th[data-sort=desc] {
        background-color: red;
        color: white;
    }
    table th,
    table td {
        border: 1px solid #bbb;
        padding: 0.25em 0.5em;
    }

关于性能的一句话：

根据 Chrome 78 的开发者工具的性能分析器，在我的电脑上，performance.now()调用表明行在大约 300 毫秒内排序，但是在 JavaScript 停止运行后发生的“重新计算样式”和“布局”操作分别花费了 240 毫秒和 450 毫秒（ 690 毫秒的总重新布局时间，加上 300 毫秒的排序时间意味着从点击到排序需要整整一秒（1,000 毫秒）。

当我更改脚本以便将<tr>元素添加到中间DocumentFragment而不是<tbody>（这样.appendChild可以保证每次调用都不会导致回流/布局，而不仅仅是假设.appendChild不会触发回流）并重新运行性能测试我的结果定时的数字是更多或更少相同的（他们实际上稍微高了约120毫秒后，重复5次总共为（1,120ms）的平均时间-但我会把下来到浏览器JIT播放机.

这是里面更改的代码sortTableRowsByColumn：

    function sortTableRowsByColumn( table, columnIndex, ascending ) {

        const rows = Array.from( table.querySelectorAll( ':scope > tbody > tr' ) );

        rows.sort( ( x, y ) => {

            const xValue = x.cells[columnIndex].textContent;
            const yValue = y.cells[columnIndex].textContent;

            const xNum = parseFloat( xValue );
            const yNum = parseFloat( yValue );

            return ascending ? ( xNum - yNum ) : ( yNum - xNum );
        } );

        const fragment = new DocumentFragment();
        for( let row of rows ) {
            fragment.appendChild( row );
        }

        table.tBodies[0].appendChild( fragment );
    }

我认为由于自动表格布局算法，性能相对较慢。我敢打赌，如果我更改 CSS 以使用table-layout: fixed;布局时间会缩短。（更新：我测试了它，table-layout: fixed;令人惊讶的是它根本没有提高性能 - 我似乎无法获得比 1,000 毫秒更好的时间 - 哦，好吧）。