【排序算法】一篇文章带你搞懂所有排序！

文章目录

• 一、排序
  • 1.1排序的概念
  • 1.2 常见的排序算法
• 二、常见的排序算法实现
  • 2.1 插入排序
    • 2.1.1.基本思想
    • 2.1.2.直接插入排序
    • 2.1.3 希尔排序
  • 2.1 选择排序
    • 2.2.1基本思想：
    • 2.2.2 直接排序选择
    • 2.2.3 堆排序
  • 2.3 交换排序
    • 2.3.1冒泡排序
    • 2.3.2. 快速排序
  • 2.4 归并排序
    • 2.4.1 基本思想
    • 2.4.2 归并排序总结
    • 2.4.3 海量数据的排序问题
• 三、排序算法复杂度及稳定性分析
• 总结

一、排序

1.1排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

1.2 常见的排序算法

二、常见的排序算法实现

2.1 插入排序

2.1.1.基本思想

直接插入排序是一种简单的插入排序法，其基本思想是：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

2.1.2.直接插入排序

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。

代码实现：

publicclassInsertionSort{/** * 直接插入排序算法 * @param arr 待排序的数组 */publicstaticvoidinsertionSort(int[] arr){// 数组为空或只有一个元素时，直接返回if(arr ==null|| arr.length <=1){return;}// 从第二个元素开始遍历（第一个元素默认已排序）for(int i =1; i < arr.length; i++){// 待插入的元素int key = arr[i];// 与已排序部分的元素比较，从已排序部分的末尾开始int j = i -1;// 将大于key的元素向后移动一位while(j >=0&& key < arr[j]){ arr[j +1]= arr[j]; j--;}// 将key插入到正确位置 arr[j +1]= key;}}// 测试方法publicstaticvoidmain(String[] args){// 测试数组int[] testArr ={32,26,87,72,26,17};System.out.print("原始序列: ");printArray(testArr);// 调用排序方法insertionSort(testArr);System.out.print("排序后序列: ");printArray(testArr);}// 辅助方法：打印数组privatestaticvoidprintArray(int[] arr){for(int num : arr){System.out.print(num +" ");}System.out.println();}}

直接插入排序的特性总结：

1 . 元素集合越接近有序，直接插入排序算法的时间效率越高
2 . 时间复杂度：O(N^2)
3 . 空间复杂度：O(1)，它是一种稳定的排序算法
4 . 稳定性：稳定

2.1.3 希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：选定一个整数（增量），把待排序文件里的所有记录分成多个组，所有距离为该增量的记录分在同一组内，然后对每一组内的记录进行排序。之后，减小这个增量，重复上述分组和排序的操作。当增量最终变为 1 时，所有记录在同一个组内排好序。

下面为一个希尔排序的流程：

希尔排序代码实现：

publicclassShellSort{publicstaticvoidshellSort(int[] arr){int n = arr.length;// 初始增量设为数组长度的一半，之后每次减半for(int gap = n /2; gap >0; gap /=2){for(int i = gap; i < n; i++){int temp = arr[i];int j;// 对间隔为gap的子序列进行直接插入排序for(j = i; j >= gap && arr[j - gap]> temp; j -= gap){ arr[j]= arr[j - gap];} arr[j]= temp;}}}publicstaticvoidmain(String[] args){int[] arr ={12,34,54,2,26,9,17,5};System.out.print("原始数组: ");for(int num : arr){System.out.print(num +" ");}shellSort(arr);System.out.print("\n排序后的数组: ");for(int num : arr){System.out.print(num +" ");}}}

希尔排序的特性总结：

1 . 希尔排序是对直接插入排序的优化。
2 . 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很
快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3 . 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定
4 . 稳定性：不稳定

2.1 选择排序

2.2.1基本思想：

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

2.2.2 直接排序选择

在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素
若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

直接排序代码示例：

// 直接插入排序方法publicstaticvoiddirectInsertionSort(int[] arr){// 数组为空或长度小于2，无需排序if(arr ==null|| arr.length <2){return;}// 从第二个元素开始遍历（第一个个元素默认已排序）for(int i =1; i < arr.length; i++){// 保存当前待插入的元素int current = arr[i];// 已排序部分的最后一个元素索引int j = i -1;// 在已排序部分中找到合适的插入位置// 将大于current的元素依次向后移动while(j >=0&& arr[j]> current){ arr[j +1]= arr[j]; j--;}// 将当前元素插入到正确位置 arr[j +1]= current;}}// 测试方法publicstaticvoidmain(String[] args){int[] array ={35,26,18,47,52,9,13};System.out.print("排序前: ");for(int num : array){System.out.print(num +" ");}directInsertionSort(array);System.out.print("\n排序后: ");for(int num : array){System.out.print(num +" ");}}

直接选择排序的特性总结：

1 . 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2 . 时间复杂度：O(N^2)
3 . 空间复杂度：O(1)
4 . 稳定性：不稳定

2.2.3 堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

代码实现：

// 二叉树节点类classTreeNode{int value;TreeNode left;// 左子节点TreeNode right;// 右子节点TreeNode parent;// 父节点引用（方便向上调整）publicTreeNode(int value){this.value = value;this.left =null;this.right =null;this.parent =null;}}publicclassHeapSortWithTree{// 堆的根节点privateTreeNode root;// 记录堆的大小privateint size;// 记录最后一个节点（用于插入和交换）privateTreeNode lastNode;/** * 堆排序主方法 * @param array 待排序数组 * @return 排序后的数组 */publicint[]sort(int[] array){if(array ==null|| array.length <=1){return array;}// 1. 构建最大堆buildMaxHeap(array);// 2. 执行堆排序int[] result =newint[array.length];for(int i = array.length -1; i >=0; i--){// 提取堆顶元素（最大值） result[i]=extractMax();}return result;}/** * 构建最大堆 */privatevoidbuildMaxHeap(int[] array){ root =null; size =0; lastNode =null;// 逐个插入元素并调整堆for(int num : array){insert(num);}}/** * 向堆中插入元素 */privatevoidinsert(int value){TreeNode newNode =newTreeNode(value); size++;if(root ==null){// 堆为空时，新节点作为根节点 root = newNode; lastNode = root;return;}// 找到插入位置（按完全二叉树规则）TreeNode parent =findInsertParent();if(parent.left ==null){ parent.left = newNode;}else{ parent.right = newNode;} newNode.parent = parent; lastNode = newNode;// 向上调整以维持最大堆特性bubbleUp(newNode);}/** * 找到新元素应该插入的父节点（保持完全二叉树结构） */privateTreeNodefindInsertParent(){// 使用广度优先搜索找到第一个左或右子节点为空的节点List<TreeNode> queue =newArrayList<>(); queue.add(root);while(!queue.isEmpty()){TreeNode current = queue.remove(0);if(current.left ==null|| current.right ==null){return current;} queue.add(current.left); queue.add(current.right);}returnnull;// 理论上不会到达这里}/** * 向上调整：将节点与父节点比较，确保父节点值更大 */privatevoidbubbleUp(TreeNode node){while(node.parent !=null&& node.value > node.parent.value){// 交换节点与父节点的值int temp = node.value; node.value = node.parent.value; node.parent.value = temp;// 继续向上调整 node = node.parent;}}/** * 向下调整：从指定节点开始，确保子树满足最大堆特性 */privatevoidbubbleDown(TreeNode node){while(true){TreeNode largest = node;// 找到左右子节点中的最大值if(node.left !=null&& node.left.value > largest.value){ largest = node.left;}if(node.right !=null&& node.right.value > largest.value){ largest = node.right;}// 如果当前节点已是最大值，则无需继续调整if(largest == node){break;}// 交换值int temp = node.value; node.value = largest.value; largest.value = temp;// 继续向下调整 node = largest;}}/** * 提取堆顶最大元素，并重新调整堆 */privateintextractMax(){if(root ==null){thrownewIllegalStateException("堆为空");}int maxValue = root.value; size--;if(size ==0){// 堆已空 root =null; lastNode =null;return maxValue;}// 将最后一个节点的值移到根节点 root.value = lastNode.value;// 更新最后一个节点TreeNode newLastNode =findNewLastNode();// 断开原最后一个节点的连接if(lastNode.parent !=null){if(lastNode.parent.right == lastNode){ lastNode.parent.right =null;}else{ lastNode.parent.left =null;}} lastNode = newLastNode;// 从根节点开始向下调整bubbleDown(root);return maxValue;}/** * 找到删除最后一个节点后的新最后一个节点 */privateTreeNodefindNewLastNode(){if(size ==1){return root;}// 使用广度优先搜索找到倒数第二个节点List<TreeNode> queue =newArrayList<>(); queue.add(root);TreeNode result = root;for(int i =0; i < size -1; i++){TreeNode current = queue.remove(0); result = current;if(current.left !=null){ queue.add(current.left);}if(current.right !=null){ queue.add(current.right);}}return result;}// 测试方法publicstaticvoidmain(String[] args){HeapSortWithTree heapSort =newHeapSortWithTree();int[] array ={14,10,8,7,9,3,2,4,1};System.out.print("排序前: ");for(int num : array){System.out.print(num +" ");}int[] sortedArray = heapSort.sort(array);System.out.print("\n排序后: ");for(int num : sortedArray){System.out.print(num +" ");}}}

堆排序的特性总结：

1 . 堆排序使用堆来选数，效率就高了很多。
2 . 时间复杂度：O(N*logN)
3 . 空间复杂度：O(1)
4 . 稳定性：不稳定

2.3 交换排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

2.3.1冒泡排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

代码实现：

/** * 基础版冒泡排序 * 每次遍历将最大元素"浮"到末尾 */publicstaticvoidbubbleSortBasic(int[] arr){if(arr ==null|| arr.length <=1){return;}int n = arr.length;// 外层循环控制需要进行多少轮比较for(int i =0; i < n -1; i++){// 内层循环进行每轮的比较和交换// 每轮结束后，最大的元素已"浮"到末尾，下一轮可减少一次比较for(int j =0; j < n -1- i; j++){// 如果当前元素大于下一个元素，则交换if(arr[j]> arr[j +1]){int temp = arr[j]; arr[j]= arr[j +1]; arr[j +1]= temp;}}}}/** * 优化版冒泡排序 * 添加标志位，当某轮未发生交换时说明数组已有序，可提前结束 */publicstaticvoidbubbleSortOptimized(int[] arr){if(arr ==null|| arr.length <=1){return;}int n = arr.length;boolean swapped;// 标志位，记录本轮是否发生过交换for(int i =0; i < n -1; i++){ swapped =false;for(int j =0; j < n -1- i; j++){if(arr[j]> arr[j +1]){// 交换元素int temp = arr[j]; arr[j]= arr[j +1]; arr[j +1]= temp; swapped =true;}}// 如果本轮没有交换，说明数组已完全有序，直接退出if(!swapped){break;}}}// 测试方法publicstaticvoidmain(String[] args){int[] testArr1 ={64,34,25,12,22,11,90};int[] testArr2 ={5,1,4,2,8};System.out.print("基础版排序前: ");printArray(testArr1);bubbleSortBasic(testArr1);System.out.print("基础版排序后: ");printArray(testArr1);System.out.print("\n优化版排序前: ");printArray(testArr2);bubbleSortOptimized(testArr2);System.out.print("优化版排序后: ");printArray(testArr2);}// 辅助方法：打印数组privatestaticvoidprintArray(int[] arr){for(int num : arr){System.out.print(num +" ");}System.out.println();}

冒泡排序的特性总结：

1 . 冒泡排序是一种非常容易理解的排序
2 . 时间复杂度：O(N^2)
3 . 空间复杂度：O(1)
4 . 稳定性：稳定

2.3.2. 快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

// 假设按照升序对array数组中[left, right)区间中的元素进行排序voidQuickSort(int[] array,int left,int right){if(right - left <=1){return;}// 按照基准值对array数组的 [left, right)区间中的元素进行划分int div =partion(array, left, right);// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)// 递归排[left, div)QuickSort(array, left, div);// 递归排[div+1, right)QuickSort(array, div +1, right);}

上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。

将区间按照基准值划分为左右两半部分的常见方式有：

1. Hoare版

privatestaticintpartition(int[] array,int left,int right){int i = left;int j = right;int pivot = array[left];while(i < j){while(i < j && array[j]>= pivot){ j--;}while(i < j && array[i]<= pivot){ i++;}swap(array, i, j);}swap(array, i, left);return i;}

2. 挖坑法

privatestaticintpartition(int[] array,int left,int right){int i = left;int j = right;int pivot = array[left];while(i < j){while(i < j && array[j]>= pivot){ j--;} array[i]= array[j];while(i < j && array[i]<= pivot){ i++;} array[j]= array[i];} array[i]= pivot;return i;}

3. 前后指针

写法一：

privatestaticintpartition(int[] array,int left,int right){int prev = left;int cur = left +1;while(cur <= right){if(array[cur]< array[left]&& array[++prev]!= array[cur]){swap(array, cur, prev);} cur++;}swap(array, prev, left);return prev;}

写法二：

privatestaticintpartition(int[] array,int left,int right){int d = left +1;int pivot = array[left];for(int i = left +1; i <= right; i++){if(array[i]< pivot){swap(array, i, d); d++;}}swap(array, d -1, left);return d -1;}

快速排序优化

1. 三数取中法选key
2. 递归到小的子区间时，可以考虑使用插入排序

快速排序非递归

voidquickSortNonR(int[] a,int left,int right){Stack<Integer> st =newStack<>(); st.push(left); st.push(right);while(!st.empty()){ right = st.pop(); left = st.pop();if(right - left <=1)continue;int div =PartSort1(a, left, right);// 以基准值为分割点，形成左右两部分：[left, div) 和 [div+1, right)  st.push(div +1); st.push(right); st.push(left); st.push(div);}}

快速排序总结

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)

2.4 归并排序

2.4.1 基本思想

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：

代码示例：

/** * 归并排序主方法 * @param arr 待排序的数组 */publicstaticvoidmergeSort(int[] arr){if(arr ==null|| arr.length <=1){return;// 数组为空或只有一个元素时无需排序}// 创建临时数组用于合并操作，避免频繁创建销毁int[] temp =newint[arr.length];// 调用递归排序方法sort(arr,0, arr.length -1, temp);}/** * 递归分治排序 * @param arr 待排序数组 * @param left 左边界索引 * @param right 右边界索引 * @param temp 临时数组 */privatestaticvoidsort(int[] arr,int left,int right,int[] temp){if(left < right){// 找到中间位置，将数组分为两部分int mid = left +(right - left)/2;// 避免直接(left+right)可能的溢出// 递归排序左半部分sort(arr, left, mid, temp);// 递归排序右半部分sort(arr, mid +1, right, temp);// 合并已排序的两部分merge(arr, left, mid, right, temp);}}/** * 合并两个已排序的子数组 * @param arr 原数组 * @param left 左子数组起始索引 * @param mid 中间索引（左子数组结束索引） * @param right 右子数组结束索引 * @param temp 临时数组，用于存放合并结果 */privatestaticvoidmerge(int[] arr,int left,int mid,int right,int[] temp){int i = left;// 左子数组的起始索引int j = mid +1;// 右子数组的起始索引int t =0;// 临时数组的当前索引// 比较两个子数组的元素，将较小的元素放入临时数组while(i <= mid && j <= right){if(arr[i]<= arr[j]){ temp[t++]= arr[i++];}else{ temp[t++]= arr[j++];}}// 将左子数组剩余元素复制到临时数组while(i <= mid){ temp[t++]= arr[i++];}// 将右子数组剩余元素复制到临时数组while(j <= right){ temp[t++]= arr[j++];}// 将临时数组中的结果复制回原数组 t =0;while(left <= right){ arr[left++]= temp[t++];}}// 测试方法publicstaticvoidmain(String[] args){int[] testArr ={12,11,13,5,6,7};System.out.print("排序前: ");printArray(testArr);mergeSort(testArr);System.out.print("排序后: ");printArray(testArr);}// 辅助方法：打印数组privatestaticvoidprintArray(int[] arr){for(int num : arr){System.out.print(num +" ");}System.out.println();}

2.4.2 归并排序总结

1 . 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2 . 时间复杂度：O(N*logN)
3 . 空间复杂度：O(N)
4 . 稳定性：稳定

2.4.3 海量数据的排序问题

外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1G，需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序

先把文件切分成 200 份，每个 512 M分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了

三、排序算法复杂度及稳定性分析

总结

本篇文章介绍了常见的排序，通过对代码和原理解释了各个算法的特征。最后介绍了对各种算法的复杂度及稳定度分析。
以上就是本文全部内容，感谢各位能够看到最后，如有问题，欢迎各位大佬在评论区指正，希望大家可以有所收获！创作不易，希望大家多多支持！