Ответ 1

Вы можете легко "стабилизировать" неустойчивый вид, используя узор украшать-сортировать-undecorate

function stableSort(v, f)
{
    if (f === undefined) {
        f = function(a, b) {
            a = ""+a; b = ""+b;
            return a < b ? -1 : (a > b ? 1 : 0);
        }
    }
    var dv = [];
    for (var i=0; i<v.length; i++) {
        dv[i] = [v[i], i];
    }
    dv.sort(function(a, b){
              return f(a[0], b[0]) || (a[1] - b[1]);
            });
    for (var i=0; i<v.length; i++) {
        v[i] = dv[i][0];
    }
}

Идея состоит в том, чтобы добавить индекс в качестве последнего члена сортировки, чтобы ни один из двух элементов не был теперь "тем же", и если все остальное будет одинаковым, то исходным индексом будет определяющий фактор.

Ответ 2

• Поместите объекты в массив.

• Вызвать Array.sort(). Это очень быстро.

  var array = [3,7,2,8,2,782,7,29,1,3,0,34];
  array.sort();
  console.log(array); // prints [0, 1, 2, 2, 29, 3, 3, 34, 7, 7, 782, 8]
  

Почему эта печать выполняется в лексикографическом порядке? Это как Array.sort() работает по умолчанию, например. , если вы не предоставляете функцию компаратора.. Исправьте это.

    var array = [3,7,2,8,2,782,7,29,1,3,0,34];
    array.sort(function (a, b)
    {
        return a-b;
    });
    console.log(array); // prints [0, 1, 2, 2, 3, 3, 7, 7, 8, 29, 34, 782]

Ответ 3

Quicksort (рекурсивный)

function quicksort(array) {
  if (array.length <= 1) {
    return array;
  }

  var pivot = array[0];
  
  var left = []; 
  var right = [];

  for (var i = 1; i < array.length; i++) {
    array[i] < pivot ? left.push(array[i]) : right.push(array[i]);
  }

  return quicksort(left).concat(pivot, quicksort(right));
};

var unsorted = [23, 45, 16, 37, 3, 99, 22];
var sorted = quicksort(unsorted);

console.log('Sorted array', sorted);

Ответ 4

Функциональный эквивалент

В праздновании функционального Javascript, который, кажется, в вещи

на данный момент, особенно учитывая ES6+ замечательные синтаксические добавления сахара. Функции стрелок и деструктуризация Я предлагаю очень чистый, короткий функциональный эквивалент функции быстрой сортировки. Я не проверял его на производительность и не сравнивал его со встроенной функцией быстрой сортировки, но он может помочь тем, кто пытается понять практическое использование быстрой сортировки. Учитывая его декларативный характер, очень легко увидеть, что происходит, в отличие от того, как это работает.

Вот версия JSBin без комментариев https://jsbin.com/zenajud/edit?js,console

function quickSortF(arr) {
    // Base case
    if (!arr.length) return []

    // This is a ES6 addition, it uses destructuring to pull out the 
    // first value and the rest, similar to how other functional languages
    // such as Haskell, Scala do it. You can then use the variables as 
    // normal below
    const [head, ...tail] = arr,
          // here we are using the arrow functions, and taking full 
          // advantage of the concise syntax, the verbose version of
          // function(e) => { return e < head } is the same thing
          // so we end up with the partition part, two arrays,
          // one smaller than the pivot and one bigger than the 
          // pivot, in this case is the head variable
          left = tail.filter( e => e < head),
          right = tail.filter( e => e >= head)

       // this is the conquer bit of divide-and-conquer
       // recursively run through each left and right array
       // until we hit the if condition which returns an empty
       // array. These results are all connected using concat,
       // and we get our sorted array.
       return quickSortF(left).concat(head, quickSortF(right))           

}

const q7 = quickSortF([11,8,14,3,6,2,7]) 
//[2, 3, 6, 7, 8, 11, 14]
const q8 =  quickSortF([11,8,14,3,6,2,1, 7])
//[1, 2, 3, 6, 7, 8, 11, 14]
const q9 = quickSortF([16,11,9,7,6,5,3, 2])
//[2, 3, 5, 6, 7, 9, 11, 16]

console.log(q7,q8,q9)

Комментариев должно быть достаточно, если уже не ясно, что происходит. Фактический код очень короткий без комментариев, и вы, возможно, заметили, что я не фанат точки с запятой. :)

Ответ 5

В этом блоге http://www.nczonline.net/blog/2012/11/27/computer-science-in-javascript-quicksort/, который указал, что Array.sort реализован в сортировке quicksort или merge.

