十大基本算法介绍Tozhang

其中插入算法和归并算法对重复率比较高的排序比较友好；冒泡算法不适合大量数据。

二、具体定义：

1.冒泡排序：

*概念：冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

*算法描述:

*动画演示：

*算法实例：

functionbubbleSort(arr){varlen=arr.length;for(vari=0;iarr[j+1]){//相邻元素两两对比vartemp=arr[j+1];//元素交换arr[j+1]=arr[j];arr[j]=temp;}}}returnarr;}vararr=[6,5,4,3,2,1];console.log(arr);//[6,5,4,3,2,1]bubbleSort(arr);console.log(arr);//[1,2,3,4,5,6]

2.选择排序：

*概念：选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

functionselectionSort(arr){if(arr==null||arr.length<2){returnarr;}for(vari=0;i<(arr.length-1);i++){letminIndex=i;for(letj=i+1;j

3.插入排序：

*概念：插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

functioninsertionSort(arr){if(arr==null||arr.length<2){returnarr;}for(leti=1;i=0&&arr[j]>arr[j+1];j--){lettemp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}}returnarr;}vararr=[3,4,2,1,6,7,8,4];console.log(arr);//[3,4,2,1,6,7,8,4]insertionSort(arr);console.log(arr);//[1,2,3,4,4,6,7,8]

4.希尔排序：

*概念：1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者RobertSedgewick提出的。

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

functionshellSort(arr){varlen=arr.length;for(vargap=Math.floor(len/2);gap>0;gap=Math.floor(gap/2)){for(vari=gap;i=0&&arr[j]>arr[gap+j];j-=gap){vartemp=arr[j];arr[j]=arr[gap+j];arr[gap+j]=temp;}}}}vararr=[49,38,65,97,76,13,27,49,55,04];console.log(arr);//[49,38,65,97,76,13,27,49,55,4]shellSort(arr);console.log(arr);//[4,13,27,38,49,49,55,65,76,97]

5.归并算法：

*概念：归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（DivideandConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

functionmergeSort(arr){if(arr.length==1){returnarr;}varmid=Math.floor(arr.length/2);varleftArr=arr.slice(0,mid);varrightArr=arr.slice(mid);returnmerge(mergeSort(leftArr),mergeSort(rightArr));}functionmerge(leftArr,rightArr){varresult=[];while(leftArr.length&&rightArr.length){if(leftArr[0]

6.快速排序：

*概念：快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

constquickSort=(array)=>{constsort=(arr,left=0,right=arr.length-1)=>{if(left>=right){//如果左边的索引大于等于右边的索引说明整理完毕return}leti=leftletj=rightconstbaseVal=arr[j]//取无序数组最后一个数为基准值while(ii&&arr[j]>=baseVal){//找到一个比基准值小的数交换j--}arr[i]=arr[j]//将较小的值放在左边如果没有找到比基准值小的数就是将自己赋值给自己（i等于j）}arr[j]=baseVal//将基准值放至中央位置完成一次循环（这时候j等于i）sort(arr,left,j-1)//将左边的无序数组重复上面的操作sort(arr,j+1,right)//将右边的无序数组重复上面的操作}constnewArr=array.concat()//为了保证这个函数是纯函数拷贝一次数组sort(newArr)returnnewArr}vararr=[6,5,4,5,3,4,1];console.log(arr);//[6,5,4,5,3,4,1]console.log(quickSort(arr));//[1,3,4,4,5,5,6]

7.堆排序：

*概念：堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

8.计数排序：

functioncountingSort(arr,maxValue){varbucket=newArray(maxValue+1),sortedIndex=0,arrLen=arr.length,bucketLen=maxValue+1;for(vari=0;i0){arr[sortedIndex++]=j;bucket[j]--;}}returnarr;}vararr=[4,3,3,2,3,4,5,6,3,5,6,4,6,5,2,1,2];console.log(arr);countingSort(arr,6);console.log(arr);

9.桶排序：

*概念：桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。

桶排序(Bucketsort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

10.基数排序：

*概念：基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

基数排序的空间复杂度为O(n+k)，其中k为桶的数量。一般来说n>>k，因此额外空间需要大概n个左右。

functionradixSort(arr,maxDigit){varcounter=[];varmod=10;vardev=1;for(vari=0;i