Java集合和数据结构排序实例详解-eolink官网

Java集合和数据结构排序实例详解

目录概念插入排序直接插入排序代码实现性能分析希尔排序代码实现性能分析选择排序直接选择排序代码实现性能分析堆排序代码实现性能分析交换排序冒泡排序代码实现性能分析快速排序代码实现性能分析非递归实现快速排序代码实现性能分析归并排序归并排序代码实现性能分析非递归实现归并排序代码实现性能分析海量数据的排序问题总结

概念

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

平时的上下文中，如果提到排序，通常指的是排升序（非降序）。

通常意义上的排序，都是指的原地排序(in place sort)。

稳定性：两个相等的数据，如果经过排序后，排序算法能保证其相对位置不发生变化，则我们称该算法是具备稳定性的排序算法。

插入排序

直接插入排序

整个区间被分为

有序区间

无序区间

每次选择无序区间的第一个元素，在有序区间内选择合适的位置插入

代码实现

逻辑代码：

public class InsertSort {

public static void insertSort(int[] array) {

for (int i = 1; i < array.length; i++) {

int temp = array[i];

int j = i-1;

for (; j >= 0; j--) {

if (array[j] > temp) {

array[j+1] = array[j];

}else {

break;

}

array[j+1] = temp;

}

调试代码：

public class TestDemo {

public static void main(String[] args) {

int[] array = {10,3,2,7,19,78,65,127};

System.out.println("排序前：" + Arrays.toString(array));

InsertSort.insertSort(array);

System.out.println("排序后：" + Arrays.toString(array));

}

该代码的执行结果为：

可见，实现了对原数组的升序排序。

性能分析

时间复杂度：

最好情况：O(n)【数据有序】

平均情况：O(n2)

最坏情况：O(n2)【数据逆序】

空间复杂度：O(1)

稳定性：稳定

对于直接插入排序：越有序越快。另外，直接插入排序会用在一些排序的优化上。

希尔排序

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

希尔排序是对直接插入排序的优化。

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

代码实现

逻辑代码：

public class ShellSort {

public static void shell(int[] array,int gap) {

for (int i = gap; i < array.length; i = i + gap) {

int temp = array[i];

int j = i-gap;

for (; j >= 0; j = j-gap) {

if (array[j] > temp) {

array[j+gap] = array[j];

}else {

break;

}

array[j+gap] = temp;

}

public static void shellSort(int[] array) {

int[] drr = {5,3,1};//增量数组-->没有明确的规定，但保证为素数的增量序列

for (int i = 0; i < drr.length; i++) {

shell(array,drr[i]);

}

测试代码：

public class TestDemo {

public static void main(String[] args) {

int[] array = {10,3,2,7,19,78,65,127};

System.out.println("排序前：" + Arrays.toString(array));

ShellSort.shellSort(array);

System.out.println("排序后：" + Arrays.toString(array));

}

该代码的执行结果为：

可见，实现了对原数组的升序排序。

性能分析

时间复杂度：

最好情况：O(n)【数据有序】

平均情况：O(n1.3)

最坏情况： O(n2) 【比较难构造】

空间复杂度：O(1)

稳定性：不稳定

选择排序

直接选择排序

每一次从无序区间选出最大（或最小）的一个元素，存放在无序区间的最后（或最前），直到全部待排序的数据元素排完。

代码实现

逻辑代码：

public class SelectSort {

public static void selectSort(int[]TVINaHQnM array) {

for (int i = 0; i < array.length-1; i++) {

for (int j = i+1; j < array.length; j++) {

if (array[i] > array[j]) {

int temp = array[j];

array[j] = array[i];

array[i] = temp;

}

测试代码：

public class TestDemo {

public static void main(String[] args) {

int[] array = {10,3,2,7,19,78,65,127};

System.out.println("排序前：" + Arrays.toString(array));

SelectSort.selectSort(array);

System.out.println("排序后：" + Arrays.toString(array));

}

该代码的执行结果为：

可见，实现了对原数组的升序排序。

性能分析

时间复杂度 : 不管是最好情况还是最坏情况都是O(n2) 【数据不敏感】

空间复杂度: O(1)

稳定性：不稳定

堆排序

基本原理也是选择排序，只是不在使用遍历的方式查找无序区间的最大的数，而是通过堆来选择无序区间的最大的数。

注意：排升序要建大堆；排降序要建小堆。

代码实现

逻辑代码：

public class HeapSort {

public static void heapSort(int[] array) {

PriorityQueue priorityQueue = new PriorityQueue<>(new Comparator() {

@Override

public int compare(Integer o1, Integer o2) {

return o1-o2;

}

});

for (int i = 0; i < array.length; i++) {

priorityQueue.add(array[i]);

}

for (int i = 0; i < array.length; i++) {

array[i] = priorityQueue.poll();

}

测试代码：

public class TestDemo {

public static void main(String[] args) {

int[] array = {10,3,2,7,19,78,65,127};

System.out.println("排序前：" + Arrays.toString(array));

HeapSort.heapSort(array);

System.out.println("排序后：" + Arrays.toString(array));

}

该代码的执行结果为：

可见，实现了对原数组的升序排序。

性能分析

时间复杂度：不管是最好的情况还是最坏的情况都是O(n * log(n)) 。

空间复杂度：O(1)。

稳定性：不稳定

交换排序

冒泡排序

在无序区间，通过相邻数的比较，将最大的数冒泡到无序区间的最后，持续这个过程，直到数组整体有序。

代码实现

逻辑代码：

public class BubbleBort {

public static void bubbleBort(int[] array) {

for (int i = 0; i < array.length-1; i++) {

for (int j = 0; j < array.length-i-1; j++) {

if (array[j] > array[j+1]) {

int temp = array[j];

array[j] = array[j+1];

array[j+1] = temp;

}

测试代码：

public class TestDemo {

public static void main(String[] args) {

int[] array = {10,3,2,7,19,78,65,127};

System.out.println("排序前：" + Arrays.toString(array));

BubbleBort.bubbleBort(array);

System.out.println("排序后：" + Arrays.toString(array));

}

该代码的执行结果为：

可见，实现了对原数组的升序排序。

性能分析

时间复杂度：

最好情况：O(n)【数据有序】

平均情况：O(n2)

最坏情况： O(n2) 【数据逆序】

空间复杂度：O(1)。

稳定性：稳定

快速排序

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

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

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

代码实现

逻辑代码：

public class QuickSort {

public static void quick(int[] array,int low,int high) {

if (low < high) {

int piv = piovt(array,low,high);//找基准

quick(array,low,piv-1);

quick(array,piv+1,high);

}

private static int piovt(int[] array,int start,int end) {

int temp = array[start];

while (start < end) {

while (start < end && array[end] >= temp) {

end--;

}

array[start] = array[end];

while (start < end && array[start] < temp) {

start++;

}

array[end] = array[start];

}

array[start] = temp;

return start;

}

public static void quickSort(int[] array) {

quick(array,0,array.length-1);

}

测试代码：

public class TestDemo {

public static void main(String[] args) {

int[] array = {10,3,2,7,19,78,65,127};

System.out.println("排序前：" + Arrays.toString(array));

QuickSort.quickSort(array);

System.out.println("排序后：" + Arrays.toString(array));

}

该代码的执行结果为：

可见，实现了对原数组的升序排序。

性能分析

时间复杂度：

最好情况：O(n * log(n))

平均情况：O(n * log(n))

最坏情况： O(n2)

空间复杂度：

最好情况：O(log(n))

平均情况：O(log(n))

最坏情况：O(n)

稳定性：不稳定

非递归实现快速排序

代码实现

逻辑代码：

/**

* 非递归实现快速排序

public class QuickSortNor {

public static void quickSortNor(int[] array) {

int low = 0;

int high = array.length - 1;

int piv = piovt(array, low, high);

Stack stack = new Stack<>();

if (piv > low + 1) {

stack.push(low);

stack.push(piv - 1);

}

if (piv < high - 1) {

stack.push(piv + 1);

stack.push(high);

}

while (!stack.isEmpty()) {

high = stack.pop();

low = stack.pop();

piv = piovt(array, low, high);

if (piv > low + 1) {

stack.push(low);

stack.push(piv - 1);

}

if (piv < high - 1) {

stack.push(piv + 1);

stack.push(high);

}

private static int piovt(int[] array, int start, int end) {

int temp = array[start];

while (start < end) {

while (start < end && array[end] >= temp) {

end--;

}

array[start] = array[end];

while (start < end && array[start] < temp) {

start++;

}

array[end] = array[start];

}

array[start] = temp;

return start;

}

测试代码：

public class TestDemo {

public static void main(String[] args) {

int[] array = {10,3,2,7,19,78,65,127};

System.out.println("排序前：" + Arrays.toString(array));

QuickSortNor.quickSortNor(array);

System.out.println("排序后：" + Arrays.toString(array));

}

该代码的执行结果为：

可见，实现了对原数组的升序排序。

性能分析

时间复杂度： O(n * log(n))

空间复杂度：

最好情况：O(log(n))

最坏情况：O(n)

稳定性：不稳定

归并排序

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

代码实现

逻辑代码：

public class MergeSort {

public static void merge(int[] array, int start, int mid, int end) {

int s1 = start;

int s2 = mid + 1;

int[] temp = new int[end - start + 1];

int k = 0;

while (s1 <= mid && s2 <= end) {

if (array[s1] <= array[s2]) {

temp[k++] = array[s1++];

} else {

temp[k++] = array[s2++];

}

while (s1 <= mid) {

temp[k++] = array[s1++];

}

while (s2 <= end) {

temp[k++] = array[s2++];

}

for (int i = 0; i < temp.length; i++) {

array[i + start] = temp[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, mid, high);

}

public static void mergeSort(int[] array) {

mergeSortInternal(array, 0, array.length - 1);

}

测试代码：

public class TestDemo {

public static void main(String[] args) {

int[] array = {10,3,2,7,19,78,65,127};

System.out.println("排序前：" + Arrays.toString(array));

MergeSort.mergeSort(array);

System.out.println("排序后：" + Arrays.toString(array));

}

该代码的执行结果为：

可见，实现了对原数组的升序排序。

性能分析

时间复杂度： O(n * log(n))

空间复杂度：O(n)

稳定性：稳定

非递归实现归并排序

代码实现

逻辑代码：

/**

* 非递归实现归并排序

public class MergeSortNor {

public static void merge(int[] array, int gap) {

int s1 = 0;

int e1 = s1 + gap - 1;

int s2 = e1 + 1;

int e2 = s2 + gap - 1 < array.length ? s2 + gap - 1 : array.length - 1;

int[] temp = new int[array.length];

int k = 0;

while (s2 < array.length) {

while (s1 <= e1 && s2 <= e2) {

if (array[s1] <= array[s2]) {

temp[k++] = array[s1++];

} else {

temp[k++] = array[s2++];

}

while (s1 <= e1) {

temp[k++] = array[s1++];

}

while (s2 <= e2) {

temp[k++] = array[s2++];

}

s1 = e2+1;

e1 = s1+gap-1;

s2 = e1+1;

e2 = s2 + gap - 1 < array.length ? s2 + gap - 1 : array.length - 1;

}

while (s1 < array.length) {

temp[k++] = array[s1++];

}

for (int i = 0; i < temp.length; i++) {

array[i] = temp[i];

}

public static void mergeSortNor(int[] array) {

for (int i = 1; i < array.length; i *= 2) {

merge(array, i);

}

测试代码：

public class TestDemo {

public static void main(String[] args) {

int[] array = {10,3,2,7,19,78,65,127};

System.out.println("排序前：" + Arrays.toString(array));

MergeSortNor.mergeSortNor(array);

System.out.println("排序后：" + Arrays.toString(array));

}

该代码的执行结果为：

可见，实现了对原数组的升序排序。

性能分析

时间复杂度： O(n * log(n))

空间复杂度：O(n)

稳定性：稳定

海量数据的排序问题

外部排序：排序过程需要在磁盘等外部存储进行的排序

前提：内存只有 1G，需要排序的数据有 100G

因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序。

先把文件切分成 200 份，每个 512 M

分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以

进行 200 路归并，同时对 200 份有序文件做归并过程，最终结果就有序了

排序总结

总结

Python接口自动化之文件上传/下载接口怎么实现

246 2022-10-04

Java集合和数据结构排序实例详解

java中的接口是类吗

Spring中的aware接口详情

Python接口自动化之文件上传/下载接口怎么实现

推荐文章

接口调用是什么意思？几种常用接口调用方式

接口设计原则

8款在线 API 接口文档管理工具

api管理系统是什么？

什么是接口调试？接口调试的步骤有哪些？

api 接口管理系统有哪些？

接口测试有几种测试方法

API文档生成工具有哪些？

微服务和api网关区别

交换机配置步骤

最近发表

热评文章

在线接口文档管理工具推荐，支持在线测试，HTTP接口

开源的在线接口文档wiki工具Mindoc的介绍与使

如何优雅的进行接口设计？接口设计的六大原则是什么？

什么是API测试,api检测公司

软件接口设计怎么做？前后端分离软件接口设计思路

接口管理平台推荐，几大接口管理平台总有一款适合你！