Quicksort обычно считается эффективным и быстрым, и используемый V8 как реализация для Array.prototype.sort() для массивов с более чем 23 пунктами. Для менее чем 23 элементов, V8 использует вставку сортировать по [2]. Сортировка слияний является конкурентом быстрой сортировки, так как это также эффективным и быстрым, но имеет дополнительное преимущество быть стабильным. Это почему Mozilla и Safari используют его для Array.prototype.sort,().

и при использовании Array.sort вы должны вернуть -1 0 1 вместо true или false в Chrome.

arr.sort(function(a,b){
  return a<b;
});
// maybe--> [21, 0, 3, 11, 4, 5, 6, 7, 8, 9, 10, 1, 2, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22]
arr.sort(function(a,b){
  return a > b ? -1 : a < b ? 1 : 0;
});
// --> [22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

Ответ 6

var array = [8, 2, 5, 7, 4, 3, 12, 6, 19, 11, 10, 13, 9];
quickSort(array, 0, array.length -1);
document.write(array);


function  quickSort(arr, left, right)
{
	var i = left;
	var j = right;
	var tmp;
	pivotidx = (left + right) / 2; 
	var pivot = parseInt(arr[pivotidx.toFixed()]);  
	/* partition */
	while (i <= j)
	{
		while (parseInt(arr[i]) < pivot)
		i++;
		while (parseInt(arr[j]) > pivot)
			j--;
		if (i <= j)
		{
			tmp = arr[i];
			arr[i] = arr[j];
			arr[j] = tmp;
			i++;
			j--;
		}
	}

	/* recursion */
	if (left < j)
		quickSort(arr, left, j);
	if (i < right)
		quickSort(arr, i, right);
	return arr;
}

Ответ 7

Используя ES6 rest, выкладывайте:

smaller = (a, list) => list.filter(x => x <= a)
larger = (a, list) => list.filter(x => x > a)
qsort = ([x, ...list]) => (!isNaN(x))
    ? [...qsort(smaller(x, list)), x, ...qsort(larger(x, list))]
    : []

Ответ 8

Этот алгоритм работает почти так же быстро, как реализация по умолчанию of Array.prototype.sort в хром.

function quickSort(t){
    _quickSort(t,0,t.length-1,0,t.length-1);
}

function _quickSort(t, s, e, sp, ep){   
    if( s>=e )  return;
    while( sp<ep && t[sp]<t[e] ) sp++;  
    if( sp==e )
        _quickSort(t,s,e-1,s,e-1);  
    else{
        while(t[ep]>=t[e] && sp<ep ) ep--;      
        if( sp==ep ){
            var temp = t[sp];
            t[sp] = t[e];
            t[e] = temp;
            if( s!=sp ){
                _quickSort(t,s,sp-1,s,sp-1);
            }
            _quickSort(t,sp+1,e,sp+1,e);            
        }else{
            var temp = t[sp];
            t[sp] = t[ep];
            t[ep] = temp;
            _quickSort(t,s,e,sp+1,ep);
        }
    }
}

время быстрой сортировки (мс): 738
javaScriptSort time (ms): 603

var m = randTxT(5000,500,-1000,1000);
VS(m);

function VS(M){
    var t;
    t = Date.now();
    for(var i=0;i<M.length;i++){
        quickSort(M[i].slice());
    }console.log("quickSort time (ms): "+(Date.now()-t));

    t = Date.now();
    for(var i=0;i<M.length;i++){
        M[i].slice().sort(compare);
    }console.log("javaScriptSort time (ms): "+(Date.now()-t));
}

function compare(a, b) {
    if( a<b )
        return -1;
    if( a==b )
        return 0;
    return 1;
}

function randT(n,min,max){
    var res = [], i=0;
    while( i<n ){
        res.push( Math.floor(Math.random()*(max-min+1)+min) );
        i++;
    }
    return res; 
}
function randTxT(n,m,min,max){
    var res = [], i=0;
    while( i<n ){
        res.push( randT(m,min,max) );
        i++;
    }
    return res; 
}

Ответ 9

Еще одна демонстрация быстрой сортировки, которая занимает середину массива как ось вращения без какой-либо конкретной причины.

const QuickSort = function (A, start, end) {
    // 
    if (start >= end) {
        return;
    }
    // return index of the pivot
    var pIndex = Partition(A, start, end);
    // partition left side
    QuickSort(A, start, pIndex - 1);
    // partition right side
    QuickSort(A, pIndex + 1, end);
}

