1、冒泡排序
排序原理：相邻两个元素比较，如果前者比后者大，则交换两个元素。每执行一次，都会确定一个最大值，其位置就固定了，下一次就不需要再参与排序了。
时间复杂度： O(n^2)
稳定性：稳定
具体实现：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
public class Bubble { /** * 对数组a中的元素进行排序 */ public static void sort(Comparable[] a){ //每冒泡一次，参与冒泡排序的元素个数就少一个 //需要排序的次数为数组个数减一 /*for (int i=a.length-1; i>0; i--){ for (int j=0; j<i; j++){ if (greater(a[j],a[j+1])){ exch(a, j,j+1); } } }*/ for (int i=0; i<a.length-1; i++){ for (int j=0; j<a.length-i-1; j++){ if (greater(a[j],a[j+1])){ exch(a, j,j+1); } } } } /** * 比较u元素是否大于v元素 */ private static boolean greater(Comparable u, Comparable v){ return u测试数据pareTo(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 }; sort(a); System.out.println(Arrays.toString(a)); } } |
优化：可以加一个标志位，当冒泡一次也没有执行的时候，就说明已经排好了，就不需要再冒泡了。
2、选择排序
排序原理：从数组中找出最小值的下标，然后将最小值交换到前边。每执行一次前边就会有一个最小值位置固定，之后就不再需要参与查找最小值了。
时间复杂度： O(n^2)
稳定性：不稳定
具体实现：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
public class Selelction { /** * 将数组排序 * @param a 待排序的数组 */ public static void sort(Comparable[] a){ for ( int i= 0 ; i<a.length- 1 ; i++){ //找出最小的值 int minIndex = i; //注意这里不需要减一 for ( int j=i+ 1 ; j<a.length; j++){ //Comparable数组 不能直接用下标比较大小 if (greater(a[minIndex],a[j])){ minIndex = j; } } //交换 if (minIndex != i){ exch(a, minIndex, i); } } } /** * 比较第一个参数是否大于第二个参数 * @param a * @param b * @return 第一个参数是否大于第二个参数 */ private static boolean greater(Comparable a, Comparable b){ return a测试数据pareTo(b) > 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; } /** * 测试方法 * @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)
稳定性：稳定
具体实现：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
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测试数据pareTo(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)
稳定性：不稳定
具体实现：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
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<a.length; i++){ for ( int j=i; j>=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测试数据pareTo(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)
稳定性：稳定
具体实现：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
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.得到mid int 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测试数据pareTo(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)
稳定性：不稳定
具体实现：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
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测试数据pareTo(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)); } } |
总结
本篇文章就到这里了，希望能给你您带来帮助，也希望您能够多多关注的更多内容！
原文链接：https://HdhCmsTestcnblogs测试数据/lk0528/p/14969735.html