八大排序算法解析及Java实现
本文共 9930 字，大约阅读时间需要 33 分钟。
八大排序算法解析及Java实现
1、冒泡排序
时间复杂度:
| 平均时间 | 最好情况 | 最坏情况 |
|---|---|---|
| O(n^2) | O(n) | O(n^2) |
空间复杂度:
O(1)两层循环：
第一层循环从第一个元素到倒数第二个元素，因为每次比较是前一个元素和后一个元素进行比较， 所以在第一层循环，最后一个元素会和前一个元素进行比较，所以就没必要循环到最后一个元素。 第二层循环从0到 length-i-1，也就是还没有比较，此时是乱序的元素。改良算法:
该冒泡排序为改良的冒泡排序，添加了监视哨 flag,定义初始值为 true，在一层循环的比较中，如果发生了交换，则改为 false，如果没有发生交换，flag 为 true，说明序列有序，就不需要进行循环了，则直接退出，节省了时间。Java 实现
public class BubbleSort { public static void bubbleSort(int arrays[]) { for (int i = 0; i < arrays.length - 1; i++) { boolean flag = true; for (int j = 0; j < arrays.length - 1 - i; j++) { if (arrays[j] > arrays[j + 1]) { arrays[j] = arrays[j] + arrays[j + 1]; arrays[j + 1] = arrays[j] - arrays[j + 1]; arrays[j] = arrays[j] - arrays[j + 1]; flag = false; } } if (flag) { break; } } } public static void main(String[] args) { int[] arrays = new int[]{5, 4, 3, 2, 1}; bubbleSort(arrays); for (int array : arrays) { System.out.print(array + " "); } }} 2、插入排序
时间复杂度:
| 平均时间 | 最好情况 | 最坏情况 |
|---|---|---|
| O(n^2) | O(n) | O(n^2) |
空间复杂度:
O(1)具体思路:
第一层循环从 1 开始，到数组的长度，因为默认第一个元素(下标0)有序， 定义 j 为 i-1，即为待插入的位置，默认有序数组的最后一个位置， key 为需要新插入的元素，为外层循环 i 下标的元素， 第二层循环，当下标在大于或等于0的范围内则继续，该例子为升序排列， 如果当前的数大于待插入的数 key，循环就继续，元素就到往后移动一位， 最后一步，把待插入的数 key插入到待插入的位置。为什么是 j+1 的位置，因为 在 while 里面，当把 j 位置上的数移到后边时，j 又减了1,如果这个时候循环条件 不满足退出了，理应该是插入 j 的位置，所以需要加回 1。Java 实现
public class InsertSort { public static void insertSort(int arrays[]) { for (int i = 1; i < arrays.length; i++) { int key = arrays[i]; int j = i - 1; while (j >= 0 && arrays[j] > key) { arrays[j + 1] = arrays[j]; j--; } arrays[j + 1] = key; } } public static void main(String[] args) { int[] arrays = new int[]{4, 2, 1, 3, 5}; insertSort(arrays); for (int array : arrays) { System.out.print(array + " "); } }} 3、希尔排序
时间复杂度:
| 平均时间 | 最好情况 | 最坏情况 |
|---|---|---|
| O(nlogn) | O(nlog^2n) | O(nlog^2n) |
空间复杂度:
O(1)具体思路：
希尔排序是插入排序的改进，运用了分治的思想，定义了一个增量数组 d， 根据增量的个数，进行 k 趟排序，增量值为从大到小，优先比较较远距离 的数，减少交换的次数。Java 实现
public class ShellSort { public static void shellSort(int[] arrays, int d[]) { for (int k = 0; k < d.length; k++) { int dk = d[k]; for (int i = dk; i < arrays.length; i++) { int key = arrays[i]; int j = i - dk; while (j >= 0 && arrays[j] > key) { arrays[j + dk] = arrays[j]; j -= dk; } arrays[j + dk] = key; } } } public static void main(String[] args) { int[] arrays = new int[]{5, 4, 3, 2, 1}; shellSort(arrays, new int[]{3, 2, 1}); for (int array : arrays) { System.out.print(array + " "); } }} 4、快速排序
时间复杂度:
| 平均时间 | 最好情况 | 最坏情况 |
|---|---|---|
| O(nlogn) | O(nlogn) | O(n^2) |
空间复杂度:
O(1)具体思路:
1、定义两个哨兵，一个准基数，一个哨兵从右边找比准基数小的， 另一个哨兵从左边找比准基数大的，如果找到了就交换位置。 2、当两个哨兵相遇后，就和准基数交换位置，此时，准基数左边的 数都比准基数小，右边的数都比准基数大，再递归对左边的数和右边 的数进行相同的排序方式。推荐一篇博文：https://blog.csdn.net/shujuelin/article/details/82423852
Java 实现
public class QuickSort { public static void quickSort(int[] arrays, int low, int high) { if (low > high) return; //i,j 是哨兵，t 是准基数 int i = low, j = high, t = arrays[low]; while (i < j) { //从右边找一个比基准数小的数 while (arrays[j] >= t && i < j) { j--; } while (arrays[i] <= t && i < j) { i++; } //如果找到了就交换 if (i < j) { arrays[i] = arrays[i] + arrays[j]; arrays[j] = arrays[i] - arrays[j]; arrays[i] = arrays[i] - arrays[j]; } //两个哨兵相遇后，与基准数交换 arrays[low] = arrays[i]; arrays[i] = t; //继续对前一部分和后一部分排序 quickSort(arrays, low, i - 1); quickSort(arrays, i + 1, high); } } public static void main(String[] args) { int[] arr = {10, 4, 7, 62, 3, 2, 1, 8, 9, 19}; quickSort(arr, 0, arr.length - 1); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } }} 5、堆排序
时间复杂度:
| 平均时间 | 最好情况 | 最坏情况 |
|---|---|---|
| O(nlogn) | O(nlogn) | O(nlogn) |
空间复杂度:
O(1)具体思路:
1、首先是建堆，从数组中间的下标开始，建立一个大顶堆， 在建立的过程中，i 依次递减，在起始下标为 1 的前提下， 2*i 为左节点，2*i+1为右节点，然后比较当前节点(根节点)， 左节点，右节点的大小，选出最大的，和根节点进行交换， 当进行交换后，可能下层的子树不满足最大堆的性质，则需要 递归调整大小。 2、每次调整为最大堆后，把根节点和最后一个节点交换位置， 然后排除根节点，然后调整剩下的节点，以满足最大堆性质， 重复这个过程，直到排序完成。Java 实现
public class HeapSort { //构建一个最大堆 public static void build_max_heap(int array[], int length) { for (int i = array.length / 2; i > 0; i--) { max_heapify(array, i, length); } } //调整最大堆 public static void max_heapify(int arrays[], int i, int length) { // int l = i * 2;//左节点，数组初始下标为 1，为 0 时为2*i+1 int r = i * 2 + 1; int largest = -1; if (l < length && arrays[l] > arrays[i]) { largest = l; } else { largest = i; } if (r < length && arrays[r] > arrays[largest]) { largest = r; } if (largest != i) { //交换当前节点a[i]和最大的节点a[largest] arrays[i] = arrays[i] + arrays[largest]; arrays[largest] = arrays[i] - arrays[largest]; arrays[i] = arrays[i] - arrays[largest]; max_heapify(arrays, largest, length); } } //堆排序 //最大堆，每次调整，最大元素总在a[1]中，与a[n]互换，然后排除a[n]再调整 //在剩余节点中，由于交换并排序了原来为最大节点的根，可能会违背最大堆的性质 //为了维护最大堆，则调用max_heapify(array,1,i)在a[1..i]上构造一个最大堆 //每一次取出最大元素，绕后调整最大堆 public static void sort_heap(int array[]) { build_max_heap(array, array.length); int i = array.length - 1; while (i > 1) { array[1] = array[1] + array[i]; array[i] = array[1] - array[i]; array[1] = array[1] - array[i]; i--; max_heapify(array, 1, i); } } public static void main(String[] args) { int nums[] = {0, 5, 3, 17, 10, 84, 19, 6, 22, 9, 35}; sort_heap(nums); for (int i : nums) System.out.print(i + " "); }} 6、归并排序
时间复杂度:
| 平均时间 | 最好情况 | 最坏情况 |
|---|---|---|
| O(nlogn) | O((nlogn) | O((nlogn) |
空间复杂度:
O(n)基本思路:
1、首先实现二路归并的代码，定义i，j两个指针，一个指针从左边的第一个下标开始， 另一个指针从右边的第一个下标开始移动，再定义一个临时数组，用来复制有序的序列， 2、使用一层循环来复制数组，依次比较 i 和 j 下标所对应的数，把较小的数先复制到临时 数组里面。最后在使用两个循环判断左右两组数还有没有没有复制完成的数，如果还有没复制 的数，再全部复制到临时数组里面。 3、最后把临时数组复制到原数组里面。 4、对数组进行递归排序，依次对左边的数和右边的数进行递归，当序列只有一个元素时， 表示递归结束，进行回调。 6、最后把各个有序的子序列合并成整个有序的序列。Java 实现
public class MergeSort { public static void merge(int[] arrays, int p, int q, int r) { int[] temp = new int[arrays.length]; int i = p, j = q + 1, k = p; while (i <= q && j <= r) { if (arrays[i] <= arrays[j]) { temp[k++] = arrays[i++]; } else { temp[k++] = arrays[j++]; } } while (i <= q) temp[k++] = arrays[i++]; while (j <= r) temp[k++] = arrays[j++]; //将temp从索引p位置开始，赋值到arrays索引p的位置，赋值r-p+1个数 System.arraycopy(temp,p,arrays,p,r-p+1); } public static void mergeSort(int[] arrays, int p, int r) { if (p < r) {//当子序列只有一个元素是递归结束 int q = (p + r) / 2; mergeSort(arrays, p, q); mergeSort(arrays, q + 1, r); merge(arrays, p, q, r); } } public static void main(String[] args) { int[] arrays = new int[]{5, 2, 3, 4, 1}; mergeSort(arrays, 0, arrays.length - 1); for (int array : arrays) { System.out.print(array + " "); } }} 7、选择排序
时间复杂度:
| 平均时间 | 最好情况 | 最坏情况 |
|---|---|---|
| O(n^2) | O(n^2) | O(n^2) |
空间复杂度:
O(1)基本思路:
1、第一层循环从0到倒数第二个数，为什么是第二个数，因为是每次
选择一个最小的数放到前面，所以最后一个数不用选择。 2、定义一个下标min保存最小的数的下标，每次循环默认下标为i的为最小 的数，依次和 j 进行比较，如果下标为 j 的比下标为 i 的小，就把 j 下标赋值 给 min。 3、每一次第一层循环结束，就把 下标为 i 的数和下标为 min的数进行交换。Java 实现
public class SelectionSort { public static void selectSort(int[] arrays) { int min; for (int i = 0; i < arrays.length - 1; i++) { min = i; for (int j = i + 1; j < arrays.length; j++) { if (arrays[j] < arrays[min]) { min = j; } } int t = arrays[i]; arrays[i] = arrays[min]; arrays[min] = t; } } public static void main(String[] args) { int[] arrays = new int[]{5, 2, 3, 4, 1}; selectSort(arrays); for (int array : arrays) { System.out.print(array + " "); } }} 8、计数排序
时间复杂度:|
| 平均时间 | 最好情况 | 最坏情况 |
|---|---|---|
| O(n+k) | O(n+k) | O(n+k) |
空间复杂度:|
O(k)|
基本思路:
1、假设 n个输入元素中的每一个都是在 0 到 k区间的一个整数。 2、初始化一个数组，默认值都设置为0。 3、遍历需要排序的数组，如果一个数为a[j]，那c[a[j]]就加1。 4、然后循环数组c，计算计算有几个数是小于c[i]的。 5、定义一个数组b，从a的最后一个元素开始，然后把数依次放到数组b里面， 因为c[arrays[j]]存放的是小于arrays[j]的数，所以可以由后往前根据下标和值赋值给 数组b，赋值完成后，c[arrays[j]]需要减一，如果下一个数和arrays[j]相同，就可以 放到前一个位置上。Java 实现
public class CountingSort { public static void countSort(int[] arrays, int b[]) { int c[] = new int[arrays.length]; //初始化操作，数组c的值全部设置为0 for (int i = 0; i < arrays.length; i++) { c[i] = 0; } //遍历每一个输入的值，如果一个元素输入值为i，则从c[i]加1 //c[i]保存的就是等于i的元素的个数 for (int j = 1; j < arrays.length; j++) { c[arrays[j]]++; } //计算有多少个元素是小于或等于i的 for (int i = 1; i < arrays.length; i++) { c[i] = c[i] + c[i - 1]; } for (int j = arrays.length - 1; j >= 1; j--) { //把每个元素a[j]放到输出数组b的正确位置上 b[c[arrays[j]]] = arrays[j]; //如果有多个相同的数，则需要减一，那么下一个相同的数将会放到该数的前一个位置上 c[arrays[j]] -= 1; } } public static void main(String[] args) { int arrays[] = new int[]{0, 5, 4, 1, 2, 3}; int b[] = new int[arrays.length]; countSort(arrays, b); for (int i : b) { System.out.print(i + " "); } }} 9、小结
ABOUT
公众号：【星尘Pro】
github：
推荐阅读
你可能感兴趣的文章
C++总结8——shared_ptr和weak_ptr智能指针
查看>>
c++写时拷贝1
查看>>
C++ 写时拷贝 2
查看>>
Linux网络编程---I/O复用模型之poll
查看>>
Java NIO详解
查看>>
单列模式-编写类ConfigManager读取属性文件
查看>>
java中float和double的区别
查看>>
Statement与PreparedStatement区别
查看>>
Tomcat配置数据源步骤以及使用JNDI
查看>>
before start of result set 是什么错误
查看>>
(正则表达式)表单验证
查看>>
在JS中 onclick="save();return false;"return false是
查看>>
JSTL 常用标签总结
查看>>
内容里面带标签，在HTML显示问题，JSTL
查看>>
VS编译器运行后闪退，处理方法
查看>>
用div+css做下拉菜单，当鼠标移向2级菜单时，为什么1级菜单的a:hover背景色就不管用了？
查看>>
idea 有时提示找不到类或者符号
查看>>
JS遍历的多种方式
查看>>
ng-class的几种用法
查看>>
node入门demo-Ajax让前端angularjs/jquery与后台node.js交互,技术支持：mysql+html+angularjs/jquery
查看>>