选择排序js?
发布网友
发布时间：2024-09-26 16:49
共1个回答
热心网友
时间：2024-10-28 05:26
原理：比较两个相邻的元素，将值大的元素交换至右端。
思路：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复第一趟步骤，直至全部排序完成。
N个数字要排序完成，总共进行N-1趟排序，每i趟的排序次数为(N-i)次，所以可以用双重循环语句，外层控制循环多少趟，内层控制每一趟的循环次数。
冒泡排序的优点：每进行一趟排序，就会少比较一次，因为每进行一趟排序都会找出一个较大值。如上例：第一趟比较之后，排在最后的一个数一定是最大的一个数，第二趟排序的时候，只需要比较除了最后一个数以外的其他的数，同样也能找出一个最大的数排在参与第二趟比较的数后面，第三趟比较的时候，只需要比较除了最后两个数以外的其他的数，以此类推……也就是说，没进行一趟比较，每一趟少比较一次，一定程度上减少了算法的量。
冒泡排序优化版：
一.选择排序原理
1.每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置
2.再从剩余未排序元素中继续寻找最小（大）元素，然后放到刚才已排序序列的后面。
3.以此类推，直到全部待排序的数据元素排完。
选择排序是不稳定的排序方法。例如：序列3，3，2，1，我们知道第一次遍历的时候，选择最后一个元素1和第一个元素3交换，那么原序列中2个3的相对前后顺序就和之前不一样了，所以选择排序不是一个稳定的排序算法。
二.选择排序时间复杂度
第一次循环比较n-1次，第二次循环比较n-2次，依次类推，最后一个元素不需要比较，因此共进行n-1次循环，最后一次循环比较1次。
因此一共比较1+2+3+...+（n-2）+（n-1）次，求和得n2/2-n/2，忽略系数，取最高指数项，该排序的时间复杂度为O(n2)
选择排序优化版：
插入排序：
JS常见排序算法排序算法说明:
（1）对于评述算法优劣术语的说明
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
内排序：所有排序操作都在内存中完成；
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
时间复杂度:一个算法执行所耗费的时间。
空间复杂度:运行完一个程序所需内存的大小。
(2)排序算法图片总结:
1.冒泡排序:
解析：1.比较相邻的两个元素，如果前一个比后一个大，则交换位置。
2.第一轮的时候最后一个元素应该是最大的一个。
3.按照步骤一的方法进行相邻两个元素的比较，这个时候由于最后一个元素已经是最大的了，所以最后一个元素不用比较。
2.快速排序:
解析：快速排序是对冒泡排序的一种改进，第一趟排序时将数据分成两部分，一部分比另一部分的所有数据都要小。然后递归调用，在两边都实行快速排序。
3.插入排序:
解析：
?（1）?从第一个元素开始，该元素可以认为已经被排序
?（2）取出下一个元素，在已经排序的元素序列中从后向前扫描
?（3）如果该元素（已排序）大于新元素，将该元素移到下一位置
?（4）重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
?（5）将新元素插入到下一位置中
?（6）重复步骤2
2.二分查找:
解析：二分查找，也为折半查找。首先要找到一个中间值，通过与中间值比较，大的放又，小的放在左边。再在两边中寻找中间值，持续以上操作，直到找到所在位置为止。
（1）递归方法
（2）非递归方法
4.选择排序:
解析:首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
以此类推，直到所有元素均排序完毕。
5.希尔排序:
解析:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序
6.归并排序:
解析:归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
7.堆排序:
解析:堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是
小于（或者大于）它的父节点。
8.计数排序:
?解析:计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。
9.桶排序:
解析:假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排
10.基数排序:
解析:基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优
先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。
基数排序vs计数排序vs桶排序
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
基数排序：根据键值的每位数字来分配桶计数排序：每个桶只存储单一键值桶排序：每个桶存储一定范围的数值
用JS实现排序的功能js常用排序实现，参考代码如下
script?
Array.prototype.swap?=?function(i,?j)?
{?
var?temp?=?this[i];?
this[i]?=?this[j];?
this[j]?=?temp;?
}?
Array.prototype.bubbleSort?=?function()?
{?
for?(var?i?=?this.length?-?1;?i??0;?--i)?
{?
for?(var?j?=?0;?j??i;?++j)?
{?
if?(this[j]??this[j?+?1])?this.swap(j,?j?+?1);?
}?
}?
}?
Array.prototype.selectionSort?=?function()?
{?
for?(var?i?=?0;?i??this.length;?++i)?
{?
var?index?=?i;?
for?(var?j?=?i?+?1;?j??this.length;?++j)?
{?
if?(this[j]??this[index])?index?=?j;?
}?
this.swap(i,?index);?
}?
}?
Array.prototype.insertionSort?=?function()?
{?
for?(var?i?=?1;?i??this.length;?++i)?
{?
var?j?=?i,?value?=?this[i];?
while?(j??0??this[j?-?1]??value)?
{?
this[j]?=?this[j?-?1];?
--j;?
}?
this[j]?=?value;?
}?
}?
Array.prototype.shellSort?=?function()?
{?
for?(var?step?=?this.length??1;?step??0;?step?=?1)?
{?
for?(var?i?=?0;?i??step;?++i)?
{?
for?(var?j?=?i?+?step;?j??this.length;?j?+=?step)?
{?
var?k?=?j,?value?=?this[j];?
while?(k?=?step??this[k?-?step]??value)?
{?
this[k]?=?this[k?-?step];?
k?-=?step;?
}?
this[k]?=?value;?
}?
}?
}?
}?
Array.prototype.quickSort?=?function(s,?e)?
{?
if?(s?==?null)?s?=?0;?
if?(e?==?null)?e?=?this.length?-?1;?
if?(s?=?e)?return;?
this.swap((s?+?e)??1,?e);?
var?index?=?s?-?1;?
for?(var?i?=?s;?i?=?e;?++i)?
{?
if?(this[i]?=?this[e])?this.swap(i,?++index);?
}?
this.quickSort(s,?index?-?1);?
this.quickSort(index?+?1,?e);?
}?
Array.prototype.stackQuickSort?=?function()?
{?
var?stack?=?[0,?this.length?-?1];?
while?(stack.length??0)?
{?
var?e?=?stack.pop(),?s?=?stack.pop();?
if?(s?=?e)?continue;?
this.swap((s?+?e)??1,?e);?
var?index?=?s?-?1;?
for?(var?i?=?s;?i?=?e;?++i)?
{?
if?(this[i]?=?this[e])?this.swap(i,?++index);?
}?
stack.push(s,?index?-?1,?index?+?1,?e);?
}?
}?
Array.prototype.mergeSort?=?function(s,?e,?b)?
{?
if?(s?==?null)?s?=?0;?
if?(e?==?null)?e?=?this.length?-?1;?
if?(b?==?null)?b?=?new?Array(this.length);?
if?(s?=?e)?return;?
var?m?=?(s?+?e)??1;?
this.mergeSort(s,?m,?b);?
this.mergeSort(m?+?1,?e,?b);?
for?(var?i?=?s,?j?=?s,?k?=?m?+?1;?i?=?e;?++i)?
{?
b[i]?=?this[(k??e?||?j?=?m??this[j]??this[k])???j++?:?k++];?
}?
for?(var?i?=?s;?i?=?e;?++i)?this[i]?=?b[i];?
}?
Array.prototype.heapSort?=?function()?
{?
for?(var?i?=?1;?i??this.length;?++i)?
{?
for?(var?j?=?i,?k?=?(j?-?1)??1;?k?=?0;?j?=?k,?k?=?(k?-?1)??1)?
{?
if?(this[k]?=?this[j])?break;?
this.swap(j,?k);?
}?
}?
for?(var?i?=?this.length?-?1;?i??0;?--i)?
{?
this.swap(0,?i);?
for?(var?j?=?0,?k?=?(j?+?1)??1;?k?=?i;?j?=?k,?k?=?(k?+?1)??1)?
{?
if?(k?==?i?||?this[k]??this[k?-?1])?--k;?
if?(this[k]?=?this[j])?break;?
this.swap(j,?k);?
}?
}?
}?
function?generate()?
{?
var?max?=?parseInt(txtMax.value),?count?=?parseInt(txtCount.value);?
if?(isNaN(max)?||?isNaN(count))?
{?
alert("个数和最大值必须是一个整数");?
return;?
}?
var?array?=?[];?
for?(var?i?=?0;?i??count;?++i)?array.push(Math.round(Math.random()?*?max));?
txtInput.value?=?array.join("\n");?
txtOutput.value?=?"";?
}?
function?demo(type)?
{?
var?array?=?txtInput.value?==?""???[]?:?txtInput.value.replace().split("\n");?
for?(var?i?=?0;?i??array.length;?++i)?array[i]?=?parseInt(array[i]);?
var?t1?=?new?Date();?
eval("array."?+?type?+?"Sort()");?
var?t2?=?new?Date();?
lblTime.innerText?=?t2.valueOf()?-?t1.valueOf();?
txtOutput.value?=?array.join("\n");?
}?
/script?
body?onload=generate()?
table?style="width:100%;height:100%;font-size:12px;font-family:宋体"?
tr?
td?align=right?
textarea?id=txtInput?readonly?style="width:100px;height:100%"/textarea?
/td?
td?width=150?align=center?
随机数个数input?id=txtCount?value=500?style="width:50px"brbr?
最大随机数input?id=txtMax?value=1000?style="width:50px"brbr?
button?onclick=generate()重新生成/buttonbrbrbrbr?
耗时(毫秒)：label?id=lblTime/labelbrbrbrbr?
button?onclick=demo("bubble")冒泡排序/buttonbrbr?
button?onclick=demo("selection")选择排序/buttonbrbr?
button?onclick=demo("insertion")插入排序/buttonbrbr?
button?onclick=demo("shell")谢尔排序/buttonbrbr?
button?onclick=demo("quick")快速排序(递归)/buttonbrbr?
button?onclick=demo("stackQuick")快速排序(堆栈)/buttonbrbr?
button?onclick=demo("merge")归并排序/buttonbrbr?
button?onclick=demo("heap")堆排序/buttonbrbr?
/td?
td?align=left?
textarea?id=txtOutput?readonly?style="width:100px;height:100%"/textarea?
/td?
/tr?
/table?
/body
