尽管当初编程语言的库函数都提供了排序的性能，但经典的排序算法里利用了十分重要的算法思维，并且面试官也喜爱问它们。「排序算法」是十分好的学习材料。本篇文章将会举例列举集体认为比拟根本和重要的排序算法。
算法概述
算法分类
- 比拟类排序：通过比拟来决定元素间的绝对秩序，因为其工夫复杂度不能冲破O(nlogn)，因而也称为非线性工夫比拟类排序。
- 非比拟类排序：不通过比拟来决定元素间的绝对秩序，它能够冲破基于比拟排序的工夫下界，以线性工夫运行，因而也称为线性工夫非比拟类排序。
算法复杂度
相干概念
- 稳固：如果a本来在b后面，而a=b，排序之后a依然在b的后面。
- 不稳固：如果a本来在b的后面，而a=b，排序之后 a 可能会呈现在 b 的前面。
- 工夫复杂度：对排序数据的总的操作次数。反映当n变动时，操作次数出现什么法则。
- 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
冒泡排序
抉择排序(Selection-sort)是一种简略直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，寄存到排序序列的起始地位，而后，再从残余未排序元素中持续寻找最小（大）元素，而后放到已排序序列的开端。以此类推，直到所有元素均排序结束。
function selectionSort(arr) { var len = arr.length; var minIndex, temp; for (var i = 0; i < len - 1; i++) { minIndex = i; for (var j = i + 1; j < len; j++) { if (arr[j] < arr[minIndex]) { // 寻找最小的数 minIndex = j; // 将最小数的索引保留 } } temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } return arr;}插入排序
插入排序（Insertion-Sort）的算法形容是一种简略直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应地位并插入。
public class Solution { //实现插入的形式：一一替换到后面适合的地位 public int[] sortArray(int[] nums) { int len = nums.length; // 循环不变量：将 nums[i] 插入到区间 [0, i) 使之成为有序数组 for (int i = 1; i < len; i++) { for (int j = i; j > 0; j--) { if (nums[j - 1] > nums[j]) { swap(nums, j - 1, j); } else { break; } } } return nums; } private void swap(int[] nums, int index1, int index2) { int temp = nums[index1]; nums[index1] = nums[index2]; nums[index2] = temp; }}归并排序
所谓归并，就是将两个或两个以上的 有序 序列合并成一个新的有序序列的过程。
public class Solution { public int[] sortArray(int[] nums) { int len = nums.length; mergeSort(nums, 0, len - 1); return nums; } /** * 对数组 nums 的子区间 [left..right] 进行归并排序 * * @param nums * @param left * @param right */ private void mergeSort(int[] nums, int left, int right) { if (left == right) { return; } int mid = left + (right - left) / 2; mergeSort(nums, left, mid); mergeSort(nums, mid + 1, right); mergeOfTwoSortedArray(nums, left, mid, right); } /** * 合并两个有序数组：先把值复制到长期数组，再合并回去 * * @param nums * @param left * @param mid [left, mid] 有序，[mid + 1, right] 有序 * @param right */ private void mergeOfTwoSortedArray(int[] nums, int left, int mid, int right) { // 每做一次合并，都 new 数组用于归并，开销大 int len = right - left + 1; int[] temp = new int[len]; for (int i = 0; i < len; i++) { temp[i] = nums[left + i]; } // i 和 j 别离指向前有序数组和后有序数组的起始地位 int i = 0; int j = mid - left + 1; for (int k = 0; k < len; k++) { // 先写 i 和 j 越界的状况（若i越界则让j归并回去,j++） if (i == mid + 1 - left) { nums[left + k] = temp[j]; j++; } else if (j == right + 1 - left) { nums[left + k] = temp[i]; i++; } else if (temp[i] <= temp[j]) { // 留神：这里必须写成 <=，否则归并排序就成了非稳固的排序 nums[left + k] = temp[i]; i++; } else { nums[left + k] = temp[j]; j++; } } }}工夫复杂度
空间复杂度
归并须要 O(N)这么多的辅助空间，递归调用的深度是 O(logN)，因而空间复杂度是 O(N + log N) =O(N)（计算复杂度的时候，两个加法项，保留较大的那个项）。
疾速排序
疾速排序和归并排序一样采纳了分而治之的思维，根本思维：通过一趟排序将待排记录分隔成独立的两局部，其中一部分记录的关键字均比另一部分的关键字小，则可别离对这两局部记录持续进行排序，以达到整个序列有序。
public class Solution { public int[] sortArray(int[] nums) { int len = nums.length; quickSort(nums, 0, len - 1); return nums; } private void quickSort(int[] nums, int left, int right) { // 留神：这里包含 > 的状况，与归并排序不同，请通过调试了解这件事件 if (left >= right) { return; } int p = partition(nums, left, right); quickSort(nums, left, p - 1); quickSort(nums, p + 1, right); } private int partition(int[] nums, int left, int right) { int pivot = nums[left]; // 循环不变量： lt 意即 less than // [left + 1, lt] < pivot， // [lt + 1, i) >= pivot int lt = left; // 留神，这里取等号 for (int i = left + 1; i <= right; i++) { if (nums[i] < pivot) { // 替换以后元素与 lt 的地位 lt++; swap(nums, i, lt); } } // 最初这一步要记得替换到切分元素 swap(nums, left, lt); return lt; } private void swap(int[] nums, int index1, int index2) { int temp = nums[index1]; nums[index1] = nums[index2]; nums[index2] = temp; }}扩大：O(n) 工夫复杂度内求无序数组中的第 K 大元素
咱们抉择数组区间 A[0...n-1]的最初一个元素 A[n-1]作为 pivot，对数组 A[0...n-1]原地分区，这样数组就分成了三局部，A[0...p-1]、A[p]、A[p+1...n-1]。如果 p+1=K，那 A[p]就是要求解的元素；如果 K>p+1, 阐明第 K 大元素呈现在 A[p+1...n-1]区间，咱们再依照下面的思路递归地在 A[p+1...n-1]这个区间内查找。
堆排序
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。沉积是一个近似齐全二叉树的构造，并同时满足沉积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
- 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列
- 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列
/** * 下沉操作 * @param {array} arr 待调整的堆 * @param {number} parentIndex 要下沉的父节点 * @param {number} length 堆的无效大小 */function downAdjust(arr, parentIndex, length) { // temp保留父节点的值，用于最初赋值 let temp = arr[parentIndex] let childrenIndex = 2 * parentIndex + 1 while(childrenIndex < length) { // 如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子 // 这里其实是比拟左、右子树的大小，抉择更大的 if (childrenIndex + 1 < length && arr[childrenIndex + 1] > arr[childrenIndex]) { childrenIndex++ } // 如果父节点大于任何一个孩子得值，则间接跳出 if (temp >= arr[childrenIndex]) { break } // 当左、右子树比父节点更大，进行替换 arr[parentIndex] = arr[childrenIndex] parentIndex = childrenIndex childrenIndex = 2 * childrenIndex + 1 } arr[parentIndex] = temp}/** * 堆排序(升序) * @param {array} arr 待调整的堆 */function heapSort(arr) { // 把无序数组构建成最大堆, 这里-2,是因为从索引0开始、另外就是叶子节点【最初一层是不须要堆化的】 for(let i = (arr.length - 2)/2; i >= 0; i--) { downAdjust(arr, i, arr.length) } // 循环删除堆顶元素，并且移到汇合尾部，调整堆产生新的堆顶 for(let i = arr.length - 1; i > 0; i--) { // 替换最初一个元素与第一个元素 let temp = arr[i] arr[i] = arr[0] arr[0] = temp // 下沉调整最大堆 downAdjust(arr, 0, i) } return arr}// test caseconsole.log(heapSort([4, 4, 6, 5, 3, 2, 8, 1]))