排序算法
强烈推荐：
博客园：https://www.cnblogs.com/onepixel/p/7674659.html
参考资料：
《大话数据结构》
极客时间-数据结构和算法之美
开场白
不知道大家学习算法是从哪里起步的？反正我是之前没有学过数据结构和算法就上手代码做项目的，后来才觉得自己底子薄弱，在回头来看数据结构和算法的，我看了严蔚敏老师的那本数据结构，大话数据结构，还有王道那本考研数据结构，知道我看到排序算法，我才发现，原来我之前就接触过排序算法，不管大家之前有没有接触过排序算法，我觉得排序算法应该是所有人接触过的第一类算法。并不是指代码中，大家上学的时候肯定是“被排序的”，比如考试成绩，是按总分从高到低排序的；点名表大概率是按名字首字母排序的。那这些排序是怎么实现的？这就是排序算法。
排序的基本概念与分类
基本定义就不说了。
我们来了解一下一些名词：
1）排序的稳定性：
假设 ki = kj (1 <= i <= n, 1 <= j <= n, i != j),且在排序前的序列中ri领先rj(即 i < j).如果排序后ri仍领先于rj，则称所用的排序方法是稳定的。反之若可能使得排序后的序列中rj领先ri，则称所用的排序方法是不稳定的。
比如：
[0,0,5,4,3,2,1,0];
这个数组使用排序算法。我们定义第一个0为01，第二个为02，第三个为03.
稳定排序后，应该是[0,0,0.1,2,3,4,5]。其中0的顺序和之前定义的顺序一样，第一个0为01，第二个为02，第三个为03.
不稳定排序后，结果也是[0,0,0.1,2,3,4,5]。但是其中0的顺序就不一定是之前定义的，有可能第一个0为01，第二个为03，第三个为02，或是其他的顺序。
2）内排序和外排序:
内排序：是在排序整个过程中，待排序的所有记录全部被放置在内存中。
外排序：是由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据，才能进行。
内排序、外排序具体每个算法需要具体分析。
排序算法的执行效率
1）最好、最坏、平均情况时间复杂度：
这个没得说，时间复杂度是衡量算法效率的标准，这里需要的是这三种的时间复杂度，为什么呢？因为第一，有些排序算法会区分，为了好对比，所以我们最好都做一下区分。第二，对于要排序的数据，有的接近有序，有的完全无序。有序度不同的数据，对于排序的执行时间肯定是有影响的，我们要知道排序算法在不同数据下的性能表现。
2）时间复杂度的系数、常数、低阶：
时间复杂度反应的是数据规模n很大的时候的一个增长趋势，所以它表示的时候会忽略系数、常数、低阶。但是实际的软件开发中，我们排序的可能是10个、100个、1000个这样规模很小的数据，所以，在对同一阶时间复杂度的排序算法性能对比的时候，我们就要把系数、常数、低阶也考虑进来。
3）比较次数和交换（或移动）次数：
基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动。所以，如果我们在分析排序算法的执行效率的时候，应该把比较次数和交换（或移动）次数也考虑进去。
排序算法的分类
直接给出了，后面说明的时候慢慢理解。
排序算法分为 1比较类排序、2非比较类排序
1比较类算法：交换排序、插入排序、选择排序、归并排序
2非比较类排序：计数排序、橘排序、基数排序
交换排序：冒泡排序、快速排序
插入排序：简单插入排序、希尔排序
选择排序：简单选择排序、堆排序
归并排序：二路归并排序、多路归并排序
排序算法具体实现及思路
1、交换排序
1、冒泡排序（Bubble Sort）
1）比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3）针对所有的元素重复以上的步骤，除了最后一个；
4）重复步骤1~3，直到排序完成。
图解可以去查看最顶上那个博客园的链接。
代码：
function BubbleSort(arr) {
let len = arr.length;
for(let i = 0; i < len - 1; i++) { //注意这里是len-1
for(let j = 0; j < len - i - 1; j++) { //注意这里是len - i - 1
if (arr[j] > arr[j + 1]) { //上面的len - 1和这里的j+1有关，
//自己推倒一下过程就知道，当排到数组下标为len-2的时候，则将数组中所有的元素排完了。
let temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
优化一下
function bubbleSort1(arr) {
let flag = true;
for (let i = 0; i < arr.length - 1; i++) {
if (flag) { //设置标识位，如果没有数据交换进行下一次循环
flag = false;
for (let j = 0; j < arr.length - 1 - i; j++) { //内层遍历
if (arr[j] > arr[j + 1]) { //比较内层循环里相邻的两个数
swap(arr,arr[j],arr[j + 1]);
flag = true;
}
}
}
}
return arr;
}
时间复杂度分析：
最好情况：数组是排序好的，不需要去改变元素位置所以时间复杂度为O(n)
最坏情况：数组是反序的，全部都需要换，所以是O(n^2);
平均情况：这里是我自己想的，平均就是从最好的情况一直加到最坏情况 / n（加了n次）
从最好的情况加到最坏情况：最好是O(n),差一点的就是需要移动一次，就是O(n * 1),两次就是O(n * 2),依次类推最后一次就是O(n * n-1),所以根据等差数列前n项和公式就是(n^2 + n) / 2，=>时间复杂度O(n^2)
平均时间复杂度是个人见解，如有不对请批评指正。
2、快速排序（Quick Sort）
快速排序的基本思路是基于分治法的：
在待排序表L中任取一个元素pivot作为基准（通常取首元素），通过一趟排序将待排序表分为独立的两部分L[1, k-1]和L[k+1, n]，使得L[1, k-1]中所有的元素小于pivot,L[K+1,n]中的所有元素大于pivot，则pivo放在了其最终位置L[k]上，这个过程称为一趟快速排序，然后分别递归的对两个子表重复上述过程，直到每部分内都只有一个元素或空为止，即所有元素都放在了最终位置上。
1）从数列中挑出一个元素，称为基准pivot。
2）重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准大的摆在基准后面（相同的树可以放到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3）递归地把小于基准值元素的子数列和大于基准值元素的子树列排列
function quckSort(arr, left, right) {
let len = arr.length;
let partitionIndex;
let left = typeof left != 'number' ? 0 : left;
let right = typeof right != 'number' ? len - 1 : right;
if(left < right) {
partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
return arr;
}
//分区操作
function partition(arr, left, right) {
//设定基准值pivot
let pivot = left;
let index= pivot + 1;
for(let i = index; i <= right; i++) {
if(arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
}
function swap(arr, i, j) {
vartemp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
2、插入排序
1、直接插入排序（Insertion Sort）
1）从第一个元素开始，该元素可以认为已经被排序；
2）取出下一个元素，在已经排序的元素序列中从后向前扫描；
3）如果该元素（已排序）大于新元素，将该元素移到下一位置；
4）重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5）将新元素插入到该位置后；
6）重复步骤2~5。
function InsertionSort(arr) {
let len = arr.length;
let preIndex, current;
for(let i = 1; i < len; i++) {
preIndex = i - 1; //当前项的前一项（从1开始，所以preIndex从0开始）
current = arr[i]; //当前项的值
//循环，将前一项后移一位，知道preIndex < 0或者 arr[preIndex] <= current
while(preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
return arr;
}
2、希尔排序（Shell Sort）
第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
1）选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1。
2）按增量序列个数k，对序列进行k 趟排序。
3）每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
function shellSort(arr) {
let len = arr.length;
let gap = Math.floor(len/2);
for(; gap > 0; gap = Math.floor(gap/2)) {
for(let i = gap; i < len; i++) {
let j = i;
let current = arr[i];
while(j - gap >= 0 && current < arr[j - gap]) {
arr[j] = aarr[j - gap];
j = j - gap;
}
arr[j] = currnt;
}
}
}
3、选择排序
1、简单选择排序（Selection Sort）
1）初始状态：无序区为R[1..n]，有序区为空；
2）第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个的新无序区；
3）n-1趟结束，数组有序化了。
function SelectionSort(arr) {
let len = arr.length;
let minIndex, temp;
for(let i = 0; i < len - 1; i++) { //这里是len - 1，因为只需要循环n - 1次
minIndex = i;
//查询最小数
for(let j = i + 1; j < len; j++) { //这里是len,因为要循环到最后一项。
if(arr[j] < arr[minIndex]) {
minIndex = j;
}
}
//交换
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
时间复杂度分析：
最好时间复杂度：O(n)
最坏时间复杂度：O(n^2)
平均时间复杂度：O(n^2)
2、堆排序（Heap Sort）
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
1）将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
2）将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
3）由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
let len
function buildMaxHeap(arr) {
len = arr.length;
for(let i = Math.floor(len / 2); i >= 0; i--) {
heapify(arr, i);
}
}
function heapify(arr, i) {
let left = 2 * i + 1,
let right = 2 * i + 2,
let largest = i;
if(left < len && arr[left] > arr[largest]) {
largest = left;
}
if(right < len && arr[right] > arr[largest]) {
largest = right;
}
if(largest != i) {
swap(arr, i, largest);
heapify(arr, largest);
}
}
function swap(arr, i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function heapSort(arr) {
buildMaxHeap(arr);
for(let i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0);
}
return arr;
}
4、归并排序
1、两路归并排序（Merge Sort）
归并排序是建立在归并操作上的一种有效的排序算法。
归并操作使用的是分治思想。
将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列段间有序。
1）把长度为n的输入序列分为两个长度为n/2的子序列。
2）对这两个子序列分别采用归并排序。
3）将两个排序好的子序列合并成一个最终的排序序列。
function mergeSort(arr) {
let len = arr.length;
if(len < 2) return arr;
let middle = Math.floor(len / 2);
let left = arr.slice(0, middle);
let right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
let resulr = [];
while(left.length > 0 && right.length > 0) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(reight.shift());
}
}
while(left.length) {
result.push(left.shift());
}
while(right.length) {
result.push(reight.shift());
}
return result;
}
排序算法
开场白
排序的基本概念与分类
排序算法的执行效率
排序算法的分类
排序算法具体实现及思路
1、交换排序
2、插入排序
3、选择排序
4、归并排序