js字母排序,js字符串排序

js为8大排序8大排序1、插入排序——直接插入排序2、插入排序—— hill排序(最小增量排序) 3、选择排序——简单选择排序4、选择排序——累计排序5、更换排序—— babbe排序3

八大名次

这里的8个排序都是内部排序，也可以通过存储器进行排序。

1、插入排序——直接插入排序(1)基本思想

a、首先将待排序数组的第一个元素视为有序子数组；

b、从第二个要素开始依次将排序对象要素x与排序完毕的排列[i-1] ~[0] (从后向前)进行比较；

当c、x小于比较元素时，比较元素向后移动一个数量级； 否则，将x插入序列的当前位置。

)2)演示实例

)3) js的实现

functioninsertsort(arr ) (/第一层循环)遍历要比较的数组元素for (leti=1； i arr.length； I ) {let temp=arr[i]； //第二层循环：将本倒圆角带比较的元素与已经排序的元素进行比较的for(varj=I-1； j=0 arr[j] temp； j--}{arr[j1]=arr[j]； //将插入元素插入到正确位置的arr[j 1]=temp； }return arr； } console.log (insertsort ([ 1，5，3，7，2，8 ] )； //8 ) [2、3、4、5、7、7、8、10]2、插入排序——辅助排序(最小增量排序)1)基本思想改进直接插入排序

a、首先将序列按增量d(n/2，n为待排序数的个数)分成几组，所有距离为d倍数的记录归入同一组； 各组内直接进行插入排序；

b、然后按较小增量(d/2 )对其进行分组，每组直接插入排序； 将增量减少为1，直接进行插入排序，即可完成整体排序。

)2)演示实例

)3) js的实现

需要三层循环扫描

functionshellsort(arr ) { let n=arr.length，d=n； //第一层循环：分割增量dwhile(d1 ) d=math.floor ) d/2 )； //下双重循环直接插入排出for(varI=d； i n； I ) (/比较对象要素var temp=arr[i]； for(varj=I-d； j=0 arr[j] temp； j=j-d({arr[jd]=arr[j]； } arr[j d]=temp； } } return arr； }console.log (壳快照([ 1，5，3，7，2，8 ] )； 3、选择顺序——简选顺序(1)基本思想——比较交换

只要找到要排序的元素中的最小值，就将最小值与要排序的第一个元素交换，并继续直到排序结束。

)2)演示实例

)3) js的实现

functiondirectselectsort(arr ) { let minIndex，temp； for(varI=0； i arr.length； I ) { minIndex=i； //找到最小值for (varj=i1； j arr.length； j () if ) arr[j]arr[minindex] ) { minIndex=j； }//将最小值与第一个未排序的元素交换的temp=arr[i]； arr[i]=arr[minIndex]； arr[minIndex]=temp； } return arr； ) 4、选择顺序——积累顺序(1)基本思想

大堆：每个节点的值等于或大于其子节点的值，堆排序算法用于按升序排序。

a、首先将长度为n的序列构建称为大堆，此时根节点必须是当前序列的最大值；

b、取出当前顶层堆的根节点，将其与数组末尾的元素进行交换；

c、调整交换的n-1个序列元素，使之符合大顶性质；

D、重复B、C两个步骤，直到堆中只有一个元素。 小的顶层堆：每个节点的值小于或等于其子节点的值，堆排序算法用于按降序排序。 )2) js的实现

核心：先制作萝卜堆，输出堆顶元素后调整萝卜堆

