Java集合和数据结构排序实例详解 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[] 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() {@Overridepublic 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)。

稳定性：稳定

【Java集合和数据结构排序实例详解】
快速排序

从待排序区间选择一个数，作为基准值(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)); }}

该代码的执行结果为：