锐客网

  1. 首页 > it技术 > >

新手初学Java常见排序算法

目录

  • 1、冒泡排序
  • 2、选择排序
  • 3、简单插入排序
  • 4、希尔排序
  • 5、归并排序
  • 6、快速排序
  • 总结

1、冒泡排序 排序原理：相邻两个元素比较，如果前者比后者大，则交换两个元素。每执行一次，都会确定一个最大值，其位置就固定了，下一次就不需要再参与排序了。
时间复杂度：O(n^2)
稳定性：稳定
具体实现：
public class Bubble {/*** 对数组a中的元素进行排序*/public static void sort(Comparable[] a){//每冒泡一次，参与冒泡排序的元素个数就少一个//需要排序的次数为数组个数减一/*for (int i=a.length-1; i>0; i--){for (int j=0; j
优化：可以加一个标志位，当冒泡一次也没有执行的时候，就说明已经排好了，就不需要再冒泡了。

2、选择排序 排序原理：从数组中找出最小值的下标，然后将最小值交换到前边。每执行一次前边就会有一个最小值位置固定，之后就不再需要参与查找最小值了。
时间复杂度：O(n^2)
稳定性：不稳定
具体实现：
public class Selelction {/*** 将数组排序* @param a 待排序的数组*/public static void sort(Comparable[] a){for (int i=0; i 0; }/*** 交换数组的两个元素* @param a 数组* @param i 数组下标* @param j 数组下标*/privatestatic void exch(Comparable[] a, int i, int j){Comparable temp; temp = a[i]; a[i] = a[j]; a[j] = temp; }/*** 测试方法* @param args*/public static void main(String[] args) {Integer[] array = {1,6,7,3,2,5,7,8,4,0,5,3,7}; sort(array); System.out.println(Arrays.toString(array)); }


3、简单插入排序 排序原理：将数组分成两组，左边一组是已排序的，右边一组是未排序的，然后拿未排序的第一个与左边的从后往前比较，如果比前边的小就交换，直到前边的值比它小或者等于它。
时间复杂度：O(n^2)
稳定性：稳定
具体实现：
public class Insertion {/*** 对数组a中的元素进行排序*/public static void sort(Comparable[] a){for (int i = 1; i < a.length; i++) {for (int j = i; j > 0; j--){if (greater(a[j-1],a[j])){exch(a, j-1, j); }else {break; }}}}/*** 比较u元素是否大于v元素*/private static boolean greater(Comparable u, Comparable v){return u.compareTo(v) > 0; }/*** 交换数组下标为i和j的元素的位置*/private static void exch(Comparable[] a, int i, int j){Comparable temp; temp = a[i]; a[i] = a[j]; a[j] = temp; }/*** 测试*/public static void main(String[] args) {Integer[] a = {8, 5, 7, 4, 3, 2, 6, 8}; sort(a); System.out.println(Arrays.toString(a)); }}

优化思路：将要插入的数先保存起来，然后交换的代码就可以改成覆盖，就相当于后移，等找到合适位置再把之前保存的值放进去。

4、希尔排序 排序原理：是插入排序的优化版，插入排序在比较时只能一个一个比较，而希尔排序中加了一个增长量，可以跨元素比较，相对减少了比较交换的次数。
时间复杂度：O(n^1.3)
稳定性：不稳定
具体实现：
public class Shell {/*** 将数组排序* @param a 待排序的数组* @return 排好序的数组*/public static void sort(Comparable[] a){//1.确定增长量h的值int h=1; while(h < a.length/2){h = h*2+1; }//2.进行排序while(h>=1){//找到待排序的第一个值for (int i=h; i=h; j-=h){if (greater(a[j-h],a[j])){exch(a, j, j-h); }else{break; }}}//h减小h/=2; }}/*** 比较u元素是否大于v元素*/private static boolean greater(Comparable u, Comparable v){return u.compareTo(v) > 0; }/*** 交换数组下标为i和j的元素的位置*/private static void exch(Comparable[] a, int i, int j){Comparable temp; temp = a[i]; a[i] = a[j]; a[j] = temp; }//测试数据public static void main(String[] args) {Integer[] a = {8, 5, 7, 4, 3, 2, 6, 8, 6, 7}; sort(a); System.out.println(Arrays.toString(a)); }}


5、归并排序 排序原理：使用了递归的思想，先把数组从中间递归分解，接着先排序左边的子数组，然后再排序右边的子数组，最后合并为一个数组。核心方法是merge方法。
时间复杂度：O(nlogn)
稳定性：稳定
具体实现：
public class Merge {/*** 辅助数组*/private static Comparable[] access; /*** 对数组a进行排序* @param a*/public static void sort(Comparable[] a){//1.初始化辅助数组access = new Comparable[a.length]; //2.定义两个下标值int lo = 0; int hi = a.length -1; //3.调用分组排序函数sort(a, lo, hi); }/*** 对数组a中的lo到hi进行排序* @param a* @param lo* @param hi*/private static void sort(Comparable[] a, int lo, int hi){//保护if (hi <= lo){return; }//1.得到midint mid = lo + (hi-lo)/2; //2.对左数组分组排序sort(a, lo, mid); //3.对右数组分组排序sort(a, mid+1, hi); //4.将两个数组合并merge(a, lo, mid, hi); }/*** 将两个数组进行排序合并* @param a* @param lo* @param mid* @param hi*/private static void merge(Comparable[] a, int lo, int mid, int hi){//1.定义三个指针int i=lo; int p1=lo; int p2=mid+1; //2.分别遍历两个子数组，直到有一个数组遍历完毕while (p1 <= mid && p2 <= hi){if (less(a[p1], a[p2])){access[i++] = a[p1++]; }else{access[i++] = a[p2++]; }}//3。将剩下的一个数组的剩余值放到辅助数组中while(p1 <= mid){access[i++] = a[p1++]; }while(p2 <= hi){access[i++] = a[p2++]; }//4。将辅助数组中的值覆盖到原数组中for (int index=lo; index<=hi; index++){a[index] = access[index]; }}/*** 比较第一个下标的值是不是小于第二个下标的值* @param u* @param v* @return*/private static boolean less(Comparable u, Comparable v){return u.compareTo(v) <= 0; }/*** 测试*/public static void main(String[] args) {Integer[] a = {8, 5, 7, 4, 3, 2, 6, 8}; sort(a); System.out.println(Arrays.toString(a)); }}


6、快速排序 排序原理：把数组的第一个值设置为中间值，比中间值小的放到左边，比中间值大的放到右边。然后再对左边的做相同的操作，最后是对右边的做相同的操作。核心方法是partition方法，将小的数移到左边，大的数移到右边，最后返回中间值的下标。
时间复杂度：O(nlogn)
稳定性：不稳定
具体实现：
public class Quick {/*** 对数组a进行排序* @param a*/public static void sort(Comparable[] a){int lo = 0; int hi = a.length-1; sort(a, lo, hi); }/*** 对数组a中的lo到hi进行排序* @param a* @param lo* @param hi*/private static void sort(Comparable[] a, int lo, int hi){//保护if (hi <= lo){return; }//获取中间值int mid = partition(a, lo, hi); //对左子数组进行排序sort(a, lo, mid-1); //对右子数组进行排序sort(a, mid+1, hi); }/*** 将比子数组中第一个值小的数放到其左边，大于的放到右边，最后返回中间值的下标* @param a* @param lo* @param hi* @return*/private static int partition(Comparable[] a, int lo, int hi){//1.定义两个指针int p1= lo; int p2 = hi+1; while (true){//2.先移动右指针，找到第一个小于标准值的数while(less(a[lo],a[--p2])){if (p2 == lo){break; }}//3.移动左指针，找到第一个大于标准值的数while(less(a[++p1],a[lo])){if (p1 == hi){break; }}if (p1 >= p2){//5.退出循环break; }else {//4.交换两个值exch(a, p1, p2); }}//6.最后把子数组的第一个值和右指针所指的值交换，最后返回其下标exch(a, lo, p2); return p2; }/*** 比较第一个下标的值是不是小于第二个下标的值* @param u* @param v* @return*/private static boolean less(Comparable u, Comparable v){return u.compareTo(v) < 0; }/*** 交换数组中两个下标的值* @param a* @param i* @param j*/private static void exch(Comparable[] a, int i, int j){Comparable temp; temp = a[i]; a[i] = a[j]; a[j] = temp; }/*** 测试*/public static void main(String[] args) {Integer[] a = {8, 5, 7, 4, 3, 2, 6, 8}; sort(a); System.out.println(Arrays.toString(a)); }}


总结 【新手初学Java常见排序算法】本篇文章就到这里了，希望能给你您带来帮助，也希望您能够多多关注脚本之家的更多内容！

    推荐阅读


    上一篇：spring框架集成flyway项目的详细过程

    下一篇：Mybatis如何实现关联属性懒加载