快速排序

Question

这个还没学过
看了下还没看懂  虽然还是得试着下
还是希望各位前辈们写一个
我好对着参考参考 谢谢......................
(ps:我希望的是最基本的快速排序  关键数据为array[0])

Answer 1

给你一个最基本关于数组元素的排序。<SCRIPT LANGUAGE="JavaScript">
<!--
var arr=[9,2,5,4,3,1,0];
function c(a,b){return a-b;}
document.write(arr.sort(c));
//-->
</SCRIPT>

Answer 2

js冒泡排序不知能帮到你的忙：<script language="javascript">
　　var DataOne=new Array(5,3,7,8,3,1,2,0,100)
　　var len=DataOne.length
　　for(var i=0;i<len;i++)
　　{
　　for(var j=0;j<len;j++)
　　{
　　One=DataOne[j]
　　Two=DataOne[j+1]
　　if(One<Two)
　　{
　　DataOne[j]=Two
　　DataOne[j+1]=One
　　}
　　}
　　}
　　var str=""
　　for(var n=0;n<len;n++)
　　{
　　str+=DataOne[n]+","
　　}
　　alert(str)
　　</script>

Answer 3

function InsertSort(arr) { //插入排序->直接插入法排序   
  
  var st = new Date();   
  
  var temp, j;   
  
  for(var i=1; i<arr.length; i++) {   
  
   if((arr[i]) < (arr[i-1])) {   
  
    temp = arr[i];   
  
    j = i-1;   
  
    do {   
  
     arr[j+1] = arr[j];   
  
     j--;   
  
    }   
  
    while (j>-1 && (temp) < (arr[j]));   
  
    arr[j+1] = temp;   
  
   }//endif   
  
  }   
  
  status = (new Date() - st) + ' ms';   
  
  return arr;   
  
 }   
  
  
  
  
  
 function ShellSort(arr) { //插入排序->希儿排序   
  
  var st = new Date();   
  
  var increment = arr.length;   
  
  do {   
  
   increment = (increment/3|0) + 1;   
  
   arr = ShellPass(arr, increment);   
  
  }   
  
  while (increment > 1)   
  
  
  
  status = (new Date() - st) + ' ms';   
  
  return arr;   
  
 }   
  
 function ShellPass(arr, d) { //希儿排序分段执行函数   
  
  var temp, j;   
  
  for(var i=d; i<arr.length; i++) {   
  
   if((arr[i]) < (arr[i-d])) {   
  
    temp = arr[i]; j = i-d;   
  
    do {   
  
     arr[j+d] = arr[j];   
  
     j = j-d;   
  
    }   
  
    while (j>-1 && (temp) < (arr[j]));   
  
    arr[j+d] = temp;   
  
   }//endif   
  
  }   
  
  return arr;   
  
 }   
  
  
  
  
  
 function BubbleSort(arr) { //交换排序->冒泡排序   
  
  var st = new Date();   
  
  var temp;   
  
  var exchange;   
  
  for(var i=0; i<arr.length; i++) {   
  
   exchange = false;   
  
   for(var j=arr.length-2; j>=i; j--) {   
  
    if((arr[j+1]) < (arr[j])) {   
  
     temp = arr[j+1];   
  
     arr[j+1] = arr[j];   
  
     arr[j] = temp;   
  
     exchange = true;   
  
    }   
  
   }   
  
   if(!exchange) break;   
  
  }   
  
  status = (new Date() - st) + ' ms';   
  
  return arr;   
  
 }   
  
  
  
 function QuickSortDemo(arr) {   
  
  var st = new Date();   
  
  var result = QuickSort(arr);   
  
  status = (new Date() - st) + ' ms';   
  
  return result;   
  
 }    
  
  
  
 function QuickSort(arr) { //交换排序->快速排序   
  
  if (arguments.length>1) {   
  
   var low = arguments[1];   
  
   var high = arguments[2];   
  
  } else {   
  
   var low = 0;   
  
   var high = arr.length-1;   
  
  }   
  
  if(low < high){   
  
   // function Partition   
  
   var i = low;   
  
   var j = high;   
  
   var pivot = arr[i];   
  
   while(i<j) {   
  
    while(i<j && arr[j]>=pivot)   
  
     j--;   
  
    if(i<j)   
  
     arr[i++] = arr[j];   
  
    while(i<j && arr[i]<=pivot)   
  
     i++;   
  
    if(i<j)   
  
     arr[j--] = arr[i];   
  
   }//endwhile   
  
   arr[i] = pivot;   
  
   // end function   
  
   var pivotpos = i; //Partition(arr，low，high);   
  
   QuickSort(arr, low, pivotpos-1);   
  
   QuickSort(arr, pivotpos+1, high);   
  
  } else  
  
   return;   
  
   return arr;   
  
 }   
  
    
  
 /*function Partition(arr, i, j) { //快速排序, 对待排序的数组进行划分  
 
  var pivot = arr[i];  
 
  while(i<j) {  
 
   while(arr[j]>=pivot)  
 
    j--;  
 
   if(i<j)  
 
    arr[i++] = arr[j];  
 
   while(arr[i]<=pivot)  
 
    i++;  
 
   if(i<j)  
 
    arr[j--] = arr[i];  
 
  }  
 
  arr[i] = pivot;  
 
  return arr;  
 
 }*/  
  
  
  
 function SelectSort(arr) { //选择排序->直接选择排序   
  
  var st = new Date();   
  
  var temp;   
  
  for(var i=0; i<arr.length; i++) {   
  
   var k = i;   
  
   for(var j=i+1; j<arr.length; j++) {   
  
    if((arr[j]) < (arr[k]))   
  
     k = j;   
  
   }   
  
   if (k != i){   
  
    temp = arr[i];   
  
    arr[i] = arr[k];   
  
    arr[k] = temp;   
  
   }   
  
  }   
  
  status = (new Date() - st) + ' ms';   
  
  return arr;   
  
 }   
  
    
  
  
  
 function unicode(str) {//求字符串的unicode码   
  
  var uni=0;   
  
  for(var i=0; i<str.length; i++){   
  
   uni += str.charCodeAt(i)/6553.5 * Math.pow(10, str.length-i);   
  
  }   
  
  return uni;   
  
 }   
  
