Java数据结构的十大排序 Java数据结构的十大排序

1.直接插入排序

1.1动图演示
1.2插入排序的思路
1.3代码实现
1.4性能分析

2.希尔排序

2.1原理
2.2动图演示
2.3代码实现
2.4性能分析

3.直接选择排序

3.1动图演示
3.2代码实现
3.3性能分析

4.堆排序

4.1动图演示
4.2代码实现
4.3性能分析

5.冒泡排序

5.1动图演示
5.2代码实现
5.3性能分析

6.快速排序

6.1原理
6.2动图演示
6.3实现方法

6.3.1Hoare法
6.3.2挖坑法

6.4代码实现

6.5快排优化

6.5.1三数取中法
6.5.2加上直接插入排序

6.6非递归的实现

6.6.1非递归思路
6.6.2非递归代码实现

6.7性能分析

7.归并排序

7.1原理

7.2动图演示

7.3代码实现—递归

7.4代码实现—非递归

7.5性能分析

8.计数排序

8.1算法的步骤

8.2动图演示

8.3代码实现

8.4性能分析

9.桶排序

9.1原理

9.2算法的步骤

9.3画图解析

9.4代码实现

9.5性能分析

10.基数排序

10.1算法的步骤

10.2动图演示

10.3代码实现

10.4性能分析

文章图片

1.直接插入排序
1.1 动图演示

文章图片

1.2 插入排序的思路

从第一个元素开始,这里我们第一个元素是已排序的.
取下一个元素,和有序序列的元素从后往前比较.( 有序区间 : [0,i) )
如果得到的有序序列的元素比该元素大则将取得的有序元素往后放
重复3操作,直到得到的有序元素比该元素小, 或者有序元素比完了.记录这个位置
然后将该元素放入到这个位置.
遍历数组,重复2~5的操作.

1.3 代码实现

/*** 时间复杂度:*最好的情况: O(n)*最坏的情况: O(n^2)* 空间复杂度: O(1)* @param array*/public static void insertSort(int[] array) {for (int i = 1; i < array.length; i++) {int j = i - 1; int tmp = array[i]; while (j >= 0) {if (array[j] > tmp) {array[j + 1] = array[j]; j--; }else {break; }}array[j + 1] = tmp; }}

1.4 性能分析

时间复杂度(平均)	时间复杂度(最坏)	时间复杂度(最好)	空间复杂度	稳定性
O(n^2)	O(n^2)	O(n)	O(1)	稳定

插入排序，初始数据越接近有序，时间效率越高。

2.希尔排序
2.1 原理
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数gap，把待排序文件中所有记录分成个gap组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后，取gap = (gap/3)+1，重复上述分组和排序的工作。当到达gap=1时，所有记录在统一组内排好序。

希尔排序是对直接插入排序的优化。
当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

文章图片

2.2 动图演示

2.3 代码实现

