排序算法之冒泡排序和选择排序【Java版】
引言
本篇是排序算法的第一篇,介绍冒泡排序和选择排序,后面的几篇将会陆续的更新。
冒泡算法
1、算法步骤
比较相邻的元素。如果第一个比第二个大,就交换他们两个。
从第一位开始,持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
2、什么时候最快
当元素已经是正序的时候(因为这时候排序已经完成)
3、什么时候最慢
当元素已经是倒序的时候(因为这时候每个元素都要交换n-1次)
4、算法实现
public class BubbleSort { public static void main(String[] args) { int[] numbers = {12,2,24,30,6,16}; int[] result = BubbleSort.bubbleSort(numbers); StringBuffer stringBuffer = new StringBuffer(); for (int i = 0; i < result.length; i++) { stringBuffer.append(result[i] + " "); } System.out.println(stringBuffer.toString()); } //冒泡排序算法 public static int[] bubbleSort(int[] numbers){ //对参数进行拷贝 int[] needSort = Arrays.copyOf(numbers, numbers.length); for(int i=1; i<needSort.length; i++){ boolean flag =true; for(int j=0; j<needSort.length - i; j++){ if(needSort[j] > needSort[j+1]){ int t = needSort[j]; needSort[j] = needSort[j+1]; needSort[j+1] = t; flag = false; } } //如果为true,说明后面的排序已经完成,没有交换的元素了 if(flag){ break; } } return needSort; } } 复制代码
控制台输出:
2 6 12 16 24 30 复制代码
选择排序
1、算法步骤
首先选择排序序列中最小的数字,然后放置到首位,第一轮结束。
第二轮再在剩余的排序队列中选择最小的,再放置到第二位,继续循环,直到排序完成。
2、时间复杂度
平均时间复杂度O(n2n^2n2)
3、算法实现
public class ChoseSort { public static void main(String[] args) { int[] numbers = {12,2,24,30,6,16}; int[] result = ChoseSort.sort(numbers); StringBuffer stringBuffer = new StringBuffer(); for (int i = 0; i < result.length; i++) { stringBuffer.append(result[i] + " "); } System.out.println(stringBuffer.toString()); } //选择排序算法 public static int[] sort(int[] numbers){ //对参数进行拷贝 int[] needSort = Arrays.copyOf(numbers, numbers.length); int length = needSort.length; //总共要比较n-1次 for(int i=0; i<length-1; i++){ int min = i; for(int j=i+1; j<length; j++){ if(needSort[min] > needSort[j]){ min = j; } } //交换位置 if(i != min){ int tmp = needSort[i]; needSort[i] = needSort[min]; needSort[min] = tmp; } } return needSort; } } 复制代码
控制台输出:
2 6 12 16 24 30
作者:夏夜凉月
链接:https://juejin.cn/post/7027752494818131976