</script>  

Answer 4

function quickSort(array,start,end) {   
    if(start < end) {
         var s = start;
         var e = end + 1;
         var temp = array[s][1];
         var temp0 = array[s][0];
         while(1) {
              while((++s)<=end && array[s][1] > temp);
              while((--e)>=start && array[e][1] < temp);
              if(s > e) {
                   break;
              }
              var tem = array[s][1];
              array[s][1] = array[e][1];
              array[e][1] = tem;
              tem = array[s][0];
              array[s][0] = array[e][0];
              array[e][0] = tem;
        }
        array[start][1] = array[e][1];
        array[e][1] = temp;
        array[start][0] = array[e][0];
        array[e][0] = temp0;
        quickSort(array,start,e-1);
        quickSort(array,e+1,end);
    }
}

Answer 5

js里面不是有个sort么？
话说在解释型脚本里面用其他排序，效率也高不到哪里去

Answer 6

sort 是可以 但是也得看场合用
如果你在面试  考官要你用快速排序去排一个数组 
你去用sort   那你可以直接喀擦掉了to unicode 这个例子 我在网上看到过 首先没看懂  其次他连返回直都没有 那该如何测试了to ws_hgo 这个写法跟网上的说法很象  但是我始终不能得到正确的测试数据 
如 Partition([1,2,3,4,5,6,7,8],0,7)  返回结果是正确的吗???

Answer 7

<html>
<head><title>quicksort demo</title></head>
<body>
<script>
function quicksort(arr, low, high) {
low = typeof low == "undefined" ? 0 : low;
high = typeof high == "undefined" ? arr.length - 1 : high;
if (low >= high) return;
var i = low, j = high;
var pivot = arr[Math.floor((low + high) / 2)]; while (i <= j) {
while (arr[i] < pivot) i++;
while (arr[j] > pivot) j--;
if (i <= j) {
var t = arr[i];
arr[i] = arr[j];
arr[j] = t;
i++;
j--;
}
}
if (low < j) arguments.callee(arr, low, j);
if (i < high) arguments.callee(arr, i, high);
}(function () {
var list0 = [];
var list1 = [];
var list2 = [];
for (var i = 0; i < 20; i++) {
var t = Math.floor(Math.random() * 100);
list0.push(t);
list1.push(t);
list2.push(t);
}
quicksort(list1);
list2.sort();
alert("list0:" + list0 + "\r\nlist1:" + list1 + "\r\nlist2:" + list2);
})();
</script>
</body>
</html>系统默认是按字符串排序，所有对比有些情况会不一样。

Answer 8

<script>
function QuickSort_Once(_pnArray, _pnLow, _pnHigh) {
// 首先将首元素做为枢轴
var nPivot = _pnArray[_pnLow];
var i = _pnLow, j = _pnHigh; // 设置两个指针,分别指向首尾处
while(i < j) {  // 直到两个指针重合
// 从右向左,寻找首个小于枢轴的元素
while(_pnArray[j] >= nPivot && i < j) j--;
_pnArray[i] = _pnArray[j];   // 找到后 执行替换 // 从左到右,寻找首个大于枢轴的元素
while(_pnArray[i] <= nPivot && i < j) i++;
_pnArray[j] = _pnArray[i];   // 找到后 执行替换
}
// 至此i,j两指针重合执行同一位置,i即是新的枢轴位置
_pnArray[i] = nPivot;
return i;
}
function QuickSort(_pnArray, _pnLow, _pnHigh) {
if(_pnLow >= _pnHigh) return;
// 获取枢轴
var _nPivotIndex = QuickSort_Once(_pnArray, _pnLow, _pnHigh);
// 然后对被枢轴分开的两侧进行分别递归
QuickSort(_pnArray, _pnLow, _nPivotIndex - 1);
QuickSort(_pnArray,  _nPivotIndex + 1, _pnHigh);
}/* 排序测试 */
(function() {
// 10个随机数
var arr = [];
for(var i = 0; i < 10; i++) {
arr[i] = Math.floor(Math.random() * 60);
}
document.write('初始值: ' + arr + '<br/>');
QuickSort(arr, 0, arr.length - 1);
document.write('排序值: ' + arr);
})();
</script>

Answer 9

<script type="text/javascript">var arr = new Array(6)
arr[0] = "10"
arr[1] = "5"
arr[2] = "40"
arr[3] = "25"
arr[4] = "1000"
arr[5] = "1"document.write(arr + "<br />")
document.write(arr.sort())</script>输出：10,5,40,25,1000,1
1,10,1000,25,40,5请注意，上面的代码没有按照数值的大小对数字进行排序，要实现这一点，就必须使用一个排序函数：<script type="text/javascript">function sortNumber(a,b)
{
return a - b
}var arr = new Array(6)
arr[0] = "10"
arr[1] = "5"
arr[2] = "40"
arr[3] = "25"
arr[4] = "1000"
arr[5] = "1"document.write(arr + "<br />")
document.write(arr.sort(sortNumber))</script>输出：10,5,40,25,1000,1
1,5,10,25,40,1000