常见的排序算法总结（JavaScript）(4)

　　

平均时间复杂度   最优时间复杂度   最差时间复杂度   空间复杂度  
O(nLogn)   O(nLogn)   O(n^2)   O(1)  

 

1 function quickSort (arr) { 2 function sort(array, first, last) { 3 if (first >= last) { 4 return; 5 } 6 var base = Math.floor((first + last) / 2); 7 var i = first - 1; 8 var j = last - 1; 9 var temp; 10 while (j > i) { 11 while (j > i && array[j] > array[base]) { 12 j--; 13 } 14 while (i < j && array[i] <= array[base]) { 15 i++; 16 } 17 temp = array[i]; 18 array[i] = array[j]; 19 array[j] = temp; 20 } 21 temp = array[base]; 22 array[base] = array[i]; 23 array[i] = temp; 24 sort(array, first, i); 25 sort(array, i + 2, last) 26 } 27 sort(arr, 1, arr.length); 28 }

　　在这里我们 JavaScript 描绘出快速排序的过程：

var interval = 500;
function nodesGenerator(n) {
 var frame = document.getElementById("frame");
 for (var i = 0; i < n; i++) {
  var node = document.createElement("div");
  node.setAttribute("class", "node");
  node.style.height = (Math.floor(Math.random() * 250) + 1) + "px";
  frame.appendChild(node);
 }
}
nodesGenerator(400);

function domQuickSort(array, first, last) {
 if (first >= last) {
  return;
 }
 var base = parseInt(array[first - 1].style.height.match(/\d+/));
 var i = first - 1;
 var j = last - 1;
 var temp;
 while (j > i) {
  while (j > i && parseInt(array[j].style.height.match(/\d+/)) > base) {
   j--;
  }
  while (i < j && parseInt(array[i].style.height.match(/\d+/)) <= base) {
   i++;
  }
  temp = array[i].style.height;
  array[i].style.height = array[j].style.height;
  array[j].style.height = temp;
 }
 temp = array[first - 1].style.height;
 array[first - 1].style.height = array[i].style.height;
 array[i].style.height = temp;
 setTimeout(function(argument) {
  domQuickSort(array, first, i);
 }, interval);
 setTimeout(function(argument) {
  domQuickSort(array, i + 2, last)
 }, interval);
}
setTimeout(function (argument) {
 domQuickSort(document.getElementsByClassName("node"), 1, document.getElementsByClassName("node").length);
}, interval);