js实现八大排序
· 八大排序
·
· 7、归并排序
· 8、基数排序
· 9、八大排序对比
·
八大排序
这里的八大排序都是内部排序，即使用内存进行排序。
1、插入排序——直接插入排序
（1）基本思想
a、先将待排序序列的第1个元素看成是一个有序的子序列；
b、从第2个元素开始，逐个将待排序的元素x与已排序序列[i-1] ~[0]（从后往前）进行比较；
c、若x小于比较元素，则比较元素向后移动一位；否则，将x插入序列当前位置。
（2）演示示例
（3）js实现
funcnort(arr){
//第一层循环：遍历待比较的数组元素
for(let i = 1; i < arr.length; i++){
let temp = arr[i];
//第二层循环：将本轮带比较的元素与已经排序的元素相比较
for(var j = i - 1; j >= 0 && arr[j] > temp; j--){
arr[j + 1] = 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实现
需要三层循环遍历
function shellSort(arr){
let n = arr.length,
d = n;
//第一层循环:分割增量d
while(d > 1){
d = Math.floor(d/2);
//下面；两层循环是直接插入排
for(var i = d; i < n; i++){
//记录待比较的元素
var temp = arr[i];
for(var j = i - d; j >= 0 && arr[j] > temp; j = j -d){
arr[j + d] = arr[j];
}
arr[j + d] = temp;
}
}
return arr;}
console.log(shellSort([1,5,3,7,2,8]));
3、选择排序——简单选择排序
（1）基本思想——比较+交换
每次遍历找到待排序元素中的最小值，将最小值和待排序的第一个元素交换，直至排序结束。
（2）演示示例
（3）js实现
function directSelectSort(arr){
let minIndex, temp;
for(var i = 0; i < arr.length; i++){
minIndex = i;
//找到最小的值
for(var j = i + 1; 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）基本思想
1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
a、首先将长度为n的序列构建称为大顶堆，此时根节点一定是当前序列的最大值；
b、取出当前大顶堆的根节点，将其与序列末尾元素进行交换；
c、对交换后的n-1个序列元素进行调整，使其满足大顶堆的性质；
d、重复b、c两个步骤，直至堆中只有1个元素为止。
2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列。
（2）js实现
核心：初始建立大根堆、输出堆顶元素后调整大根堆
function heapSort1(arr) {
len = arr.length;
//建堆
for(let i = Math.floor(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)，且不要求内存空间，但是不稳定。