常用排序算法JavaScript实现.docx

《常用排序算法JavaScript实现.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、常用排序算法JavaScript实现1、插入排序1）算法描述和实现一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：1.从第一个元素开始，该元素可以认为已经被排序；2.取出下一个元素，在已经排序的元素序列中从后向前扫描；3.如果该元素（已排序）大于新元素，将该元素移到下一位置；4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；5.将新元素插入到该位置后；重复步骤2~5。JavaScript代码实现：functioninsertionSort(array){if(Object.prototype.toString.call(array).sl

2、ice(8,-1)==='Array'){for(vari=1;i=0&&array[j]>key){array[j+1]=array[j];j--;}array[j+1]=key;}returnarray;}else{return'arrayisnotanArray!';}}3）算法分析最佳情况：输入数组按升序排列。T(n)=O(n)最坏情况：输入数组按降序排列。T(n)=O(n2)平均情况：T(n)=O(n2)二、二分插入排序1）算法简介二分插入（Binary-ins

3、ert-sort)排序是一种在直接插入排序算法上进行小改动的排序算法。其与直接插入排序算法最大的区别在于查找插入位置时使用的是二分查找的方式，在速度上有一定提升。2）算法描述和实现一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：从第一个元素开始，该元素可以认为已经被排序；取出下一个元素，在已经排序的元素序列中二分查找到第一个比它大的数的位置；将新元素插入到该位置后；重复上述两步。JavaScript代码实现：functionbinaryInsertionSort(array){if(Object.prototype.toString.call(arr

4、ay).slice(8,-1)==='Array'){for(vari=1;i=left;j--){array[j+1]=array[j];}array[left]=key;}returnarray;}else{retu

5、rn'arrayisnotanArray!';}}3）算法分析最佳情况：T(n)=O(nlogn)最差情况：T(n)=O(n2)平均情况：T(n)=O(n2)三、选择排序1）算法简介选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。2）算法描述和实现n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：初始状态：无序区为R[1..n]，有序区为空；

6、第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；n-1趟结束，数组有序化了。JavaScript代码实现：functionselectionSort(array){if(Object.prototype.toString.call(array).slice(8,-1)==='Array'){varlen=array.length,temp

7、;for(vari=0;i