简单排序
冒泡排序
冒泡排序是最简单排序算法,时间复杂度为n的平方,代码如下:
function bubbleSort(array) {
for (var i = 0; i < array.length; i++) {
for (var j = array.length; j > 0; j--) {
if (array[j] < array[j - 1]) {
var temp = array[j - 1];
array[j - 1] = array[j];
array[j] = temp;
}
}
/* 输出结果 */
document.write("这是第 + (i + 1) + "次循环·,结果为:");
for (var k = 0; k < array.length; k++) {
document.write(array[k] + ",");
}
document.write("<br />");
/* 输出结果结束 */
}
}
直接插入排序
直接插入排序也属于简单排序算法,时间复杂度也为n的平方,但性能略好于冒泡排序,代码如下:
function insertSort(array) {
var temp;
for (var i = 1; i < array.length; i++) {
var temp = array[i];
for (var j = i; j > 0 && temp < array[j - 1]; j--) {
array[j] = array[j - 1];
}
array[j] = temp
/* 输出结果 */
document.write("第? + i + "遍排序的结果是:")
for (var n = 0; n < array.length; n++) {
document.write(array[n] + ",");
}
document.write("<br />")
/* 输出结果结束 */
}
}
选择排序[color=orange][/color]
选择排序也属于简单排序算法,时间复杂度也为n的平方,性能同样略微好于冒泡排序,代码如下:
function selectSort(array) {
var min, temp; ;
for (var i = 0; i < array.length; i++) {
min = i;
for (var j = i + 1; j < array.length; j++) {
if (array[min] > array[j])
min = j;
}
if (min != i) {
temp = array[i];
array[i] = array[min];
array[min] = temp;
}
/* 输出结果 */
document.write("第 + i + "遍排序的结果是:")
for (var n = 0; n < array.length; n++) {
document.write(array[n] + ",");
}
document.write("<br />")
/* 输出结果结束 */
}
}
复杂排序
希尔排序
希尔排序是插入排序的升级,1959年希尔通过将简单排序中两两比较改为设置步长跳跃式比较而突破了n的平方的时间复杂度,希尔排序根据步长的不同时间复杂度由最好的nlogn到最坏的n的平方。代码如下:
function shallSort(array) {
var increment = array.length;
var i
var temp; //暂存
var count = 0;
do {
increment = Math.floor(increment / 3) + 1;
for (i = increment; i < array.length; i++) {
if (array[i] < array[i - increment]) {
temp = array[i];
for (var j = i - increment; j > 0 && temp < array[j]; j -= increment) {
array[j + increment] = array[j];
}
array[j + increment] = temp;
/* 输出结果 */
count++;
document.write("<br />第 + count + "遍排序的结果是:")
for (var n = 0; n < array.length; n++) {
document.write(array[n] + ",");
}
/* 输出结果结束 */
}
}
}
while (increment > 1)
}
堆排序
堆排序是选择排序的升级,通过不断构建大顶堆或者小顶堆来选择最大或者最小的值放入队列前端进行排序,堆排序任何情况下的时间复杂度都为nlogn,代码如下:
function heapSort(array) {
var temp;
var i;
for (i = Math.floor(array.length / 2); i >= 0; i--) {
heapAdjust(array, i, array.length - 1); //将数组array构建成一个大顶堆
}
for (i = array.length - 1; i >= 0; i--) {
/*把根节点交换出去*/
temp = array[i];
array[i] = array[0];
array[0] = temp;
/*余下的数组继续构建成大顶堆*/
heapAdjust(array, 0, i - 1);
/* 输出结果 */
document.write("<br />第 + (array.length - i).toString() + "遍排序的结果是:")
for (var n = 0; n < array.length; n++) {
document.write(array[n] + ",");
}
/* 输出结果结束 */
}
}
//要调整的子树
//start为数组开始下标
//max是数组结束下标
function heapAdjust(array, start, max) {
var temp, j;
temp = array[start];//temp是根节点的值
for (j = 2 * start; j < max; j *= 2) {
if (j < max && array[j] < array[j + 1]) { //取得较大孩子的下标
++j;
}
if (temp >= array[j])
break;
array[start] = array[j];
start = j;
}
array[start] = temp;
}
归并排序
归并排序是复杂排序中唯一一个稳定排序,通过将待排序数组进行分拆再合并来进行排序,归并排序时间复杂度为n的平方,代码如下:
//source源数组 //dest目标数组
//s起始下标
//t目标下标
function mSort(source, dest, s, t) {
var m; //取中间值
var dest2 = new Array();
if (s == t) {
dest[s] = source[s];
}
else {
m = Math.floor((s + t) / 2);
mSort(source, dest2, s, m);
mSort(source, dest2, m+1 , t);
merge(dest2, dest, s, m, t);
/* 输出结果 */
document.write("<br />第 + ++count + "遍排序的结果是:")
for (var n = 0; n < dest.length; n++) {
document.write(array[n] + ",");
}
/* 输出结果结束 */
}
}
//将两个数组按照从小到大的顺序融合
//source原数组
//dest排序后的数组
//s第一个下标
//m第二个数组下标
//总长度
function merge(source, dest, s, m, n) {
for (var j = m+1, k = s; j <= n && s <= m; k++) {
if (source[s] < source[j]) {
dest[k] = source[s++];
}
else {
dest[k] = source[j++];
}
}
//将剩余排不完的有序数组加入到dest的末端
if (s <= m) {
for (var l = 0; l <= m - s; l++) {
dest[k + l] = source[s+l];
}
}
if (j <= n) {
for (var l = 0; l <= n - j; l++) {
dest[k + l] = source[j+l];
}
}
}
快速排序
快速排序是目前已知的速度最快的排序,时间复杂度为nlogn,代码如下:
var count = 0;
function quickSort(array, low, high) {
var temp;
if (low < high) {
var keypoint = QuickSortHelp(array, low, high);
count++;
document.write("<br />第台? + count + "遍括?排?序ò的?结á果?是?:")
for (var l = 0; l < array.length; l++) {
document.write(array[l] + ",");
}
quickSort(array, low, keypoint - 1);
quickSort(array, keypoint + 1, high);
}
}
function QuickSortHelp(array, low, high) {
while (low < high) {
while (low < high && array[low] <= array[high]) {
high--;
}
temp = array[low];
array[low] = array[high];
array[high] = temp;
while (low < high && array[low] <= array[high]) {
low++
}
temp = array[low];
array[low] = array[high];
array[high] = temp;
}
return low;
}
分享到:
相关推荐
字符串排序方法 javaScript中的字符串排序。
下面小编就为大家分享一篇基于js 各种排序方法和sort方法的区别(详解),具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序...
js冒泡排序,冒泡排序的工作原理,我们有一个未排序的数组arr = [ 1, 4, 2, 5, -2, 3 ]任务是使用冒泡排序对数组进行排序。 冒泡排序比较索引 0 中的元素,如果第 0 索引大于第 1 索引,则交换值,如果第 0 索引...
js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js...
JQ JS javascript 拖拽 排序功能 列表排序 菜单排序 表格排序
收集起来js表格排序、支持中文、日期、英文、数值排序,多个Javascript表格排序方法,完美解决
javascript 的几种排序方法
各种排序方法演示Java小程
系统自带的排序API,冒泡排序,快速排序,插入排序,选择排序,希尔排序,归并排序,堆排序,计数排序
js json 重新随机重组排序方法demo,打乱json排序的方法,让json重新组合,亲测有效,分享给大家
javascript 实现排序分类功能, 冒泡排序, 快速排序等等
js 图片排序js 图片排序 --点点滴滴js 图片排序 --点点滴滴
程序的实现的是在客户端对表格进行排序,有以下特点: 1.自定义排序列、排序属性(例如innerHTML)、排序数据类型(包括int、float、date、string)、排序顺序(顺序和倒序); 2.自定义排序函数; 3.可同时设置...
js option 中文排序
用js实现点击表头对Table排序,支持td中包含html标签,支持tr,td的原来样式不丢失,支持选择从第几行开始排序,支持时间,小数,整数和字符的排序
js中文排序算法,不用自己比较unicode
用javascript实现的十大排序算法详解
js实现各种排序算法:插入排序、冒泡排序、基数排序......,真实有效