前言
在本部分将主要学习常用的排序和搜索算法: 如:冒泡排序、选择排序、插入排序、归并排序、 快速排序和堆排序等以及:顺序搜索和二分搜索算法。
//1、在开始排序算法之前,先创建一个数组(列表)来表示待排序和搜索的数据结构。
function ArrayList() { var array = []; //1.1定义一个数组来存放数据 this.insert = function
(item) { //1.2定义一个插入方法来向数据结构中添加元素 array.push(item); }; this.toString = function
() { //使用js原生的join方法,来拼接数组中的所有元素 return array.join('-'); }; //未改进时的冒泡排序: /***
* 冒泡排序比较任何两个相邻的项,如果第一个比第二个大,则交换它们。 * 时间复杂度为 O(n^2) */ this.bubbleSort =
function () { var length = array.length; for (var i = 0; i < length; i++) {
//控制循环次数 for (var j = 0; j < length - 1; j++) { //不断比较交换相邻位置的数据 if (array[j] >
array[j + 1]) { swap(array, j, j + 1); } } } }; //改进后的冒泡排序 /** *
如果从内循环减去外循环中已经跑过的次数,就可以避免内循环中所有不必要的比较 * */ this.modifiedBubbleSort = function
() { var length = array.length; for (var i = 0; i < length; i++) { for (var j =
0; j < length - 1 - i; j++) { if (array[j] > array[i]) { swap(j, j + 1); } } }
}; /** * 选择排序:选择排序算法是一种原址比较排序算法。选择排序大致的思路是找到数据结构中最小值并将其放在第一位, *
接着找到第二小的值并将其放在第二位,以此类推。 * 其时间复杂度也为O(n^2) * * */ //选择排序算法的源代码:
this.selectionSort = function () { var length = array.length; var indexMin; for
(var i = 0; i < length - 1; i++) {//外循环迭代数组,并控制迭代轮次(数组的第n个值====下一个最小值) indexMin
= i; //假设本轮迭代的最小值 for (var j = i; j < length; j++) {
//从当前的i值开始至数组结束,比较是否位置j的值比当前最小值小,如果是 if (array[indexMin] > array[j]) { indexMin
= j;//则改变最小值至新最小值 } }//当内循环结束,得出数组第n小的值 if (i !== indexMin)
{//如果该最小值和原最小值不同,则交换其值 [array[i], array[indexMin]] = [array[indexMin],
array[i]]; } } }; /** * 插入排序:插入排序每次排一个整数项,以此构建最后的排序数组。 * * */
this.insertionSort = function () { var length = array.length; var j, temp; for
(var i = 1; i < length; i++) {//迭代数组来给第i项找到正确的位置 j = i; temp =
array[i];//用i的值来初始化一个辅助变量并将其值亦存储于--临时变量 while (j > 0 && array[j - 1] > temp)
{//查找正确的位置插入 array[j] = array[j - 1];//如果数组中前面的值比待比较的值大,把前面的值移到当前位置,J-- j--; }
array[j] = temp; //直到前面的值部不大于temp时,把temp放入当前的位置中。然后迭代下一项继续排序 } }; /** *
归并排序:归并排序是第一个可以被实际使用的算法 *前面几个算法的性能不好,归并排序不错,其复杂度为 * 时间复杂度:O(nlog^n) *
归并排序是一种分治算法。其思想是将原始数组切分成较小的数组 * 直到每个小数组只有一个位置,接着小数组归并成较大的数组,直到最后只有一个排序完毕的大数组 *
*/ this.mergeSort = function(){ array = mergeSortRec(array); }; /** *
快速排序:最常用的算法,它的复杂度为O(nlog^n) * (1)首先,从数组中选择中间一项作为主元。 *
(2)创建两个指针,左边一个指向数组第一项,右边一个指向数组最后一项。 *
移动左指针直到我们找到一个比主元大的元素,接着,移动右指针直到找到一个比主元小的元素。 * 然后交换它们,重复这个过程,直到左指针超过了右指针。 *
这个过程使得比主元小的值都排在主元之前,而比主元大的值都排在主元之后
*(3)接着,算法对划分后的小数组(较主元小的值组成的子数组,以及较主元大的值组成的子数组) * 重复之前的两个步骤,直至数组已经完全排序。 **/
this.quickSort = function(){ quick(array, 0, array.length - 1); }; //搜索算法 /** *
顺序搜索:顺序或线醒搜索是最基本的搜索算法。它的机制是: * 将每一个数据结构中的元素和我们要找的元素做比较。顺序搜索是最低效的 * 一种搜索算法。 * */
this.sequentialSearch = function(item){ for(var i=0;i<array.length;i++){
if(item === array[i]){ return i;//true或者array[i] } } return -1; } /** *
二分搜索:该算法要求被搜索的数据结构已经排序 * 步骤: * (1)选择数组的中间值 * (2)如果选中值是待搜索值,那么算法执行完毕 *
(3)如果待搜索值比选中值要小,则返回步骤1并在选中值左边的子数组中寻找 * (4)如果待搜索值比选中值要大,则返回步骤1并在选中值右边的子数组中寻找 */
this.binarySeach = function(item){ this.quickSort(); //在查找之前对数组进行排序 var low =
0; var high = array.length -1; var mid,element; while(low<= high){ mid =
Math.floor((low + high) /2); element = array[mid]; if(element <item) { low =
mid +1; } else if(element >item){ high = mid -1; }else{ return mid; //返回的是索引 }
} return -1; }; } //快速排序划分过程: var partition = function(array,left,right){ var
pivot = array[Math.floor((right + left)/2)];//选择中间项作为主元 var i= left;
//初始化为数组第一个元素 var j = right; //初始化为数组最后一个元素 while(i<= j){ while(array[i] <
pivot){ //移动指针直到找到一个元素比主元大 i++; } while(array[j] > pivot){
//对于right指针做同样的事,移动找到比主元小的 j--; } if(i<= j){
//当左指针指向的元素比主元大且右指针指向的元素比主元小,且此时左指针索引没有右指针索引大,则交换它们 swap(array,i,j); i++; j--;
} } return i; }; // 声明方法来调用递归函数,传递待排序数组,以及索引0及其最末的位置作为参数。 var quick =
function(array,left,right){ var index; //定义该变量,帮助我们将子数组分离为较小的数组和较大的数组
if(array.length >1){ index = partition(array,left,right); if(left < index -1){
quick(array,left,index-1); } if(index < right){ quick(array,index,right); } }
}; //以下为归并排序 // 实际被执行的辅助函数 var mergeSortRec = function(array){ var length =
array.length; if(length ===1){ //结束条件 return array; } var mid =
Math.floor(length/2);//获得数组的中间位 var left = array.slice(0,mid); //数组将其分成两个小数组
var right = array.slice(mid,length); return
merge(mergeSortRec(left),mergeSortRec(right)); }; //定义merge函数,负责合并和排序小数组来产生大数组
//直到回到原始数组并已经排序完成。 var merge = function(left,right){ var result = []; var iL =
0; var iR = 0; while(iL < left.length && ir < right.length) { // {8} if
(left[iL] < right[iR]) { result.push(left[iL++]); // {9} } else {
result.push(right[iR++]); } } while(iL <left.length){ result.push(left[iL++]);
} while(iR <right.length){ result.push(right[iR++]); } return result; }; //交换方法
var swap= function(array,index1,index2){ /* var aux = array[index1];
array[index1]= array[index2]; array[index2]=aux;*/ //可以利用es6中的方式来交换
[array[index1],array[index2]]=[array[index2],array[index1]]; };
测试:
//测试冒泡排序算法 //定义一个函数自动地创建一个未排序的数组,数组的长度由函数的参数指定 function
createNonSortedArray(size){ var array = new ArrayList(); for(var i =
size;i>0;i--){ array.insert(i); } return array; } //测试冒泡结果 var array =
createNonSortedArray(5); console.log("冒泡排序前:",array.toString());
array.bubbleSort(); console.log("冒泡排序后:",array.toString()); //测试选择排序算法 var
selectionArry = createNonSortedArray(5);
console.log("选择排序前:",selectionArry.toString()); selectionArry.selectionSort();
console.log("选择排序后:",selectionArry.toString()); //测试插入排序算法 var insertArry =
createNonSortedArray(5); console.log("插入排序前:",insertArry.toString());
insertArry.selectionSort(); console.log("插入排序后:",insertArry.toString());
console.log("二分查找后的数据",insertArry.binarySeach(3));
执行结果

技术
©2019-2020 Toolsou All rights reserved,
【贪心算法】哈夫曼编码问题VHDL——JK触发器react 项目--博客系统数据库期末复习:综合应用题汇总面过了,起薪30k找出游戏的获胜者(java)JAVA实验四集合与函数式编程实验排序会了递归,不学非递归太可惜了SQL综合题 员工单位综合题数据库作业五