选择排序与冒泡排序的特点与区别
++++++++++++++++++++++++++++++++++++++++++++++
选择排序 | 这一种简单的排序方法,它的基本思想是: R[n] 第一次从R[0]~R[n-1]中选取最小值,与R[0]交换; 第二次从R[1]~R[n-1]中选取最小值,与R[1]交换; ...., 第i次从R[i-1]~R[n-1]中选取最小值,与R[i-1]交换; ....., 第n-1次从R[n-2]~R[n-1]中选取最小值,与R[n-2]交换; 总共通过n-1次,得到一个按排序码从小到大排列的有序序列. |
特点 | 选择排序的平均时间复杂度是O(n²)的。 |
1 for(int i = 0;i<arr.length;i++){ 2 3 for(int j= 1 ; j<arr.length;j++){ 4 if(arr[j-1]>arr[j]){ 5 int temp = arr[j]; 6 arr[j] = arr[j-1]; 7 arr[j-1] = temp; 8 9 }10 }11}
+++++++++++++++++++++++++++++++++++++++++++++++
冒泡排序 | 依次比较相邻的两个数,将小数放在前面,大数放在后面。 即在第一趟: 首先比较第1个和第2个数,将小数放前,大数放后; 然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后; 至此第一趟结束,将最大的数放到了最后。 在第二趟: 仍从第一对数开始比较(因为可能由于第2个数和第3个数的交换,使得第1个数不再小于第2个数),将小数放前,大数放后; 一直比较到倒数第二个数(倒数第一的位置上已经是最大的); 第二趟结束,在倒数第二的位置上得到一个新的最大数(其实在整个数列中是第二大的数)。 如此下去,重复以上过程,直至最终完成排序。 |
特点 | 冒泡排序的平均时间复杂度与插入排序相同,也是平方级的,但也是非常容易实现的算法。 |
1 for(int i =0;i<arr.length-1;i++){ //从第一个开始遍历 2 3 for(int j=0;j<arr.length-1-i;j++){ // 4 5 if(arr[j]>arr[j+1]){ //前面的数比后面的数大 6 int temp = arr[j]; //然后进行交换,将大的往后排 7 arr[j] = arr[j+1]; 8 arr[j+1] = temp; 9 }10 } 11}
陌陌说:选择排序(包含shaker排序/堆排序)和冒泡排序都属于交换排序的一种。
计算机的一些排序算法:插入排序 、冒泡排序 、选择排序 、快速排序 、堆排序 、归并排序、基数排序、希尔排序
【每个排序算法都有一个 平均时间复杂度】
原标题:java 选择排序与冒泡排序
关键词:JAVA