const Partition = function (A, start, end) {
    if (A.length > 1 == false) {
        return 0;
    }
    let pivotIndex = Math.ceil((start + end) / 2);
    let pivotValue = A[pivotIndex];
    for (var i = 0; i < A.length; i++) {
        var leftValue = A[i];
        // 
        if (i < pivotIndex) {
            if (leftValue > pivotValue) {
                A[pivotIndex] = leftValue;
                A[i] = pivotValue;
                pivotIndex = i;
            }
        }
        else if (i > pivotIndex) {
            if (leftValue < pivotValue) {
                A[pivotIndex] = leftValue;
                A[i] = pivotValue;
                pivotIndex = i;
            }
        }
    }
    return pivotIndex;

}

const QuickSortTest = function () {
    const arrTest = [3, 5, 6, 22, 7, 1, 8, 9];
    QuickSort(arrTest, 0, arrTest.length - 1);
    console.log("arrTest", arrTest);
}
// 
QuickSortTest();

Ответ 10

Это оно !!!

function typeCheck(a, b){
  if(typeof a === typeof b){
    return true;
  }else{
    return false;
  }
}

function qSort(arr){
  if(arr.length === 0){
    return [];
  }

  var leftArr = [];
  var rightArr = [];
  var pivot = arr[0];

  for(var i = 1; i < arr.length; i++){
    if(typeCheck(arr[i], parseInt(0))){
      if(arr[i] < pivot){
        leftArr.push(arr[i]);
      }else { rightArr.push(arr[i]) } 
    }else{
      throw new Error("All must be integers");
    }
  }

  return qSort(leftArr).concat(pivot, qSort(rightArr));

}

var test = [];

for(var i = 0; i < 10; i++){
  test[i] = Math.floor(Math.random() * 100 + 2);
}

console.log(test);
console.log(qSort(test));

Ответ 11

Быстрая сортировка (ES6)

function quickSort(arr) {
    if (arr.length < 2) {
        return arr;
    }
    const pivot = arr[Math.floor(Math.random() * arr.length)];

    let left = [];
    let right = [];
    let equal = [];

    for (let val of arr) {
        if (val < pivot) {
            left.push(val);
        } else if (val > pivot) {
            right.push(val);
        } else {
            equal.push(val);
        }
    }
    return [
        ...quickSort(left),
        ...equal,
        ...quickSort(right)
    ];
}

Несколько заметок:

• Случайный поворот сохраняет эффективность алгоритма даже при сортировке данных.
• Как бы ни было приятно использовать Array.filter вместо цикла for of, как некоторые ответы здесь, это увеличит временную сложность (хотя вместо этого можно использовать Array.reduce).

Ответ 12

Тонкая версия:

function swap(arr,a,b){
    let temp = arr[a]
    arr[a] = arr[b]
    arr[b] = temp
    return 1
}

function qS(arr, first, last){
    if(first > last) return

    let p = first
    for(let i = p; i < last; i++)
        if(arr[i] < arr[last]) 
            p += swap(arr, i, p)

    swap(arr, p, last)

    qS(arr, first, p - 1)
    qS(arr, p + 1, last)
}

Проверено со случайными значениями Arrays и, кажется, всегда быстрее, чем Array.sort()

Ответ 13

Как насчет этого не мутирующего функционала QuickSort:

const quicksort = (arr, comp, iArr = arr) => {
  if (arr.length < 2) {
    return arr;
  }
  const isInitial = arr.length === iArr.length;
  const arrIndexes = isInitial ? Object.keys(arr) : arr;
  const compF = typeof comp === 'function'
  ? comp : (left, right) => left < right ? -1 : right < left ? 1 : 0;
  const [pivotIndex, ...indexesSansPivot] = arrIndexes;
  const indexSortReducer = isLeftOfPivot => [
    (acc, index) => isLeftOfPivot === (compF(iArr[index], iArr[pivotIndex]) === -1)
    ? acc.concat(index) : acc,
    []
  ];
  const ret = quicksort(indexesSansPivot.reduce(...indexSortReducer(true)), compF, iArr)
  .concat(pivotIndex)
  .concat(quicksort(indexesSansPivot.reduce(...indexSortReducer(false)), compF, iArr));
  return isInitial ? ret.reduce((acc, index) => acc.concat([arr[index]]), []) : ret;
};

В качестве бонуса, он поддерживает опциональную функцию сравнения, которая позволяет сортировать массив объектов по свойствам/свойствам и не замедляется при работе с большими значениями/объектами.

Сначала быстро сортирует исходные ключи массива, затем возвращает отсортированную копию исходного массива.