数据结构动态数组，gif数据结构

点击上方“Java高级架构师”，选择右上角“热门公众号”

每日发布的前20 个高级架构主题

有关高级架构的高级主题

Mysql优化专题() 网络协议专题() 从公众号首页的菜单栏查看剩余的18个专题。如果您需要加入群组进行讨论或学习，只需在后台回复添加群组即可。 ps：由于之前的动画数据结构深受好评，所以这次是动画排序算法全集。数据结构和算法合二为一。

几个动态图阐明了常见的Java 数据结构及其设计原理。

本文用动态图解+文字解释+正确的Java代码实现的方式讲解了以下10种排序算法。

冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序0.排序算法讲解

0.1 排序定义

根据特定关键字对对象序列进行排序。

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. 冒泡排序

冒泡排序是一种简单的排序算法。迭代要排序的序列，一次比较两个元素，如果元素无序则交换元素。重复访问该阵列，直到不再需要交换为止。这意味着数组已排序。该算法的名称来源于这样一个事实：小元素通过交换慢慢“浮动”到数组的开头。

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]; } 返回数组；

最好情况：T(n)=O(n) 最坏情况：T(n)=O(n2) 平均情况：T(n)=O(n2)

2. 对选择进行排序

最稳定的排序算法之一。无论输入什么数据，时间复杂度都是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 的新无序区域。传递完成，数组有序。 2.2 GIF演示

2.3 代码实现

