Javascript Бесконечные петли и ошибки рекурсии

Question

Я пытаюсь кодировать алгоритм сортировки с помощью Javascript. Псевдокод находится в моей ссылке. Это моя ссылка Go Playground. http://play.golang.org/p/wQwO6Wvd7b

Как вы видите, он работает на других языках. (Я пытался с Python, C, C++, Ruby, Go с тем же кодом, и все они работают отлично.) Так что я сделал то же самое с Javascript, но он не работает, и я не могу понять, почему. Спасибо за Крис в моей предыдущей публикации: Javascript Sorting. Allocation fail process out of memory error

я понял, мой код в JavaScript, выходит за пределы индекса с рекурсией, но я понятия не имею, почему и как это возможно в Javascript в то время как другие языки просто сделать правильную работу как Я код. Я определенно пропустил что-то фундаментальное в Javascript и в рекурсии. Может ли какой-нибудь орган помочь мне разобраться? (Не домашнее задание, просто самостоятельное самостоятельное изучение) Я довольно новичок в Javascript.

Я не думаю, что мне нужно будет сортировать в Javascript, но я хочу знать, что я делаю неправильно.

Ниже приведен мой код с целью проверки ошибок.

var arr = [-1, 5, 7, 4, 0, 1, -5]; 
    console.log("Unsorted Array:", arr); 
    console.log("# of elements in array:", arr.length) 

    function Partition(arr, first_index, last_index) { 
     console.log("---") 
     console.log("# of elements in array:", arr.length) 
     console.log("First index is", first_index); 
     console.log("Last index is", last_index); 
     console.log("---") 
     var x = arr[last_index]; 
     var i = first_index - 1; 

     for (var j = 0; j < arr.length-1; j++) { 
       if (j > 100) { 
        console.log("Looping way too much."); 
        return; 
       } 
       if (arr[j] <= x) { 
        i += 1; 
        console.log("Swap index:", i, j); 
        var temp_1 = arr[i]; 
        arr[i] = arr[j]; 
        arr[j] = temp_1; 
       } 
     } 
     console.log("Swap index:", (i+1), last_index); 
     var temp_2 = arr[i+1]; 
     arr[i+1] = arr[last_index]; 
     arr[last_index] = temp_2; 

     return i+1; 
    } 

    function QSort(arr, first_index, last_index) { 
     console.log("QuickSort index:", first_index, last_index); 

     if (first_index < last_index) { 
       var mid = Partition(arr, first_index, last_index); 
       QSort(arr, first_index, mid-1); 
       QSort(arr, mid+1, last_index); 
     } 
    } 

    QSort(arr, 0, arr.length-1); 
    console.log("Sorted Array:", arr); 

И я предполагаю, почему это зацикливание слишком много ниже. Я узнал, что я делаю что-то неправильно с рекурсией.

количество элементов в массиве: 8
Первый индекс 2
Последний индекс индекс 6

Сменный: 2 0
Индекс Обмен: 3 2
Индекс Обмен: 4 3
Сменный индекс: 5 4
индекс Обмен: 6 5
индекс Обмен: 7 6
индекс Обмен: 8 6
Цюй ickSort индекс: 2 7

количество элементов в массиве: 9
Первый индекс 2
Последний индекс 7

и дальше

Answer 1

Я не понимаю, как это будет работать на других языках, потому что это написано неправильно. Цикл в методе разбиения переходит на работу по всему массиву, когда на самом деле он должен работать только на той части, что он сказал, чтобы работать на (между FIRST_INDEX и last_index)

Эта строка кода:

for (var j = 0; j < arr.length-1; j++) 

должно быть:

for (var j = first_index; j < last_index; j++) 

Answer 2

SPOILER ALERT - это скрипка имеет рабочую версию быстрой сортировки. Я вроде как боролся с вашей версией, поэтому написал свои собственные.

Алгоритмы, такие как quicksort, предоставляют множество возможностей для ошибок (много мест для отключения одного и т. Д.).)

Как общее предложение, вы можете захотеть сделать метод быстрой сортировки, которую вы называете, просто передавая массив:

function quick_sort(array) { 
    qsort(array, 0, array.length); 
    console.log(array); 
} 

Надеется, что это помогает

http://jsfiddle.net/mwa4G/

http://en.literateprograms.org/Quicksort_(JavaScript)

Answer 3

для цикла внутри функции Partition должна быть записана в виде:

for (var j = first_index; j < last_index; j++) {...}

вместо

for (var j = 0; j < arr.length-1; j++) {...}

петлей с 0 к arr.length-1 делает его создавать новые элементы внутри исходного массива, а не только их замену.