Javascript Bug中的快速排序

Quicksort in Javascript Bug

本文关键字：快速排序 Bug Javascript      更新时间：2023-09-26

希望在Javascript中获得一些关于快速排序算法的帮助（这不是为了家庭作业或其他什么，只是为了好玩）-它不起作用，我不确定哪里出了问题。

function quicksort ( arr ) {
        // Launch the sorting process.
        sort(arr, 0, arr.length - 1 );
        /**
         * swap
         * takes in an array and two indexes,
         * swaps the elements in the array at those indexes
         */
        function swap ( arr, a, b ) {
            var temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }
        function partition ( arr, l, r) {
            var p = arr[r],
                i = l - 1,
                j = l;
            while ( j < r - 1) {
                if (arr[j] <= p) {
                    swap ( arr, ++i, j );
                }
                j++;
            }
            swap (arr, i + 1, r);
            return i + 1;
        }
        function sort ( arr, l, r ) {
            var p;
            if (l < r) {
                p = partition( arr, l, r );
                sort( arr, l, p - 1);
                sort( arr, p + 1, r);
            } else {
                console.log(arr);    
            }
        }
    }

好吧，我想我找到了。问题就在我的分区循环中，我过早地结束了它。这是完整的代码：

  function quicksort ( arr ) {
        // Launch the sorting process.
        sort(arr, 0, arr.length - 1 );
        /**
         * swap
         * takes in an array and two indicies,
         * swaps the elements in the array at those indicies
         */
        function swap ( arr, a, b ) {
            var temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }
        function partition ( arr, l, r) {
            var p = arr[r],
                i = l - 1,
                j = l;
            while ( j < r) {
                if (arr[j] <= p) {
                    swap ( arr, ++i, j );
                }
                j++;
            }
            // Put the pivot in its correct place
            swap (arr, i + 1, r);
            return i + 1;
        }
        function sort ( arr, l, r ) {
            var p;
            if (l < r) {
                p = partition( arr, l, r );
                sort( arr, l, p - 1);
                sort( arr, p + 1, r);
            } else if (l === arr.length) {
                // Output the sorted array.
                console.log(arr);    
            }
        }
    }

基本测试：

快速排序（[19,12,1,2,3123,23,2,5]）[1，2，2，3，5，12，19，23，123]

快速排序（[8,3,2,5,1,3]）[1,1,2,3,5,8]

对如何改进的建议持开放态度！：）

相关文章：