admin 管理员组文章数量: 1086019
2024年4月13日发(作者：底部导航)
排序
常见的简单排序算法
I. 选择排序
选择排序思路：选择出数组中的最小元素，将它与数组的第一个元素交换位置。
再从剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。 不断
进行这样的操作，直到将整个数组排序。
public void sort(int[] arr){
int N = ;
int minIndex = -1;
for(int i=0;i 是当前元素 minIndex=i; for(int j=i+1;j 当前元素后面的元素 if(arr[j] minIndex=j; } } if(minIndex==i){ //TODO: 这里有个小优化：如果当前元素是最小的则不用 交换了 continue; } swap(arr,minIndex,i); } } private void swap(int[] arr,int i,int j){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } @Test public void test(){ int[] a={3,5,2,4,1,0,-3}; rray(a); sort(a); rray(a); } 选择排序需要 ~N2/2 次比较和 ~N 次交换，它的运行时间与输入无关，这个特点 使得它对一个已经排序的数组也需要这么多的比较和交换操作。 II. 冒泡排序 冒泡排序思路：从左到右不断交换相邻逆序的元素，在一轮的循环之后，可以让 未排序的最大元素上浮到右侧。在一轮循环中，如果没有发生交换，就说明数组 已经是有序的，此时可以直接退出。 public void sort(int[] arr){ for(int i=-1;i>0;i--){ for(int j=0;j if(arr[j]>arr[j+1]){ swap(arr,j,j+1); } } } } private void swap(int[] arr,int i,int j){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } 添加一个状态变量对冒泡排序进行优化： public void sort(int[] arr){ boolean isSorted = false; for(int i=-1;i>0 && !isSorted ;i--){ //!isSorted 条件，当 isSorted=true 时说明是有序的，则不需要再执行了 isSorted = true; // 初始时认为是有序的 for(int j=0;j if(arr[j]>arr[j+1]){ isSorted = false; // 存在逆序，则是无序的 swap(arr,j,j+1); } } } } private void swap(int[] arr,int i,int j){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } 冒泡排序是稳定的排序算法，平均时间复杂度是 O(n^2)。
版权声明：本文标题：Java 排序 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/b/1712965011a614626.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论