十大经典排序算法总结
根据某个关键字对对象序列进行排序。
0.2 术语解释
稳定：如果a本来在b前面，且a=b，则排序后a仍然在b前面；不稳定：如果a本来在b前面，且a=b，则排序后a可能会出现在b后面；内部排序：所有排序操作都在内存中完成；外部排序：由于数据太大，所以将数据放在磁盘上，只能通过磁盘和内存之间的数据传输来进行排序；时间复杂度：执行一个算法需要多少时间。空间复杂度：运行程序所需的内存量。 0.3 算法总结
图片名词解释：
n: 数据规模k: “桶”数量In-place: 占用恒定内存，无需额外内存Out-place: 占用额外内存0.5 算法分类
0.6 比较与非比较的区别
常见的快速排序、归并排序、堆排序、冒泡排序等都属于比较排序。在排序的最终结果中，元素之间的顺序取决于它们之间的比较。每个数字必须与其他数字进行比较以确定其位置。在冒泡排序等排序中，问题大小为n，由于需要进行n次比较，因此平均时间复杂度为O(n)。在归并排序、快速排序等排序中，通过分而治之的方法将问题规模缩小到logN倍，因此平均时间复杂度为O(nlogn)。比较排序的优点是适用于各种规模的数据，并且无论数据的分布如何都可以进行排序。可以说，比较排序适用于所有需要排序的情况。
计数排序、基数排序和桶排序都是非比较排序。非比较排序通过确定每个元素前面应有多少元素进行排序。对于数组arr，计算arr[i]之前有多少个元素，那么arr[i]在排序数组中的位置就唯一确定了。非比较排序只需判断每个元素之前存在的元素个数，一次遍历即可全部解决。算法时间复杂度为O(n)。非比较排序的时间复杂度最低，但确定唯一位置会占用空间。因此，对数据规模和数据分布有一定的要求。
1、冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法。它反复遍历要排序的序列，一次比较两个元素，如果顺序错误则交换它们。重复访问数组的工作，直到不需要再进行交换，这意味着数组已经排序完毕。这个算法的名字来源于这样一个事实：较小的元素会通过交换慢慢“浮动”到数组的顶部。
1.1 算法描述
比较相邻元素。如果第一个大于第二个，则交换它们；对每对相邻元素做同样的操作，从第一对开始到最后一对结束，这样最后的元素应该是最大的数字；对除最后一个元素之外的所有元素重复上述步骤；重复步骤1至3，直至排序完成。 1.2 GIF演示
1.3 代码演示
/** * 冒泡排序* * @param array * @return */public static int[] bubbleSort(int[] array) { if (array.length==0) return array; for (int i=0; i array.length; i++) for (int j=0; j array.length - 1 - i; j++) if (array[j + 1] array[j]) { int temp=array [j+1]；数组[ j + 1]=数组[j];数组[j]=温度；返回数组； }1.4 算法分析
最好情况：T(n)=O(n) 最坏情况：T(n)=O(n2) 平均情况：T(n)=O(n2)
2、选择排序（Selection Sort）
最稳定的排序算法之一，因为无论输入什么数据，时间复杂度都是O(n2)，所以使用时数据量越小越好。唯一的优点可能就是不占用额外的内存空间。从理论上讲，选择排序也可能是大多数人在排序时想到的最常见的排序方法。
选择排序是一种简单直观的排序算法。工作原理：首先，找到未排序序列中最小（大）的元素，并将其存储在已排序序列的起始位置。然后，继续从剩余的未排序元素中找到最小（大）的元素，然后将其放入已排序的序列中。的结束。依此类推，直到所有元素都排序完毕。
2.1 算法描述
对n条记录进行直接选择排序，经过n-1次直接选择排序即可得到有序结果。具体算法描述如下：
初始状态：无序区为R[1.n]，有序区为空；在第i 次排序开始时（i=1,2,3.n-1），当前有序区域和无序区域分别为R[1.i-1] 和R(i.n)。该排序操作从当前无序区域中选择键最小的记录R[k]，并将其与无序区域中的第一条记录R交换，使得R[1.i]和R[i+1. n) 分别成为记录数增加1的新的有序区域和记录数减少1的新的无序区域； n-1 遍完成并且数组已排序。 2.2 GIF演示
/** * 选择排序* @param array * @return */public static int[] SelectionSort(int[] array) { if (array.length==0) return array; for (int i=0; i array.length; i++) { int minIndex=i; for (int j=i; j array.length; j++) { if (array[j] array[minIndex]) //找到最小的数minIndex=j; //改变最小的数，保存该数的索引} int temp=array[minIndex];数组[minIndex]=数组[i];数组[i]=温度；返回数组； }2.4 算法分析
最好情况：T(n)=O(n2) 最坏情况：T(n)=O(n2) 平均情况：T(n)=O(n2)
3、插入排序（Insertion Sort）
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它通过构建有序序列来工作。对于未排序的数据，它会在已排序的序列中从后向前扫描，找到对应的位置并插入。在插入排序的实现中，通常使用就地排序（即只使用O(1)额外空间的排序）。因此，在从后向前扫描的过程中，需要反复地、逐渐地将排序后的元素向后移动。为最新元素提供插入空间。
3.1 算法描述
一般来说，插入排序是使用原地在数组上实现的。具体算法描述如下：
从第一个元素开始，可以认为该元素已经排序；取出下一个元素，在排序后的元素序列中从后向前扫描；如果元素（已排序）大于新元素，则将该元素移动到下一个位置；重复步骤3，直到找到排序元素小于等于新元素的位置；将新元素插入到该位置；重复步骤2~5。 3.2 动画演示
1.3 代码演示
/** * 插入排序* @param array * @return */public static int[] insertSort(int[] array) { if (array.length==0) return array;整数电流； for (int i=0; i array.length - 1; i++) { current=array[i + 1]; int preIndex=i; while (preIndex=0 当前数组[preIndex]) { 数组[preIndex + 1]=数组[preIndex];预索引- -; } 数组[preIndex + 1]=当前；返回数组； }3.4 算法分析
最好情况：T(n)=O(n) 最坏情况：T(n)=O(n2) 平均情况：T(n)=O(n2)
4、希尔排序（Shell Sort）
希尔排序是Donald Shell于1959年提出的一种排序算法。希尔排序也是一种插入排序。它是简单插入排序的更高效版本，也称为收缩增量排序。同时，该算法也是最早突破O(n2)的算法之一。它与插入排序的不同之处在于它首先比较较远的元素。希尔排序也称为减少增量排序。
希尔排序是将表中的记录按照一定的增量进行分组，并使用直接插入排序算法对每个组进行排序；随着增量逐渐减小，每组包含的关键词越来越多。当增量减至1 时，整个文件被分为一组，算法终止。
4.1 算法描述
我们来看看希尔排序的基本步骤。这里我们选择增量gap=length/2，并以gap=gap/2的方式继续减少增量。我们可以用一个序列来表示这种增量选择，{n/2,(n/2)/2.1}，称为增量序列。希尔排序增量序列的选择和证明是一个数学问题。我们选择的增量序列是比较常用的，也是Hill推荐的增量。这称为希尔增量。但事实上，这种增量序列并不是最优的。出色的。这里我们以Hill 增量为例。
首先将整个待排序的记录序列分成若干子序列进行直接插入排序。具体算法描述：
选择增量序列t1,t2,tk，其中titj,tk=1；根据增量序列数k对序列进行k次排序；在每一次排序过程中，根据对应的增量ti，将待排序的序列分成若干个长度为m的子序列，对每个子表进行直接插入排序。只有当增量因子为1时，整个序列才被当作一个表来处理，表的长度就是整个序列的长度。 4.2 工艺演示
1.3 代码实现
/** * 希尔排序* * @param array * @return */public static int[] ShellSort(int[] array) { int len=array.length; int temp, 间隙=len/2; while (间隙0 ) { for (int i=间隙； i len; i++) { temp=array[i]; int preIndex=i - 间隙； while (preIndex=0 array[preIndex] temp) { array[preIndex + 间隙]=array[ preIndex]; preIndex -=间隙； } 数组[preIndex + 间隙]=temp; } 间隙/=2;返回数组； }4.4 算法分析
最好情况：T(n)=O(nlog2 n) 最坏情况：T(n)=O(nlog2 n) 平均情况：T(n)=O(nlog2n)
5、归并排序（Merge Sort）
与选择排序一样，合并排序的性能不受输入数据的影响，但性能比选择排序好得多，因为时间复杂度始终为O(n log n)。代价是额外的内存空间。
归并排序是一种基于归并操作的有效排序算法。该算法是分而治之法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已经有序的子序列合并，得到完全有序的序列；即先对每个子序列进行排序，然后对子序列段进行排序。如果两个有序列表合并为一个有序列表，则称为2 路合并。
5.1 算法描述
将长度为n的输入序列分为两个长度为n/2的子序列；分别对两个子序列进行归并排序；将两个已排序的子序列合并为最终的排序序列。 5.2 GIF演示
5.3 代码演示
/** * 合并排序* * @param array * @return */public static int[] MergeSort(int[] array) { if (array.length 2) return array; int mid=array.length/2; int[ ] left=Arrays.copyOfRange(array, 0, mid); int[] right=Arrays.copyOfRange(array, mid, array.length);返回合并（合并排序（左），合并排序（右））； } /** * 合并排序—— 将两个已排序数组合并为一个已排序数组* * @param left * @param right * @return */public static int[] merge(int[] left, int[] right) { int[ ] 结果=new int[left.length + right.length]; for (int index=0, i=0, j=0; 索引result.length; index++) { if (i=left.length) result[index]=right[j++]; } else if (j=right.length) result[index]=left[i++]; else if (左[i] 右[j]) 结果[索引]=右[j++];否则结果[索引]=左[i++];返回结果； }5. 4 算法分析
最好情况：T(n)=O(n) 最坏情况：T(n)=O(nlogn) 平均情况：T(n)=O(nlogn)
6、快速排序（Quick Sort）
快速排序的基本思想是通过一次排序将待排序的记录分成两个独立的部分。如果一部分记录的关键字小于另一部分记录的关键字，则可以将两部分记录分开排序。实现整个序列的排序。
6.1 算法描述
快速排序使用分而治之的方法将列表分为两个子列表。具体算法描述如下：
从数组中选取一个元素，称为“枢轴”；对数组进行重新排序，使得所有小于主元值的元素都放在主元的前面，所有大于主元值的元素都放在主元的后面（相同的数字可以到任一侧）。该分区退出后，碱基位于序列的中间。这称为分区操作；它递归地对小于主元值的元素子数组和大于主元值的元素子数组进行排序。 5.2 GIF演示
6.3 代码演示
/** * 快速排序方法* @param array * @param start * @param end * @return */public static int[] QuickSort(int[] array, int start, int end) { if (array.length 1 | 1) | 开始0 || 结束=array.length || 开始结束) 返回null; int SmallIndex=分区(数组， 开始， 结束); if (smallIndex start) QuickSort(数组， start,smallIndex - 1); if (smallIndex end ) QuickSort(数组，smallIndex + 1, end);返回数组； } /** * 快速排序算法——partition * @param array * @param start * @param end * @return */public static int partition(int[] array , int start, int end) { int hub=(int) (开始+ Math.random() * (结束- 开始+ 1)); int 小索引=开始- 1;交换（数组，枢轴，结束）； for ( int i=start; i=end; i++) if (array[i]=array[end]) {smallIndex++;如果（我小索引）交换（数组，我，小索引）；返回小索引； } /** * 交换数组中的两个元素* @param array * @param i * @param j */public static void swap(int[] array, int i, int j) { int temp=array[i];数组[i]=数组[j]；数组[j]=温度； }6.4 算法分析
最好情况：T(n)=O(nlogn) 最坏情况：T(n)=O(n2) 平均情况：T(n)=O(nlogn)
7、堆排序（Heap Sort）
堆排序是指利用堆的数据结构设计的排序算法。堆叠是一种近似完全二叉树的结构，满足堆叠的性质：即子节点的键值或索引总是小于（或大于）其父节点。
7.1 算法描述
将待排序关键字的初始序列（R1,R2.Rn）构造成一个大顶堆，即初始无序区；将最上面的元素R[1]与最后一个元素R[n]交换，此时得到一个新的无序区域(R1,R2,…Rn-1)和一个新的有序区域(Rn)，并满足R [1,2.n-1]=R[n]；由于堆顶新增的R[1]可能违反堆的属性，因此需要将当前无序区（R1,R2,Rn-1）调整为新的堆，并且然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2.Rn-2)和新的有序区(Rn-1,Rn)。重复这个过程，直到有序区域的元素个数为n-1，则整个排序过程完成。 7.2 GIF演示
7.3 代码实现
最好情况：T(n)=O(nlogn) 最坏情况：T(n)=O(nlogn) 平均情况：T(n)=O(nlogn)
8、计数排序（Counting Sort）
计数排序的核心是将输入的数据值转换为键并存储在额外开辟的数组空间中。计数排序作为一种线性时间复杂度排序，要求输入数据必须是一定范围内的整数。
计数排序是一种稳定的排序算法。计数排序使用额外的数组C，其中第i个元素是要排序的数组A中值等于i的元素的个数。然后根据数组C将A中的元素排列到正确的位置。它只能对整数进行排序。
8.1 算法描述
找到待排序数组中最大和最小的元素；统计数组中每个值为i的元素出现的次数，并将其存储在数组C的第i项中；累加所有计数（从C 中的第一个元素开始，将每个项目添加到前一个项目）；反向填充目标数组：将每个元素i 放置在新数组的第C(i) 项中，并为每个放置的元素从C(i) 中减去1。 8.2 GIF演示
8.3 代码演示
/** * 计数排序* * @param array * @return */public static int[] CountingSort(int[] array) { if (array.length==0) return array; int 偏差，最小值=数组[0]，最大值=数组[0]； for (int i=1; i array.length; i++) { if (array[i] max) max=array[i]; } if (array[i] min) min=array[i]; } 偏差=0 - 分钟； int[] Bucket=new int[max - min + 1]; Arrays.fill(桶， 0); for (int i=0; i array.length; i++) { 桶[array[i] + 偏差]++; } int 索引=0, i=0; while (index array.length) { if (bucket[i] !=0) { array[index]=i - 偏差；桶[i]——；索引++；否则我++；返回数组； }8.
4 算法分析 当输入的元素是n 个0到k之间的整数时，它的运行时间是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。 最佳情况：T(n) = O(n+k) 最差情况：T(n) = O(n+k) 平均情况：T(n) = O(n+k)9、桶排序（Bucket Sort）
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。 桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排 9.1 算法描述 人为设置一个BucketSize，作为每个桶所能放置多少个不同数值（例如当BucketSize==5时，该桶可以存放｛1,2,3,4,5｝这几种数字，但是容量不限，即可以存放100个3）；遍历输入数据，并且把数据一个一个放到对应的桶里去；对每个不是空的桶进行排序，可以使用其它排序方法，也可以递归使用桶排序；从不是空的桶里把排好序的数据拼接起来。注意，如果递归使用桶排序为各个桶排序，则当桶数量为1时要手动减小BucketSize增加下一循环桶的数量，否则会陷入死循环，导致内存溢出。 9.2 图片演示 /** * 桶排序 * * @param array * @param bucketSize * @return */ public static ArrayList<Integer> BucketSort(ArrayList<Integer> array, int bucketSize) { if (array == null || array.size() < 2) return array; int max = array.get(0), min = array.get(0); // 找到最大值最小值 for (int i = 0; i < array.size(); i++) { if (array.get(i) > max) max = array.get(i); if (array.get(i) < min) min = array.get(i); } int bucketCount = (max - min) / bucketSize + 1; ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount); ArrayList<Integer> resultArr = new ArrayList<>(); for (int i = 0; i < bucketCount; i++) { bucketArr.add(new ArrayList<Integer>()); } for (int i = 0; i < array.size(); i++) { bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i)); } for (int i = 0; i < bucketCount; i++) { if (bucketSize == 1) { // 如果带排序数组中有重复数字时 感谢 @见风任然是风 朋友指出错误 for (int j = 0; j < bucketArr.get(i).size(); j++) resultArr.add(bucketArr.get(i).get(j)); } else { if (bucketCount == 1) bucketSize--; ArrayList<Integer> temp = BucketSort(bucketArr.get(i), bucketSize); for (int j = 0; j < temp.size(); j++) resultArr.add(temp.get(j)); } } return resultArr; }9.4 算法分析 桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。 最佳情况：T(n) = O(n+k) 最差情况：T(n) = O(n+k) 平均情况：T(n) = O(n2)10、基数排序（Radix Sort）
基数排序也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为O(kn),为数组长度，k为数组中的数的最大的位数； 基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。 10.1 算法描述 取得数组中的最大数，并取得位数；arr为原始数组，从最低位开始取每个位组成radix数组；对radix进行计数排序（利用计数排序适用于小范围数的特点）；10.2 动图演示 10.4 算法分析 最佳情况：T(n) = O(n * k) 最差情况：T(n) = O(n * k) 平均情况：T(n) = O(n * k) 基数排序有两种方法： MSD 从高位开始进行排序 LSD 从低位开始进行排序 10.3 代码演示 /** * 基数排序 * @param array * @return */ public static int[] RadixSort(int[] array) { if (array == null || array.length < 2) return array; // 1.先算出最大数的位数； int max = array[0]; for (int i = 1; i < array.length; i++) { max = Math.max(max, array[i]); } int maxDigit = 0; while (max != 0) { max /= 10; maxDigit++; } int mod = 10, div = 1; ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>(); for (int i = 0; i < 10; i++) bucketList.add(new ArrayList<Integer>()); for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) { for (int j = 0; j < array.length; j++) { int num = (array[j] % mod) / div; bucketList.get(num).add(array[j]); } int index = 0; for (int j = 0; j < bucketList.size(); j++) { for (int k = 0; k < bucketList.get(j).size(); k++) array[index++] = bucketList.get(j).get(k); bucketList.get(j).clear(); } } return array; }基数排序 vs 计数排序 vs 桶排序
用户评论
这个游戏集合了十大经典排序算法作为核心内容之一，让我对这些算法有了更深入的理解。
有10位网友表示赞同！
对于我来说，这个平台不仅展示了排序算法的魅力，还帮助我在项目中优化了代码执行速度。
有20位网友表示赞同！
在探索《十大经典排序算法总结》时，我发现其中的快速排序部分解释得非常清晰、易懂。
有13位网友表示赞同！
这款游戏帮助我一直保持对算法的热情，并在实践中尝试将这些知识应用到我的日常编程任务中。
有13位网友表示赞同！
我对游戏中的冒泡排序演示特别印象深刻，它以有趣的方式展现了一个简单却有效的排序过程。
有11位网友表示赞同！
《十大经典排序算法总结》的游戏设计使得复杂概念变得直观，我很容易就能掌握每一种算法的操作逻辑。
有9位网友表示赞同！
这款游戏不仅提供了理论知识，还让我有机会亲手操作排序算法解决问题，极大地提升了我的实践能力。
有10位网友表示赞同！
在玩的过程中，我逐渐发现了排序算法之间的连接性，并了解到它们在不同场景下的应用。
有15位网友表示赞同！
这款教育游戏以互动学习的方式呈现经典排序算法，使得我对每一个算法的细节有更深刻的印象。
有18位网友表示赞同！
通过《十大经典排序算法总结》游戏的学习体验，我在实际编程中能够更快地找到适当的排序方法解决问题。
有7位网友表示赞同！
这款游戏将枯燥的代码编写转换成了一场有趣的探索旅程，使我对学习顺序结构充满了动力。
有10位网友表示赞同！
在体验这个游戏中，我发现自己能更迅速地理解和记忆算法之间的差异和优点。
有11位网友表示赞同！
《十大经典排序算法总结》不仅涵盖了多种算法，还提供了实际应用案例，让我在虚拟环境中亲身体验其工作原理。
有8位网友表示赞同！
这款游戏通过丰富的视觉和声音效果，使得每一次学习都变得更有乐趣，同时加深了对排序算法的记忆。
有20位网友表示赞同！
从《十大经典排序算法总结》游戏中获得的知识帮助我在竞赛中提高了比赛成绩，并提升了我的逻辑思维能力。
有11位网友表示赞同！
这款游戏鼓励我跳出舒适区，尝试用不同的排序方法解决同样的问题，这对我在专业上的决策提供了很大帮助。
有5位网友表示赞同！
我在游戏过程中发现，理论与实践的结合是最佳的学习方式，《十大经典排序算法总结》让我真正掌握这些算法。
有7位网友表示赞同！
利用《十大经典排序算法总结》来加深对计算机科学原理的理解时，我发现自己的编程之旅变得更加充实和有趣。
有19位网友表示赞同！
该游戏不仅提高了我对于排序算法的记忆能力，还增强了我对大数据处理的能力和信心。
有12位网友表示赞同！
在探索各种排序算法的动态效果时，《十大经典排序算法总结》给我带来的体验是理论与实践完美结合的典范。
有20位网友表示赞同！