旅游手机网站开发,wordpress 汉化工具,新浪云存储 wordpress,公众号网页如何制作排序算法 文章目录 冒泡排序算法步骤动图代码优化总结 选择排序算法步骤动图代码总结 插入排序算法步骤动图代码总结 排序算法#xff0c;就是使一串记录#xff0c;按照其中的某个或某些关键字的大小#xff0c;递增或递减的排列起来的操作。一般默认排序是按照由小到大即…排序算法 文章目录 冒泡排序算法步骤动图代码优化总结 选择排序算法步骤动图代码总结 插入排序算法步骤动图代码总结 排序算法就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。一般默认排序是按照由小到大即升序排列。
冒泡排序
冒泡排序Bubble Sort简单的基于比较的排序算法。每次比较相邻两个元素如果他们的顺序错误就把他们交换过来。由于较大的数据会不断地向上”冒“所以以冒泡排序命名。
算法步骤
从头开始比较相邻元素如果顺序不对就交换。每次选出一个局部最大值走过n - 1 趟后数组就有序了
动图 代码
public class P02_BubbleSort {public static void bubbleSort(int[] arr) {if(arr null || arr.length 2) {return;}for(int i 0;i arr.length - 1;i) {for(int j 0;j arr.length - 1 - i;j) {if(arr[j] arr[j 1]) {swap(arr,j,j 1);}}}}public static void swap(int[] arr,int i,int j) {int t arr[i];arr[i] arr[j];arr[j] t;}public static void main(String[] args) {int[] arr {9,8,7,6,5,4,3,2,1};bubbleSort(arr);System.out.println(Arrays.toString(arr));}
}优化 public static void bubbleSort(int[] arr) {if(arr null || arr.length 2) {return;}for(int i 0;i arr.length - 1;i) {boolean success false; for(int j 0;j arr.length - 1 - i;j) {if(arr[j] arr[j 1]) {swap(arr,j,j 1);success true;}}if(success false) {break;// 已经有序}}
}总结
冒泡排序的时间复杂度 O ( N ) O(N) O(N)空间复杂度 O ( 1 ) O(1) O(1)冒泡排序是一种性能比较差的排序如果不优化那么无论是何种数据状况都要经理 N 2 N^2 N2次比较。冒泡排序大量浪费比较行为每趟比较只会选择出一个最大值所以性能较差。
选择排序
选择排序是一种简单直观的基于比较的排序算法性能不受数据状况的左右就算是已经有序的数据也是 O ( N 2 ) O(N^2) O(N2)的时间复杂度。
算法步骤 不用交换的没有画出
0 ~ n - 1 范围 找到最小值 交换到 0 位置1 ~ n - 1 范围 找到最小值 交换到 1 位置2 ~ n - 1 范围 找到最小值 交换到 2 位置… …n - 2 ~ n - 1 范围找到较小值 交换到 n - 2 位置排序完成
动图 代码
package package01;import java.util.Arrays;public class P01_SelectSort {public static void selectSort(int[] arr) {if (arr null || arr.length 2) {return;}for (int i 0; i arr.length; i) {int minIndex i;for (int j i 1; j arr.length; j) {minIndex arr[minIndex] arr[j] ? minIndex : j;}swap(arr, minIndex, i);}}public static void swap(int[] arr, int i, int j) {int t arr[i];arr[i] arr[j];arr[j] t;}public static void main(String[] args) {int[] arr {9,8,7,6,5,4,3,2,1};selectSort(arr);System.out.println(Arrays.toString(arr));}
}总结
选择排序也是一种性能较差的排序算法性能不受数据状况左右大量浪费比较行为。
插入排序 插入排序就像打扑克时拿牌一样一张一张将扑克牌放到对应的位置也是一个基于比较的排序。只是插入排序受数据状况影响当数据状况趋于有序时插入排序的速度会非常快趋于 O ( N ) O(N) O(N)但是时间复杂度是最坏情况所以插入排序的时间复杂度是 O ( N 2 ) O(N^2) O(N2).
算法步骤 就如上述数据我们要将这组数字从小到大进行排列。从左往右依次考虑每个数字让这个数字左边局部有序考虑完整个数据就有序了。
考虑前 1 1 1 个数 已经有序考虑前 2 2 2 个数如果前面的数据大于当前数则交换做到局部有序考虑前 3 3 3 个数如果前面的数据大于当前数则交换做到局部有序… …考虑前 n − 1 n - 1 n−1 个数如果前面的数据大于当前数则交换做到局部有序完成排序
动图 代码
package package01;import java.util.Arrays;public class P03_InsertSort {public static void insertSort(int[] arr) {if(arr null || arr.length 2) {return;}for(int i 1;i arr.length;i) {for(int j i - 1;j 0 arr[j] arr[j 1];j--) {swap(arr,j,j1);}}}public static void swap(int[] arr,int i,int j) {int t arr[i];arr[i] arr[j];arr[j] t;}public static void main(String[] args) {int[] arr {0,9,8,7,6,5,4,3,2,1};insertSort(arr);System.out.println(Arrays.toString(arr));}
}总结
插入排序的常数时间要优于选择排序和插入排序但是其时间复杂度仍然是 O N 2 ON^2 ON2
如果本篇文章对你有帮助请点赞、评论、转发你的支持是我创作的动力。
