前言：
本文章主要是讲解我个人在学习Java开发环境的排序算法时做的一些准备，以及个人的心得体会，汇集成本篇文章，作为自己对排序算法理解的总结与笔记。
内容主要是 关于十大经典排序算法的简介、原理、动静态图解和源码实现的分析 。
对于一名程序员来讲，我们都知道《数据结构与算法》起初是用于C语言居多，然而在Java语言下使用算法的案例却很少，因此，特别整理了在Java开发环境的十大经典排序算法，供大家一起学习讨论。 一、排序算法1.排序算法概述（百度百科）：
所谓排序算法，即通过特定的算法因式将一组或多组数据按照既定模式进行重新排序。这种新序列遵循着一定的规则，体现出一定的规律，因此，经处理后的数据便于筛选和计算，大大提高了计算效率。对于排序，我们首先要求其具有一定的稳定性，即当两个相同的元素同时出现于某个序列之中，则经过一定的排序算法之后，两者在排序前后的相对位置不发生变化。换言之，即便是两个完全相同的元素，它们在排序过程中也是各有区别的，不允许混淆不清。 2.《数据结构与算法》中的排序算法
常见的排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。
算法图解（菜鸟教程借图）：
图解分析：
3.算法分析
时间复杂度
平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。
线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；
O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序
线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。
关于稳定性
稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。
不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。
名词解释： n：数据规模 k：＂桶＂的个数 In-place：占用常数内存，不占用额外内存 Out-place：占用额外内存 稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同 平均时间复杂度 是指所有可能的输入实例均以等概率的出现情况下得到算法的运行时间 最坏时间复杂度 ，一般讨论的时间复杂度均是最坏情况下的时间复杂度，这样做的原因是最坏情况下的时间复杂度是算法在任何输入实例上运行的界限，这就保证了算法的运行时间不会比最坏情况更长。 平均时间复杂度和最坏时间复杂度 是否一样，这就需要根据算法不同而不同了。 二、十大经典排序算法（Java开发版）
PS：案例均以数组{15，63，97，12，235，66}排序为例 1.冒泡排序
冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢＂浮＂到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名＂冒泡排序＂。 1.1实现原理比较相邻的元素。如果第一个比第二个大，就交换他们两个。 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 针对所有的元素重复以上的步骤，除了最后一个。 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
1.2实例展示1 import java.util.Arrays; 2 public class BubbleSort { 3 public static void main(String[] args) { 4 int[] arrays =new int[]{15,63,97,12,235,66}; 5 for (int i=0;i arrays[j+1]){ 10 int temp = 0;//类似空桶 11 temp = arrays[j]; //A桶中水倒入空桶C中 12 arrays[j] = arrays[j+1];//把B桶的水倒入A桶中 13 arrays[j+1] = temp;//把C桶的水倒入B桶中 14 } 15 } 16 } 17 System.out.println(Arrays.toString(arrays)); 18 } 19 }
排序结果展示：
2.快速排序
快速排序（Quicksort），计算机科学词汇，适用领域Pascal，c++等语言，是对冒泡排序算法的一种改进。 2.1实现原理
快速排序是对冒泡排序的一种改进。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分所有的数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列 从数列中挑出一个元素，称为 ＂基准＂（pivot）; 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作； 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
2.2 动图演示
2.3实例展示1 import java.util.Arrays; 2 public class QuickSort { 3 public static void main(String[] args) { 4 int[] arrays = new int[]{15,63,97,12,235,66}; 5 sort(arrays,0,arrays.length-1); 6 System.out.println(Arrays.toString(arrays)); 7 } 8 public static void sort(int[] arrays,int left,int right){ 9 int l = left; 10 int r = right; 11 12 int pivot = arrays[(left+right)/2]; 13 int temp = 0; 14 while (lpivot){ 22 r--; 23 } 24 if (l>=r){ 25 break; 26 } 27 temp = arrays[l]; 28 arrays[l] = arrays[r]; 29 arrays[r] = temp; 30 31 // 交换完数据arrays[l] = pivot 32 if (arrays[l]==pivot){ 33 r--; 34 } 35 if (arrays[r]==pivot){ 36 l++; 37 } 38 if (r==l){ 39 l++; 40 r--; 41 } 42 if (leftl){ 46 sort(arrays,l,right); 47 } 48 } 49 } 50 }
排序结果展示：
3.基数排序
基数排序（radix sort）属于＂分配式排序＂（distribution sort），又称＂桶子法＂（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些＂桶＂中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
基数排序是1887年赫尔曼、何乐礼发明的。思想是讲整数按位数切割成不同的数字，然后按每个位数分别比较。 3.1实现原理
将所有的待比较数值统一设置为同样的数位长度，位数比较短的数前面补零，然后从最地位开始依次进行一次排序，这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
3.2实例展示1 import java.text.SimpleDateFormat; 2 import java.util.Arrays; 3 import java.util.Date; 4 5 public class BasicSort { 6 7 public static void main(String[] args) { 8 int[] arrays = new int[]{15,63,97,12,235,66}; 9 SimpleDateFormat simpleDateFormat =new SimpleDateFormat(＂yyyy-mm-dd HH:MM:ss:SS＂); 10 System.out.println(＂开始排序前:＂+simpleDateFormat.format(new Date())); 11 sort(arrays); 12 System.out.println(＂排序结束:＂+simpleDateFormat.format(new Date())); 13 } 14 15 // 1.获取原序列的最大位多少 16 // @param arrays 17 public static void sort(int[] arrays){ 18 19 // 获取最大位数 20 int max = 0; 21 for(int i=0;imax){ 23 max = arrays[i]; 24 } 25 } 26 27 // 获取字符串长度，所以把int类型转字符串类型 28 int maxLength = (max+＂＂).length(); 29 30 // 定义二维数组，大小10，表示10个桶，每一个桶则是一个数组 31 // [[],[],[],[],[]...] 32 int[][] bucket = new int[10][arrays.length]; 33 34 // 辅助数组 35 int[] bucketElementCount = new int[10]; 36 37 // 循环获取无序数列 38 for (int j=0;j 排序结果展示：
插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 。插入排序是一种最简单的 排序 方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动 。
插入排序的工作方式像许多人排序一手扑克牌。开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的，原来这些牌是桌子上牌堆中顶部的牌。
插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。
实例展示
1 public class InsertSort { 2 public static void main(String[] args) { 3 int[] array = new int[]{15,63,97,12,235,66}; 4 //控制拿去每一个元素 5 for(int i=1;i=1;j--){ 8 //是否小于前面的元素 9 if (array[j]排序结果展示：
选择排序（Selection sort）是一种简单直观的排序算法。
和插入排序算法类似，一定要注意区分。
第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
1 import java.util.Arrays; 2 public class SelectSort { 3 public static void main(String[] args) { 4 int[] arr = new int[]{15,63,97,12,235,66}; 5 for (int i=0;ii;j--){ 8 9 if (arr[j]排序结果展示：
希尔排序(Shell＂s Sort)是插入排序的一种又称＂缩小增量排序＂（Diminishing Increment Sort），是 插入排序 算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2
般的初次取序列的一半为增量，以后每次减半，直到增量为1。
1 import java.util.Arrays; 2 public class ShellSort { 3 public static void main(String[] args) { 4 int[] array = new int[]{15,63,97,12,235,66}; 5 6 // 实现增量变化 7 for (int gap = array.length/2;gap>0;gap/=2){ 8 9 for (int i=gap;i=0;j-=gap){ 12 if (array[j]>array[j+gap]){ 13 int temp = 0; 14 temp = array[j]; 15 array[j] = array[j+gap]; 16 array[j+gap] = temp; 17 } 18 } 19 } 20 } 21 System.out.println(Arrays.toString(array)); 22 } 23 }
排序结果展示：
7.归并排序
归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 7.1实现原理第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置 第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置重复步骤3直到某一指针超出序列尾将另一序列剩下的所有元素直接复制到合并序列尾
我们需要将两个已经有序的子序列合并成一个有序序列，比如上图最后一次合并，将[2,4,5,6]和[1,3,7,8]已经有序的子序列合并最终序列[1,2,3,4,5,6,7,8]
7.2实例展示1 import java.util.Arrays; 2 public class MSort { 3 public static void main(String[] args) { 4 int[] array = new int[]{15,63,97,12,235,66}; 5 //临时数组 6 int[] temp = new int[array.length]; 7 sort(array,0,array.length-1,temp); 8 System.out.println(Arrays.toString(array)); 9 10 } 11 public static void sort(int[] array,int left,int right,int[] temp){ 12 if (leftO(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序，堆排序） 8.1实现原理
假设输入的线性表L的长度为n，L=L1,L2,..,Ln；线性表的元素属于有限偏序集S，|S|=k且k=O(n)，S={S1,S2,..Sk}；则计数排序可以描述如下： 扫描整个集合S，对每一个Si∈S，找到在线性表L中小于等于Si的元素的个数T(Si)； 扫描整个线性表L，对L中的每一个元素Li，将Li放在输出线性表的第T(Li)个位置上，并将T(Li)减1。
8.2实例展示1 public class CountSort { 2 public static void main(String[]args){ 3 //排序的数组 4 int a[]={15,63,97,12,235,66}; 5 int b[]=countSort(a); 6 for(int i:b){ 7 System.out.print( i+＂,＂); 8 } 9 System.out.println(); 10 } 11 public static int[] countSort(int[]a){ 12 int b[] = new int[a.length]; 13 int max = a[0],min = a[0]; 14 for(int i:a){ 15 if(i>max){ 16 max=i; 17 } 18 if(i= 0; i--) { 11 adjustHeap(array, i, array.length); //调整堆 12 } 13 14 // 上述逻辑，建堆结束 15 // 下面，开始排序逻辑 16 for (int j = array.length - 1; j > 0; j--) { 17 // 元素交换,作用是去掉大顶堆 18 // 把大顶堆的根元素，放到数组的最后；换句话说，就是每一次的堆调整之后，都会有一个元素到达自己的最终位置 19 swap(array, 0, j); 20 // 元素交换之后，毫无疑问，最后一个元素无需再考虑排序问题了。 21 // 接下来我们需要排序的，就是已经去掉了部分元素的堆了，这也是为什么此方法放在循环里的原因 22 // 而这里，实质上是自上而下，自左向右进行调整的 23 adjustHeap(array, 0, j); 24 } 25 } 26 27 /** 28 * 整个堆排序最关键的地方 29 * @param array 待组堆 30 * @param i 起始结点 31 * @param length 堆的长度 32 */ 33 public static void adjustHeap(int[] array, int i, int length) { 34 // 先把当前元素取出来，因为当前元素可能要一直移动 35 int temp = array[i]; 36 for (int k = 2 * i + 1; k < length; k = 2 * k + 1) { //2*i+1为左子树i的左子树(因为i是从0开始的),2*k+1为k的左子树 37 // 让k先指向子节点中最大的节点 38 if (k + 1 < length && array[k] < array[k + 1]) { //如果有右子树,并且右子树大于左子树 39 k++; 40 } 41 //如果发现结点(左右子结点)大于根结点，则进行值的交换 42 if (array[k] > temp) { 43 swap(array, i, k); 44 // 如果子节点更换了，那么，以子节点为根的子树会受到影响,所以，循环对子节点所在的树继续进行判断 45 i = k; 46 } else { //不用交换，直接终止循环 47 break; 48 } 49 } 50 } 51 52 /** 53 * 交换元素 54 * @param arr 55 * @param a 元素的下标 56 * @param b 元素的下标 57 */ 58 public static void swap(int[] arr, int a, int b) { 59 int temp = arr[a]; 60 arr[a] = arr[b]; 61 arr[b] = temp; 62 } 63 }
排序结果展示：
10.桶排序
桶排序 (Bucket sort)或所谓的 箱排序 ，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（ n ））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。 10.1实现原理
假定：输入是由一个随机过程产生的[0, 1)区间上均匀分布的实数。将区间[0, 1)划分为n个大小相等的子区间（桶），每桶大小1/n：[0, 1/n)， [1/n, 2/n)， [2/n, 3/n)，…，[k/n, (k+1)/n )，…将n个输入元素分配到这些桶中，对桶中元素进行排序，然后依次连接桶输入0 ≤A[1..n] <1辅助数组B[0..n-1]是一指针数组，指向桶（链表）。
然后，元素在每个桶中排序：
10.2 动图演示
10.3实例展示 1 public class BucketSort { 2 public static void main(String[] args) { 3 int[] array = new int[]{15,63,97,12,235,66}; 4 heapsort(array); 5 System.out.println(Arrays.toString(array)); 6 } 7 8 //声明全局变量，用于记录数组array的长度； 9 static int len; 10 /** 11 * 堆排序算法 12 * @param array 13 * @return 14 */ 15 public static int[] heapsort(int[] array) { 16 len = array.length; 17 if (len < 1) return array; 18 //1.构建一个最大堆 19 buildMaxHeap(array); 20 //2.循环将堆首位（最大值）与末位交换，然后在重新调整最大堆 21 while (len > 0) { 22 swap(array, 0, len - 1); 23 len--; 24 adjustHeap(array, 0); 25 } 26 return array; 27 } 28 /** 29 * 建立最大堆 30 * @param array 31 */ 32 public static void buildMaxHeap(int[] array) { 33 //从最后一个非叶子节点开始向上构造最大堆 34 for (int i = (len/2 - 1); i >= 0; i--) { //感谢 @让我发会呆 网友的提醒，此处应该为 i = (len/2 - 1) 35 adjustHeap(array, i); 36 } 37 } 38 /** 39 * 调整使之成为最大堆 40 * @param array 41 * @param i 42 */ 43 public static void adjustHeap(int[] array, int i) { 44 int maxIndex = i; 45 //如果有左子树，且左子树大于父节点，则将最大指针指向左子树 46 if (i * 2 < len && array[i * 2] > array[maxIndex]) 47 maxIndex = i * 2; 48 //如果有右子树，且右子树大于父节点，则将最大指针指向右子树 49 if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex]) 50 maxIndex = i * 2 + 1; 51 //如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。 52 if (maxIndex != i) { 53 swap(array, maxIndex, i); 54 adjustHeap(array, maxIndex); 55 } 56 } 57 }
排序结果展示：
总结：
个人认为，对排序算法的学习，主要是对各个算法的工作原理和思想进行·分析。
例：当你想要学习冒泡排序算法时，你应该先要了解冒泡排序所工作的原理和整体思想是如何的，然后对症下药，分析排序时是进行怎样的对比和如何循环嵌套的，再来应用编程思想对其进行代码整理，然后根据个人编程习惯运用判断语句、循环语句和函数等方法将整个流程给实现出来，最后再进行调试，作出分析，以求是否有更好的方法实现其功能，进一步完善自己的算法，提高代码执行效率。
记得点赞关注+转发！！！ 
什么是生酮饮食？生酮饮食是一种食物策略，在这种策略中，您可以大幅减少碳水化合物的摄入量并用脂肪代替它，以使新陈代谢达到称为酮症的状态。生酮饮食是将你的身体脂肪转化为燃料来燃烧能量。那么首选的燃料是保温杯里加两宝，疏肝理气，活血化瘀，让你气血通畅，一身轻松近日，70多岁的李大爷身体出现了异样，早上醒来总是感觉头疼脑胀，心慌气短，腹部还有不适的感觉。李大爷自己觉得这些不是正常的老年人的身体反应，于是便来到了一家医院就诊。通过医生的问诊顽痰肾虚痰多脾虚浓痰肝郁，中医教你健脾补肾，疏肝化痰不知道你有没有听过一句话顽痰肾虚痰多脾虚浓痰肝郁，这到底是什么意思呢？请往下看！1顽痰肾虚这类人的痰非常难化，就像胶水一样黏在喉咙上，咳不出去，也咽不下去，很多人认为这是脾虚的问题春季宜疏肝养阳，送你两味药，疏肝解郁，补气升阳，让你浑身舒畅大家好，我是胡医生。今天胡医生想给大家分享一个比较适合在春天疏肝养阳的小妙方，可以疏肝解郁，补气升阳。毕竟春天的到来，万物都开始生长，而在春天我们需要做两件事，一个是疏肝，另一个则轩辕故里甘肃清水深挖中医潜能打造全域生态康养胜地甘肃省天水市清水县境内的养心园农耕文化产业旅游专业合作社内，女工包装艾条。（资料图）杨兆康摄中新网兰州3月24日电（崔琳）走进甘肃省天水市清水县境内的养心园农耕文化产业旅游专业合作轩辕故里甘肃清水深挖中医潜能打造全域生态康养胜地甘肃省天水市清水县境内的养心园农耕文化产业旅游专业合作社内，女工包装艾条。（资料图）杨兆康摄走进甘肃省天水市清水县境内的养心园农耕文化产业旅游专业合作社，浓浓的草药香扑鼻而来。在该54岁烧烤摊主李先生突然中风，老中医叮嘱平时要多吃这6种食物说一下最近发生在我身边的一件事，小区楼下一个烧烤店的老板在做烤串时突然倒地，家人打120紧急送往医院，经过CT检查被确认为是中风，由于做烧烤长期熬夜，过度劳累，饮食也不规律，每天吃一季度全国GDP二十强城市预测广州第4，宁波领先天津，西安第19随着全国高质量发展的不断推进，各地的经济发展水平也在不断地提高，2023年一季度的GDP也即将公布。伴随着去年各城市经济发展的不断缓慢，今年一季度很多城市的GDP将迎来一个新的改变ChatGPT房价会下降吗？房价下降的前提条件是什么？房价下降的前提条件有很多，其中一些可能包括经济下滑如果经济处于衰退或不景气状态，人们的购买力会下降，房地产市场需求也会下降，从而可能导致房价下降。房屋供应蔡皇复刻出一个诺安成长？诺安积极回报年内收益率高达47记者杜萌曾经以重仓半导体一战成名的蔡嵩松正在复制诺安成长的业绩奇迹。Wind数据显示，蔡嵩松2022年8月20日接任的诺安积极回报，今年以来收益率高达47。14，在全市场的主动权益城市24小时人均GDP吊打京沪，四线小城凭什么每经记者刘艳美每经编辑杨欢图片来源鄂尔多斯融媒近日，鄂尔多斯市统计局发布信息称，2022年，鄂尔多斯人均地区生产总值突破25万元。2022年，鄂尔多斯市地区生产总值5613。44亿