几种排序
稳定性：保证排序前两个相等的数据其在序列中的先后位置顺序与排序后它们两个先后位置顺序相同
1. 冒泡排序
冒泡排序算法的原理如下：
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| function bubbleSort(nums) {
for(let i=0;i<nums.length;i++){
for(let j=0;j<nums.length-1-i;j++){
if(nums[j]>nums[j+1]){
let temp=nums[j+1]
nums[j+1]=nums[j]
nums[j]=temp
}
}
}
}
nums = [5, 1, 4, 2, 8];
bubbleSort(nums);
console.log(nums);
|
2. 选择排序
第一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。
算法思路：
1）假设未排序序列的第一个是最小值，记下该元素的位置，从后往前比较
2）找出最小的一个元素
3）然后将最小元素与记录元素交换位置
4）重复第二，三个步骤，直到找完未排序的部分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| function selectSort(arr){
for(let i=0;i<arr.length;i++){
let index=i
for(let j=arr.length-1;j>i;j--){
if(arr[j]<arr[index]){
index=j
}
}
let temp=arr[i]
arr[i]=arr[index]
arr[index]=temp
}
}
let arr=[5,4,3,2,1,6]
selectSort(arr)
console.log(arr)
|
3. 直接插入排序
它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
算法描述：
一般来说，插入排序都采用 in-place 在数组上实现：
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素a，在已经排序的元素序列中从后向前扫描；
- 如果a比之前的元素小，就交换位置；
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤2~5。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| function insertionSort(arr){
for(let i=1;i<arr.length;i++){
for(j=i;j>0;j--){
if(arr[j]<arr[j-1]){
let temp = arr[j-1]
arr[j-1]=arr[j]
arr[j]=temp
}
}
}
}
nums = [5, 1, 4, 2, 8];
insertionSort(nums);
console.log(nums);
|
4. 快速排序
选择数组中的一个值作为基准(arr[0])，将数组中小于该值的数置于该数之前，大于该值的数置于该数之后，接着对该数前后的两个数组进行重复操作直至排序完成。
算法步骤：
1.定义一个函数，传入参数，判断这个参数的长度，如果长度是1，直接ruturn出去，如果是进入下一步。
2.将这个数组头部的值作为中位数，定义两个新的数组left，right，然后让原数组中剩余的数与这个中位数比较，比中位数小的放到left数组，比中位数大的放到right,然后再对这两个数组进行递归。
3.最后将arrleft, 中位数，arrright拼接，return出去
1
2
3
4
5
6
7
8
9
10
11
12
| function quckSort(arr){
if(arr.length<=1) return arr
let mid=arr[0]
let left=[], right=[]
for(let i=1;i<arr.length;i++){
if(arr[i]<mid) left.push(arr[i])
else right.push(arr[i])
}
return [...quckSort(left),mid,...quckSort(right)]
}
let arr=[4,1,6,5,7,2,3]
console.log(quckSort(arr))
|
5. 堆排序
一、什么是堆
堆首先是一个完全二叉树，堆分为大顶堆和小顶堆
大顶堆：每个节点的值大于或等于其左右孩子节点的值，称为大顶堆。
小顶堆：每个节点的值小于或等于其左右孩子节点的值。
注意：每个节点的左右孩子节点的大小关系并没有限定。
堆排序基本思想
以大顶堆为例，算法步骤如下：
1、首先将待排序序列构建成一个大顶堆(存入数组中)，那么这时，整个序列的最大值就是堆顶的根节点；
2、将堆顶元素与最后一个元素交换，那么末尾元素就存入了最大值；
3、将剩余的 n - 1个元素重新构建成一个大顶堆，重复上面的操作；
反复执行，就能得到一个有序序列了。
6. 归并排序
归并排序使用分而治之的概念对给定的元素列表进行排序。它将问题分解为较小的子问题，直到它们变得足够简单以至可以直接解决为止。
归并排序，顾名思义，就是把两个已经排好序的数组进行归并，成为一个新排序好的序列。
以下是归并排序的步骤：
1、将给定的列表分为两半（如果列表中的元素数为奇数，则使其大致相等）。
2、以相同的方式继续划分子数组，直到只剩下单个元素数组。
3、从单个元素数组开始，合并子数组，以便对每个合并的子数组进行排序。
4、重复第 3 步单元，直到最后得到一个排好序的数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
function mergeSort(arr){
if(arr.length===1) return arr
let mid=Math.floor(arr.length/2)
let leftArr=arr.slice(0,mid)
let rightArr=arr.slice(mid)
return merge(mergeSort(leftArr),mergeSort(rightArr))
}
function merge(left,right){
let 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)
}
nums = [5, 1, 4, 2, 8, 11, 2, 3];
let res = mergeSort(nums);
console.log(res);
|
7. 希尔排序
思想是指定一个间隔（增量）将待排序的元素进行分组，然后再对每一组进行排序，直到间隔（增量）减至1时，整个序列恰好被分成一组，（再进行直接插入排序）最后排成有序序列。
其中增量序列的选择是非常关键的，但通常我们取步长为 n/2（数组长度的一般）然后一直取半直到 1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| function shellSort(arr){
for(let gap = Math.floor(arr.length/2);gap > 0;gap = Math.floor(gap/2)){
for(let i = gap;i < arr.length;i++){
let j = i;
let tmp = arr[j];
if(arr[j] < arr[j-gap]){
while(j - gap >= 0 && arr[j-gap] > tmp){
arr[j] = arr[j-gap];
j = j-gap;
}
arr[j] = tmp;
}
}
}
}
let arr = [9,5,8,7,1,4,6,3,2,0];
shellSort(arr)
console.log(arr);
|