function heapsort1(arr ({ len=arr.length； //堆for(letI=math.floo

r(len/2); i >= 0; i--){ heapify(arr, i); } for(let i = len - 1; i > 0; i--){ //输出堆顶元素 [arr[0], arr[i]] = [arr[i], arr[0]]; len--; //重新调整堆 heapify(arr, 0); } return arr;}//调整堆function heapify(arr, i) { var left = 2 * i + 1, right = 2 * i + 2, largest = i; if(left < len && arr[left] > arr[largest]){ largest = left; } if(right < len && arr[right] > arr[largest]){ largest = right; } if(largest !== i){ [arr[i], arr[largest]] = [arr[largest], arr[i]]; heapify(arr, largest); }} 5、交换排序——冒泡排序

（1）基本思想——两两比较相邻的元素，如果反序，则交换位置，直到没有反序为止。有序区在后面。
a、将序列中的相邻元素依次比较，较大的数向上冒（即交换到后面）；第一轮比较结束后，序列最后一个元素是当前序列的最大值。
b、对序列当中剩下的n-1个元素再次执行步骤b，直至完成。共需要n-1轮比较。

（2）演示示例

（3）js实现

function bubbleSort(arr) { let len = arr.length; //共需要n-1趟排序 for(let i = 1; i < len; i++){ for(let j = 0; j < len - i; j++){ if(arr[j] > arr[j + 1]){ [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; //解构赋值进行交换 } } } return arr;}console.log(bubbleSort([7, 3, 4, 5, 10, 7, 8, 2,21]));//改进的冒泡排序，记录上次交换的位置pos，避免对排好序的数据进行重复比较function bubbleSort1(arr) { let len = arr.length; var pos = len; //初始化时无序元素的范围 while(pos !== 0){ var bound = pos; //本趟无序元素的范围 pos = 0; for(let i = 0; i < bound; i++){ if(arr[i] > arr[i + 1]){ [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]]; //解构赋值进行交换 pos = i; } } } return arr;}console.log(bubbleSort1([7,2, 3, 4, 5, 10, 7, 8, 2,21])); 6、交换排序——快速排序

（1）基本思想：快排是冒泡排序的改进版。
a、从序列当中选择一个基准数（一般选第一个数）；
b、遍历数组，小于基准的放在left，大于基准的放在right；
c、递归。

（2）演示示例
a、一趟排序的过程：

b、排序的全过程

（3）js实现

//方式1function QSort(arr) { //如果数组<=1,则直接返回 if(arr.length <= 1){ return arr; } //找基准，并把基准从原数组删除 var pivot = arr.splice(0, 1)[0]; //定义左右数组 var left = []; var right = []; //比基准小的放在left，比基准大的放在right for(var i = 0; i < arr.length; i++){ if(arr[i] <= pivot){ left.push(arr[i]); } else{ right.push(arr[i]); } } //递归 return QSort(left).concat([pivot],QSort(right));}console.log(QSort([7,2, 3, 4, 5, 10, 7, 8, 2,21]));//方式2function QSort2(arr, left, right) { if(left < right){ //找基数第一趟排序后的位置 let pivot = partion(arr,left,right); //递归排序左右区间 QSort2(arr, left, pivot - 1); QSort2(arr, pivot + 1, right); } return arr;}//快排第一趟function partion(arr, left, right) { //第一个元素作为基数 let pivotVal = arr[left]; pivot = left; while(left<right){ while(right>left && arr[right]>=pivotVal){ right--; } [arr[left], arr[right]] = [arr[right], arr[left]]; while(left<right && arr[left]<=pivotVal){ left++; } [arr[left], arr[right]] = [arr[right], arr[left]]; } return left;}var arr = [7,2, 3, 4, 5, 10, 7, 8, 2,21];console.log(QSort2(arr, 0, arr.length-1)); 7、归并排序

（1）基本思想——分治策略：拆分+合并
a、先将数组进行分组（折半拆分），直至子序列长度为1；
b、然后再将子数组进行合并，关键点是实现两个数组的合并。

（2）演示示例

（3）js实现

//合并两个有序数组function merge(left, right) { var res = []; while(left.length > 0 && right.length > 0){ if(left[0] <= right[0]){ res.push(left.shift()); //删除第一个元素，并将其返回 }else{ res.push(right.shift()); } } return res.concat(left, right);}//归并排序function mergeSort(arr){ //一直分到长度为1时，停止递归 if(arr.length === 1){ return arr; } var mid = Math.floor(arr.length/2); var left = arr.slice(0, mid); var right = arr.slice(mid); return merge(mergeSort(left), mergeSort(right));}console.log(mergeSort([7,2, 3, 4, 5, 10, 7, 8,21])); 8、基数排序

（1）基本思想
1、MSD 从高位开始进行排序
2、LSD 从低位开始进行排序：
a、将所有待比较元素（正整数）统一为同样的数位长度，数位较短的数前面补零；
b、从个位开始，进行排序；然后一次从低位到高位，进行排序；直至最高位完成排序。
（2）演示示例

（3）js实现

//基数排序function radixSort(arr, maxDigit) { //maxDigit表示最大数字的位数 var counter = []; var mod = 10; //以十进制进行排序 var dev = 1; for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) { for(var j = 0; j < arr.length; j++) { var bucket = parseInt((arr[j] % mod) / dev); if (counter[bucket]==null) { counter[bucket] = []; } counter[bucket].push(arr[j]); } var pos = 0; for(var j = 0; j < counter.length; j++) { var value = null; if(counter[j]!=null) { while ((value = counter[j].shift()) != null) { arr[pos++] = value; } } } } return arr;}var a = [3, 4, 5, 10, 713, 8,21,4,2,124];console.log(radixSort(a, 3)); 9、八大排序对比

图中有误，js实现的归并排序的空间复杂度是O(n),网上有人分享复杂度为O(1)的方法也是用时间来换取空间。

选择排序算法的依据

四点因素：
1．待排序的记录数目n的大小；
2．记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小；
3．关键字的结构及其分布情况；
4．对排序稳定性的要求。

设待排序元素的个数为n.
（1）n较小（n<50）时，可采用直接插入排序或简单选择排序。

a、 当元素自身信息量较大时，且不要求稳定性，采用简单选择排序。b、要求稳定性的话，采用直接插入排序。

（2）若元素的初始状态基本有序，可采用直接插入排序或冒泡排序。

a、当元素分布有序，直接插入排序将大大减少比较次数和移动记录的次数。b、一般不使用或不直接使用传统的冒泡排序。

（3）n较大时，应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。

a、快速排序：是目前内部排序中被认为是最快的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短。b、归并排序：当内存空间允许，且要求稳定性时，优先选择归并排序。c、堆排序：最坏的情况下时间复杂度也是O(nlog~2~n)，且不要求内存空间，但是不稳定。 参考文献

[1] 八大排序算法原理及实现
[2] 数据结构常见的八大排序算法