/**** @param array 排序的数组* @param gap 每组的间隔 -> 数组*/public static void shell(int[] array,int gap){for (int i = gap; i < array.length ; i++) {int tmp = array[i]; int j = i - gap; while(j>=0){if(array[j] > tmp){array[j + gap] = array[j]; j -= gap; }else {break; }}array[j + gap] = tmp; }}public static void shellSort(int[] array){int gap = array.length; while (gap > 1){gap = (gap / 3) + 1; // +1 保证最后一个序列是 1 (除几都行)shell(array,gap); }}

2.4 性能分析

时间复杂度(平均)	时间复杂度(最坏)	时间复杂度(最好)	空间复杂度	稳定性
O(n^1.3)	O(n^2)	O(n)	O(1)	不稳定

3.直接选择排序
3.1 动图演示

文章图片

3.2 代码实现

/*** 时间复杂度:*最好: O(n^2)*最坏: O(n^2)* 空间复杂度: O(1)* 稳定性: 不稳定* @param array*/public static void selectSort(int[] array){for (int i = 0; i < array.length - 1; i++) {for (int j = i + 1; j
3.3 性能分析

时间复杂度(平均) 时间复杂度(最坏) 时间复杂度(最好) 空间复杂度稳定性

O(n^2) O(n^2) O(n^2) O(1) 不稳定

4.堆排序
4.1 动图演示

4.2 代码实现

public static void siftDown(int[] array,int root, int len){int parent = root; int child = root * 2 + 1; while (child < len){if( child+1 < len && array[child] < array[child+1] ){child++; }//这里child下标就是左右孩子的最大值的下标if(array[child] > array[parent]){int tmp = array[child]; array[child] = array[parent]; array[parent] = tmp; parent = child; child = parent * 2 + 1; }else {break; }}}public static void createHeap(int[] array){for (int i = (array.length - 1 - 1) / 2; i >= 0; i++) {siftDown(array,i,array.length); }}public static void heapSort(int[] array){createHeap(array); int end = array.length - 1; while (end > 0){int tmp = array[end]; array[end] = array[0]; array[0] =tmp; siftDown(array,0,end); end--; }}

4.3 性能分析

时间复杂度(平均) 时间复杂度(最坏) 时间复杂度(最好) 空间复杂度稳定性

O(n * log(n)) O(n * log(n)) O(n * log(n)) O(1) 不稳定

5.冒泡排序
5.1 动图演示

文章图片

5.2 代码实现

public static void BubbleSort(int[] array){for (int i = 0; i < array.length - 1; i++) {boolean flg = false; for (int j = 0; j < array.length - 1 - i ; j++) {if(array[j+1] < array[j]){int tmp = array[j]; array[j] = array[j+1]; array[j+1] = tmp; flg = true; }}if(!flg){break; }}}

5.3 性能分析

时间复杂度(平均) 时间复杂度(最坏) 时间复杂度(最好) 空间复杂度稳定性

O(n^2) O(n^2) O(n) O(1) 稳定

6.快速排序
6.1 原理

从待排序区间选择一个数，作为基准值(pivot)；

Partition: 遍历整个待排序区间，将比基准值小的（可以包含相等的）放到基准值的左边，将比基准值大的（可以包含相等的）放到基准值的右边；

采用分治思想，对左右两个小区间按照同样的方式处理，直到小区间的长度 == 1，代表已经有序，或者小区间的长度 == 0，代表没有数据。

6.2 动图演示

文章图片

6.3 实现方法

6.3.1 Hoare法
文章图片

6.3.2 挖坑法
文章图片

6.4 代码实现

//Hoare法public static void swap(int[] array,int i,int j){int tmp = array[i]; array[i] = array[j]; array[j] = tmp; }public static int partition1(int[] array,int low,int high) {int i = low; int tmp = array[low]; while (low < high){while (low < high && array[high] >= tmp){high--; }while (low < high && array[low] <= tmp){low++; }swap(array,low,high); }swap(array,i,low); return low; }//挖坑法public static int partition2(int[] array,int low,int high) {int tmp = array[low]; while (low < high){while (low < high && array[high] >= tmp){high--; }array[low] = array[high]; while (low < high && array[low] <= tmp){low++; }array[high] = array[low]; }array[low] = tmp; return low; }public static void quick(int[] array,int start,int end){if(start >= end) return; int pivot = partition1(array,start,end); quick(array,start,pivot-1); quick(array,pivot+1,end); }public static void quickSort(int[] array){quick(array,0,array.length-1); }

6.5 快排优化

6.5.1 三数取中法
public static void swap(int[] array,int i,int j){int tmp = array[i]; array[i] = array[j]; array[j] = tmp; }public static int partition2(int[] array,int low,int high) {int tmp = array[low]; while (low < high){while (low < high && array[high] >= tmp){high--; }array[low] = array[high]; while (low < high && array[low] <= tmp){low++; }array[high] = array[low]; }array[low] = tmp; return low; }public static void selectPivotMedianOFThree(int[] array,int start,int end,int mid){if(array[mid] > array[start]){swap(array,start,mid); }//此时mid下标的值肯定小于start下标的值 array[mid] <= array[start]if(array[mid] > array[end]){swap(array,mid,end); }//此时mid下标的值肯定小于end下标的值 array[mid] <= array[end]if(array[start] > array[end]){swap(array,start,end); }//此时有 array[mid] <= array[start] <= array[end]}public static void quick1(int[] array,int start,int end){if(start >= end) return; int mid = (start + end) / 2; selectPivotMedianOFThree(array,start,end,mid); int pivot = partition2(array,start,end); quick1(array,start,pivot-1); quick1(array,pivot+1,end); }public static void quick1Sort(int[] array){quick1(array,0,array.length - 1); }

【Java数据结构的十大排序】
6.5.2 加上直接插入排序
public static void swap(int[] array,int i,int j){int tmp = array[i]; array[i] = array[j]; array[j] = tmp; }public static void insertSort2(int[] array,int start,int end){for (int i = start + 1; i <= end; i++) {int j = i + 1; int tmp = array[i]; while (j >= 0){if(array[j] > tmp){array[j+1] = array[j]; }else {break; }}array[j+1] = tmp; }}public static int partition2(int[] array,int low,int high) {int tmp = array[low]; while (low < high){while (low < high && array[high] >= tmp){high--; }array[low] = array[high]; while (low < high && array[low] <= tmp){low++; }array[high] = array[low]; }array[low] = tmp; return low; }public static void selectPivotMedianOFThree(int[] array,int start,int end,int mid){if(array[mid] > array[start]){swap(array,start,mid); }//此时mid下标的值肯定小于start下标的值 array[mid] <= array[start]if(array[mid] > array[end]){swap(array,mid,end); }//此时mid下标的值肯定小于end下标的值 array[mid] <= array[end]if(array[start] > array[end]){swap(array,start,end); }//此时有 array[mid] <= array[start] <= array[end]}public static void quick2(int[] array,int start,int end){if(start >= end) return; if(end - start + 1 <= 100){insertSort2(array,start,end); return; }int mid = (start + end)/2; selectPivotMedianOFThree(array,start,end,mid); int pivot = partition2(array,start,end); quick2(array,start,pivot-1); quick2(array,pivot+1,end); }public static void quick2Sort(int[] array){quick2(array,0,array.length - 1); }

6.6 非递归的实现

6.6.1 非递归思路

首先调用partition,找到pivot

然后把pivot的左区间和右区间的下标放到栈立马

判断栈是否为空,不为空,弹出栈顶的2个元素(注意:入栈的顺序决定了出栈的顺序中的第一个元素是high的还是low的)

然后再进行调用partition,找pivot,

重复以上操作.

6.6.2 非递归代码实现
public static void quickSort4(int[] array){Stack stack = new Stack<>(); int low = 0; int high = array.length - 1; int pivot = partition2(array,low ,high); //左边有2个元素即以上if(pivot > low + 1){stack.push(0); stack.push(pivot - 1); }//右边有2个元素即以上if(pivot < high - 1){stack.push(pivot + 1); stack.push(high); }while (!stack.isEmpty()){high = stack.pop(); low = stack.pop(); pivot = partition2(array,low,high); //左边有2个元素即以上if(pivot > low + 1){stack.push(0); stack.push(pivot - 1); }//右边有2个元素即以上if(pivot < high - 1){stack.push(pivot + 1); stack.push(high); }}}

6.7 性能分析

时间复杂度(平均) 时间复杂度(最坏) 时间复杂度(最好) 空间复杂度稳定性

O(n * log(n)) O(n^2) O(n * log(n)) O(log(n))~O(n) 不稳定

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

文章图片

文章图片

7.2 动图演示

文章图片

7.3 代码实现—递归

public static void merge(int[] array,int low ,int high ,int mid){int s1 = low; int e1 = mid; int s2 = mid+1; int e2 = high; int[] tmp = new int[high - low + 1]; int k = 0; while (s1 <= e1 && s2 <= e2){if(array[s1] <= array[s2]){tmp[k++] = array[s1++]; }else {tmp[k++] = array[s2++]; }}while (s1 <= e1){tmp[k++] = array[s1++]; }while (s2 <= e2){tmp[k++] = array[s2++]; }for (int i = 0; i < tmp.length; i++) {array[i+low] = tmp[i]; }}public static void mergeSortInternal(int[] array,int low ,int high){if(low >= high) return; int mid = (low + high) / 2; mergeSortInternal(array,low,mid); mergeSortInternal(array,mid+1,high); merge(array,low,high,mid); }public static void mergeSort(int[] array){mergeSortInternal(array,0,array.length - 1); }

7.4 代码实现—非递归

public static void merge1(int[] array,int gap){int[] tmp = new int[array.length]; int k = 0; int s1 = 0; int e1 = s1 + gap - 1; int s2 = e1 + 1; int e2 = s2 + gap - 1 > array.length ? array.length - 1 : s2 + gap - 1; while (s2 < array.length){while (s1 <= e1 && s2 <= e2){if(array[s1] <= array[s2]){tmp[k++] = array[s1++]; }else {tmp[k++] = array[s2++]; }}while (s1 <= e1){tmp[k++] = array[s1++]; }while (s2 <= e2){tmp[k++] = array[s2++]; }s1 = e2 + 1; e1 = s1 + gap - 1; s2 = e1 + 1; e2 = s2 + gap - 1 > array.length ? array.length - 1 : s2 + gap - 1; }while (s1 <= array.length - 1){tmp[k++] = array[s1++]; }for (int i = 0; i < tmp.length; i++) {array[i] = tmp[i]; }}public static void mergeSort1(int[] array){for (int i = 1; i < array.length; i*=2) {merge1(array,i); }}

7.5 性能分析

时间复杂度(平均) 时间复杂度(最坏) 时间复杂度(最好) 空间复杂度稳定性

O(n * log(n)) O(n * log(n)) O(n * log(n)) O(n) 稳定

8.计数排序当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。

8.1 算法的步骤
（1）找出待排序的数组中最大和最小的元素
（2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项
（3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
（4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

8.2 动图演示

文章图片

8.3 代码实现

public static void CountingSort(int[] array){int maxValue = https://www.it610.com/article/GetMaxValue(array); int bucketLen = maxValue + 1; int[] bucket = new int[bucketLen]; for (int value:array) {bucket[value]++; }int index = 0 ; for (int i = 0; i < bucketLen; i++) {while(bucket[i]> 0){array[index++] = i; bucket[i]--; }}}public static int GetMaxValue(int[] array){int maxValue = https://www.it610.com/article/array[0]; for (int i = 0; i < array.length; i++) {if(maxValue < array[i]){maxValue = array[i]; }}return maxValue; }

8.4 性能分析

时间复杂度(平均) 时间复杂度(最坏) 时间复杂度(最好) 空间复杂度稳定性

O(n+k) O(n+k) O(n+k) O(k) 稳定

9.桶排序
9.1 原理
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
为了使桶排序更加高效，我们需要做到这两点：

在额外空间充足的情况下，尽量增大桶的数量

使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

9.2 算法的步骤

设置一个定量的数组当作空桶；

遍历输入数据，并且把数据一个一个放到对应的桶里去；

对每个不是空的桶进行排序；

从不是空的桶里把排好序的数据拼接起来。

9.3 画图解析

文章图片

9.4 代码实现

public static void bucketSort(int[] arr) {if (arr.length == 0) {return; }int minValue = https://www.it610.com/article/arr[0]; int maxValue = arr[0]; for (int value : arr) {if (value < minValue) {minValue = value; } else if (value> maxValue) {maxValue = https://www.it610.com/article/value; }}//得到最大和最小元素int bucketNum = (maxValue - minValue) / arr.length + 1; //桶的数量ArrayList> bucket = new ArrayList<>(bucketNum); for (int i = 0; i < bucketNum; i++) {bucket.add(new ArrayList<>()); }//将元素放入到桶中for (int i = 0; i < arr.length; i++) {int num = (arr[i] - minValue) / arr.length; bucket.get(num).add(arr[i]); }for (int i = 0; i < bucket.size(); i++) {//这里是比较,可以选择其他的方式实现,这里为了演示采取Collection的sortCollections.sort(bucket.get(i)); }// 将桶中的元素赋值到原序列int index = 0; for(int i = 0; i < bucket.size(); i++){for(int j = 0; j < bucket.get(i).size(); j++){arr[index++] = bucket.get(i).get(j); }}}

9.5 性能分析

时间复杂度(平均) 时间复杂度(最坏) 时间复杂度(最好) 空间复杂度稳定性

O(n+k) O(n^2) O(n+k) O(n+k) 稳定

10.基数排序
10.1 算法的步骤

取得数组中的最大数，并取得位数；

arr为原始数组，从最低位开始取每个位组成radix数组；

对radix进行计数排序（利用计数排序适用于小范围数的特点）

10.2 动图演示

文章图片

10.3 代码实现

public static int getNumLength(int num){if(num == 0) return 1; int count = 0; for (int i = num; i != 0; i /= 10) {count++; }return count; }public static void RadixSort(int[] array){int maxValue = https://www.it610.com/article/array[0]; for (int i = 0; i < array.length; i++) {if(maxValue < array[i]){maxValue = array[i]; }}int maxDigit = getNumLength(maxValue); int mod = 10; int dev = 1; for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {int[][] counter = new int[mod * 2][0]; for (int j = 0; j < array.length; j++) {int bucket = ((array[j] % mod) / dev) + mod; counter[bucket] = arrayAppend(counter[bucket], array[j]); }int pos = 0; for (int[] bucket : counter) {for (int value : bucket) {array[pos++] = value; }}}}public static int[] arrayAppend(int[] arr, int value) {arr = Arrays.copyOf(arr, arr.length + 1); arr[arr.length - 1] = value; return arr; }

10.4 性能分析

时间复杂度(平均) 时间复杂度(最坏) 时间复杂度(最好) 空间复杂度稳定性

O(n*k) O(n*2) O(n*k) O(n+k) 稳定

总结：

文章图片

到此这篇关于 Java数据结构的十大排序的文章就介绍到这了,更多相关 Java数据结构十大排序内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家！

推荐阅读

椰子油的生活小妙用椰子油有什么用途和功效

庆东锅炉故障代码是什么如何解决

教学教务管理人员是干什么的

联想yoga2

如何选择抗体稀释液？抗体稀释液

下载导航地图，导航地图下载

流媒体后视镜可以当行车记录仪吗行车记录仪有必要买流媒体吗

炒苔菜用不用焯水，苔菜用不用焯水再炒

昆明工业职业技术学院怎么样

（152）感赏女儿|（152）感赏女儿 2020-12-4

桃子核发霉外面是好的还能吃吗

离散傅立叶分析,origin怎么进行傅立叶分析

次密接触者的一般接触者需要隔离吗

海带炖土豆的做法海带炖土豆的做法窍门

大概的近义词大概的近义词是什么标准答案

合金筷子是塑料还是金属合金筷子是什么材质

真我与假我

钢材包括哪些钢材怎么分类

heos,黑色素瘤

【家事】节如流水

SpringBoot|SpringBoot +DynamicDataSource切换多数据源的全过程

Spring事务失效的一种原因关于this调用的问题

VUE中鼠标滚轮使div左右滚动的方法详解

java|大厂员工被裁后的不同反应，也太真实了吧（|漫画）

人工智能|那些离开大厂，回归学术界的科学家们！

资讯|Snowflake8亿美元收购Streamlit，联手构建基于数据的应用程序

Java-泛型

前端|超火的炫酷告白源码(HTML+CSS)，前端表白源码，520表白，七夕情人节专属源码--文字开场白+相册旋转+浪漫3D樱花樱花雨

前端|JavaScript基础大总结

前端|一个简单炫酷的前端小项目（html+css+js）----3D图片演示