/** * 选择排序* @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]=array[i]=temp; }2.4 算法分析

最好情况：T(n)=O(n2) 最坏情况：T(n)=O(n2) 平均情况：T(n)=O(n2)

3.插入排序

插入排序算法描述是一种简单直观的排序算法。对于未排序的数据，从后向前扫描已排序的序列，找到对应的位置，然后插入。插入排序实现通常使用就地排序（即仅使用O(1) 额外空格的排序）。因此，在扫描过程中必须从后向前反复地逐渐移动。向后排序元素，为最新元素提供插入空间。

3.1 算法描述

插入排序通常使用就地在数组上实现。具体算法解释如下。

从第一个元素开始，元素被视为已排序。获取下一个元素，从排序后的元素序列的后到前进行扫描。如果元素（已排序）大于新元素，则将该元素移动到下一个元素。然后指定一个位置，重复步骤3，直到找到排序元素小于等于新元素的位置。重复步骤2-5。

1

2.更直观的视角

3.2 代码实现

/** * 插入排序* @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]) { array[preIndex + 1]=array[preIndex]; + 1]=当前； }3.4 算法分析

最好情况：T(n)=O(n) 最坏情况：T(n)=O(n2) 平均情况：T(n)=O(n2)

4.希尔排序

Hills排序是Donald Shell于1959年提出的一种排序算法。希尔排序也是一种插入排序，是简单插入排序的更高效版本，同时，该算法是最早突破O(n2) 的算法之一。这与插入排序的不同之处在于，首先比较最远的元素。希尔排序也称为递减增量排序。

希尔排序根据表中的特定增量对记录进行分组，并使用直接插入排序算法对每个组进行排序。随着增量逐渐减少，每组包含更多的关键词。整个文件被分为一组，算法结束。

4.1 算法描述

让我们看一下山排序的基本步骤。在这里，我们选择增量间隙=长度/2 并继续将增量减小间隙=间隙/2。该增量选择可以由序列{n/2.(n/2)/2.1}，称为增量序列。希尔排序增量序列的选择和证明是一个数学问题，我们选择的增量序列也是希尔推荐的增量序列。但实际上，这个增量序列并非如此。最优化的一个。我们将在这里使用山增量作为示例。

首先将整个待排序的记录序列分成若干子序列进行直接插入排序。我来解释一下具体的算法。

选择增量序列t1, t2, tk (titj, tk=1)。在每次排序过程中，根据相应的增量ti，对序列根据增量序列k进行k次排序。将待排序的分为若干个长度为m的子序列，对每个子列表进行直接插入排序。只有当增量因子为1时，整个序列才被视为一个表，表的长度就是整个序列的长度。 4.2.1 GIF 演示

4.2.2 工艺演示

4.3 代码实现

/** * 希尔斯排序* * @param array * @return */public static int[] ShellSort(int[] array) { int len=array.length, gap=len/0 ) { for (int i=间隙； i len; i++) { temp=int preIndex=i – 间隙while (preIndex=0 array[preIndex] temp) { array[preIndex + 间隙]=array[ preIndex];间隙； } 数组[preIndex + 间隙]=temp; 4.4 算法分析

最好情况：T(n)=O(nlog2 n) 最坏情况：T(n)=O(nlog2 n) 平均情况：T(n)=O(nlog2n)

5. 归并排序

与选择排序一样，合并排序的性能不受输入数据的影响，但合并排序的性能比选择排序好得多，因为时间复杂度始终为O(n log n) 。价格是额外内存容量的价格。

归并排序是一种基于归并操作的有效排序算法。该算法是分而治之的一个非常典型的应用。归并排序是一种稳定的排序方法。合并已排序的子序列以获得完全排序的序列。即先将每个子序列按顺序排列，然后再将子序列段按顺序排列。当两个有序列表合并为一个有序列表时，称为双向合并。

5.1 算法描述

将长度为n 的输入序列拆分为长度为n/2 的两个子序列，并对这两个子序列中的每一个使用归并排序，将两个已排序的子序列形成最终的排序序列。 5.2 GIF 演示

1

2

5.3 代码实现

/** * 归并排序* * @param array * @return */public static int[] MergeSort(int[] array) { if (array.length 2) return array; ] left=Arrays.copyOfRange(array, 0, int[] right=Arrays.copyOfRange(array, mid, array.length); return merge(MergeSort(left), MergeSort(right); * 合并排序—— 将两个已排序的数组合并为一种排序* * @param left * @param右* @return */public static int[] merge(int[] left, int[] right) { int[ ] result=new int[left.length + right.length]; for (intindex=0, i=0 , j=0;index 结果.length;index++) { if (i=left.length) result[index]=right[j++ ]; else if (j=right.length) result[index]=left[i++] else if (left[i] right[j]) result[index]=left[i++] } 4 算法分析

最好情况：T(n)=O(n) 最坏情况：T(n)=O(nlogn) 平均情况：T(n)=O(nlogn)

6. 快速排序

快速排序的基本思想是在一次排序中将正在排序的记录分成两个独立的部分。如果记录的一部分中的关键字小于另一部分中的关键字，则记录的两部分被分割。您可以单独对它们进行排序以实现整个顺序。

6.1 算法描述

快速排序使用分而治之的方法将字符串（列表）拆分为两个子字符串（子列表）。具体算法解释如下。

从序列中选择一个名为“pivot”的元素，并对序列进行重新排序，以便所有小于主值的元素都放置在主值之前，所有大于主值的元素都放置在主值之后。两边都可以）。在此分区的末尾，碱基位于序列的中间。这称为分区操作，它递归地对小于主值的元素子数组和大于主值的元素子数组进行排序。 6.2 GIF 演示

1 性格开朗

2 严重

6.3 代码实现

/** * 快速排序方法* @param array * @param start * @param end * @return */public static int[] QuickSort(int[] array, int start, int end) { if (array.length 1 | | start 0 || end=array.length start end) 返回null。 ) QuickSort(array,smallIndex + 1, end); } /** * 快速排序算法——partition * @param array * @param start * @param end * @return */public static int Partition(int[] array , int start , int end) { int hub=(int) (start + Math.random() * (end – start + 1)); for ( int i=start; i=end; i++) if ( array[i]=array[end]) {smallIndex++; if (ismallIndex) } returnsmallIndex;数组中的两个元素* @param array * @param i * @param j */public static void swap(int[ ] array , int i, int j) { int temp=array[j]; array[j]=temp;

最好情况：T(n)=O(nlogn) 最坏情况：T(n)=O(n2) 平均情况：T(n)=O(nlogn)

7. 堆排序

堆排序是指利用堆数据结构设计的排序算法。栈是一种近似完全二叉树的结构，满足栈的性质。也就是说，子节点的键值或索引总是小于（或大于）其父节点。

7.1 算法描述

将要排序的关键字的初始序列（R1，R2.Rn）构建到一个大的顶堆（第一个无序区域）中。此时，我们将第一个元素R[1] 与最后一个元素R[n] 交换。 time 得到一个新的无序区域(R1,R2,Rn-1)和一个新的有序区域(Rn)，满足R[1,2.n-1]=R[n]，因为Masu.堆开头的新R[1] 可能会违反堆属性，因此将当前无序区域(R1, R2,Rn-1) 调整到新堆，然后必须替换R。 [1] 再次使用无序区域的最后一个元素，得到新的无序区域（R1，R2.Rn-2）和新的有序区域（Rn-1，Rn）。重复这个过程，直到有序区域的元素个数为n-1，整个排序过程完成。 7.2 GIF 演示

1 幸福

2 严重

7.3 代码实现

注意：这里使用了完全二叉树的几个属性。

//声明一个全局变量来记录数组的长度/** * 堆排序算法* * @param array * @return */public static int[] HeapSort(int[] array) { len=array .length ; (len 1) 返回数组； //1. 构建最大堆。 buildMaxHeap(array); //2. 交换堆的第一位（最大值）和最后一位。调整最大堆while ( len 0) { swap(array, 0, len – 1);AdjustHeap(array, 0) } return array; /** * 构建最大堆* * @param array */public static void buildMaxHeap( int [] array) { //从最后一个非叶子节点向上构建最大堆for (int i=(len – 1)/2; i=0; i–) { AdjustHeap (array, i); /** * 调整最大堆* * @param array * @param i */public static voidAdjustHeap(int[] array, int i) { int maxIndex=i; //如果有左子树且左子树为大于父节点，将max指针指向左子树if (i * 2 len array[i * 2] array[maxIndex]) maxIndex=i * 2; //如果存在右子树且右子树为父节点，将max指针指向右子树if (i * 2 + 1 len array[i * 2 + 1] array[maxIndex]) maxIndex=i * 2 + 1; //如果父节点不是最大值，交换具有最大值的父节点，并递归调整与父节点的交换位置。 if (maxIndex !=i) { swap(array, maxIndex, i);AdjustHeap(array, maxIndex); 7.4 算法分析

最好情况：T(n)=O(nlogn) 最坏情况：T(n)=O(nlogn) 平均情况：T(n)=O(nlogn)

8. 计数排序

计数排序的核心是将输入数据值转换为键并将其存储在额外开辟的数组空间中。 计数排序是一种线性时间复杂度排序，要求输入数据是一定范围内的整数。

计数排序是一种稳定的排序算法。计数排序使用额外的数组C.其中第i 个元素是正在排序的数组A 中值等于i 的元素的数量。接下来，根据数组C将A的元素放置在正确的位置。只能对整数进行排序。

8.1 算法描述

找到待排序数组中最大和最小的元素，统计数组中每个值为i的元素出现的次数，存入数组C的第i项（从第一个元素开始）。 C 首先将每一项附加到前一项）；相反，填充目标数组。将每个元素i 放入新数组的第C(i) 项中，并为每个放置的元素从C(i) 中减去1。 GIF演示

8.3 代码实现

/** * 计算排序* * @param array * @return */public static int[] CountingSort(int[] array) { if (array.length==0) return array, min=array[0] , max=array[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[] 桶=new int[max – min + 1]; for (int i=0; i array.length; i++) [array[i] + 偏差]++; index=0, i=0; while (index array.length) { if (bucket[i] !=0) { array[index]=i – bucket; } else i++;

如果输入元素是从0 到k 的n 个整数，则执行时间为O(n + k)。计数排序不是比较排序，并且排序比任何比较排序算法都快。这使得计数将被排序。具有大数据范围和大内存的数组需要大量数据。

最好情况：T(n)=O(n+k) 最坏情况：T(n)=O(n+k) 平均情况：T(n)=O(n+k)

9. 桶排序

桶排序是计数排序的升级版本。效率的关键是利用函数映射关系。

映射函数的确定。
桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排
9.1 算法描述
人为设置一个BucketSize，作为每个桶所能放置多少个不同数值（例如当BucketSize==5时，该桶可以存放｛1,2,3,4,5｝这几种数字，但是容量不限，即可以存放100个3）；遍历输入数据，并且把数据一个一个放到对应的桶里去；对每个不是空的桶进行排序，可以使用其它排序方法，也可以递归使用桶排序；从不是空的桶里把排好序的数据拼接起来。注意，如果递归使用桶排序为各个桶排序，则当桶数量为1时要手动减小BucketSize增加下一循环桶的数量，否则会陷入死循环，导致内存溢出。
9.2 图片演示
9.3 代码实现
/** * 桶排序 * * @param array * @param bucketSize * @return */ public static ArrayList BucketSort(ArrayList 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> bucketArr = new ArrayList<>(bucketCount); ArrayList resultArr = new ArrayList<>(); for (int i = 0; i < bucketCount; i++) { bucketArr.add(new ArrayList()); } 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 (bucketCount == 1) bucketSize–; ArrayList 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.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, p = 1; ArrayList> bucketList = new ArrayList>(); for (int i = 0; i < 10; i++) bucketList.add(new ArrayList()); for (int i = 0; i < maxDigit; i++, mod *= 10, p *= 10) { for (int j = 0; j < array.length; j++) { int num = (array[j] % mod) / p; 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; }10.4 算法分析
最佳情况：T(n) = O(n * k) 最差情况：T(n) = O(n * k) 平均情况：T(n) = O(n * k)
基数排序有两种方法：
MSD 从高位开始进行排序 LSD 从低位开始进行排序
基数排序 vs 计数排序 vs 桶排序
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
基数排序：根据键值的每位数字来分配桶计数排序：每个桶只存储单一键值桶排序：每个桶存储一定范围的数值总结
各种排序的稳定性，时间复杂度、空间复杂度、稳定性总结如下图：
关于时间复杂度：
(1)平方阶(O(n2))排序
各类简单排序：直接插入、直接选择和冒泡排序；
(2)线性对数阶(O(nlog2n))排序
快速排序、堆排序和归并排序；
(3)O(n1+§))排序，§是介于0和1之间的常数。
希尔排序
(4)线性阶(O(n))排序
基数排序，此外还有桶、箱排序。
关于稳定性：
稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序
不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序
本文根据以下两篇文章整理而来：
郭耀华\’s Blog：http://www.cnblogs.com/guoyaohua/p/8600214.html
以及：
www.cricode.com/3212.html
看到这里，说明你喜欢本文
你的转发，是对我最大的鼓励！点赞支持↓↓↓