@H_502_0@javascript数据结构与算法--高级排序算法（快速排序法，希尔排序法）
@H_
502_0@
一、快速排序算法
<div class="cnblogs_code">
函数首先检查数组的长度是否为0。如果是，那么这个数组就不需要任何排序，函数直接返回。
* 否则，创建两个数组，一个用来存放比基准值小的元素，另一个用来存放比基准值大的元素。
* 这里的基准值取自数组的第一个元素。
* 接下来，这个函数对原始数组的元素进行遍历，根据它们与基准值的关系将它们放到合适的数组中。
* 然后对于较小的数组和较大的数组分别递归调用这个函数。
* 当递归结束时，再将较大的数组和较小的数组连接起来，形成最终的有序数组并将结果返回。
*
(arr.length == 0 left = [];
right = [];
pivot = arr[0 ( i = 1; i < arr.length; i++ (arr[i] < a = ( i = 0; i < 10; ++= Math.floor((Math.random()*100)+1
console.log("排序前： "+"排序后： "+qSort(a));
.dataStore =.pos = 0;
.numElements = numElements;
.insert = insert;方法
.toString = toString;显示数组中所有元素
.clear = clear;
.setData = setData;生成了存储在数组中的随机数字
.gaps = gaps;
.shellSort = shellSort;
<span style="color: #008000;">/*</span><span style="color: #008000;">将传入的数组，存储在datastore中</span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">for</span> (<span style="color: #0000ff;">var</span> i = 0; i < numElements.length; ++<span style="color: #000000;">i) {
</span><span style="color: #0000ff;">this</span>.dataStore[i] =<span style="color: #000000;"> numElements[i];
}
}
<span style="color: #0000ff;">function<span style="color: #000000;"> setData() {
<span style="color: #0000ff;">for (<span style="color: #0000ff;">var i = 0; i < <span style="color: #0000ff;">this.numElements; ++<span style="color: #000000;">i) {
<span style="color: #0000ff;">this.dataStore[i] = Math.floor(Math.random() *<span style="color: #000000;">
(<span style="color: #0000ff;">this.numElements+1<span style="color: #000000;">));
}
}
<span style="color: #0000ff;">function<span style="color: #000000;"> clear() {
<span style="color: #0000ff;">for (<span style="color: #0000ff;">var i = 0; i < <span style="color: #0000ff;">this.dataStore.length; ++<span style="color: #000000;">i) {
<span style="color: #0000ff;">this.dataStore[i] = 0<span style="color: #000000;">;
}
}
<span style="color: #0000ff;">function<span style="color: #000000;"> insert(element) {
<span style="color: #0000ff;">this.dataStore[<span style="color: #0000ff;">this.pos++] =<span style="color: #000000;"> element;
}
<span style="color: #0000ff;">function<span style="color: #000000;"> toString() {
<span style="color: #0000ff;">var retstr = ""<span style="color: #000000;">;
<span style="color: #0000ff;">for (<span style="color: #0000ff;">var i = 0; i < <span style="color: #0000ff;">this.dataStore.length; ++<span style="color: #000000;">i) {
retstr += <span style="color: #0000ff;">this.dataStore[i] + " "<span style="color: #000000;">;
<span style="color: #0000ff;">if (i > 0 && i % 10 == 0<span style="color: #000000;">) {
retstr += "\n"<span style="color: #000000;">;
}
}
<span style="color: #0000ff;">return<span style="color: #000000;"> retstr;
}
<span style="color: #008000;">/*<span style="color: #008000;">
- 外循环控制间隔序列的移动。也就是说，算法在第一次处理数据集时，会检查所有间隔为5的元素。
- 下一次遍历会检查所有间隔为3的元素。
- 最后一次则会对间隔为1的元素，也就是相邻元素执行标准插入排序。
- 在开始做最后一次处理时，大部分元素都将在正确的位置，算法就不必对很多元素进行交换。
- 这就是希尔排序比插入排序更高效的地方。
- <span style="color: #008000;">*/
<span style="color: #0000ff;">function<span style="color: #000000;"> shellSort() {
console.log("排序前"+": "+<span style="color: #000000;">myNums.toString());
<span style="color: #0000ff;">for(<span style="color: #0000ff;">var g = 0; g < <span style="color: #0000ff;">this.gaps.length; ++<span style="color: #000000;">g) {
<span style="color: #0000ff;">for(<span style="color: #0000ff;">var i = <span style="color: #0000ff;">this.gaps[g]; i < <span style="color: #0000ff;">this.dataStore.length; ++<span style="color: #000000;">i) {
<span style="color: #0000ff;">var temp = <span style="color: #0000ff;">this<span style="color: #000000;">.dataStore[i];
<span style="color: #0000ff;">for(<span style="color: #0000ff;">var j = i; j >= <span style="color: #0000ff;">this.gaps[g] && <span style="color: #0000ff;">this.dataStore[j - <span style="color: #0000ff;">this.gaps[g]] > temp; j -= <span style="color: #0000ff;">this<span style="color: #000000;">.gaps[g]) {
<span style="color: #0000ff;">this.dataStore[j] = <span style="color: #0000ff;">this.dataStore[j - <span style="color: #0000ff;">this<span style="color: #000000;">.gaps[g]];
}
<span style="color: #0000ff;">this.dataStore[j] =<span style="color: #000000;"> temp;
<span style="color: #008000;">//<span style="color: #008000;"> console.log(g+"--"+i+": "+myNums.toString());
<span style="color: #000000;"> }
console.log(g+": "+<span style="color: #000000;">myNums.toString());
}
}
<span style="color: #008000;">//<span style="color: #008000;"> 希尔排序测试代码
<span style="color: #0000ff;">var numElements = [0,9,1,8,7,6,2,3,5,4<span style="color: #000000;">];
<span style="color: #0000ff;">var gaps = [3,1<span style="color: #000000;">];
<span style="color: #0000ff;">var myNums = <span style="color: #0000ff;">new<span style="color: #000000;"> CArray(numElements,gaps);
myNums.shellSort();
console.log("排序后"+": "+myNums.toString());
