冒泡排序(Bubble Sort)
1,正常写法
① 从头开始比较每一对相邻元素,如果第1个比第2个大,就交换它们的位置
执行完一轮后,最末尾那个元素就是最大的元素
② 忽略 ① 中曾经找到的最大元素,重复执行步骤 ①,直到全部元素有序
Integer[] array = {7, 3, 5, 8, 6, 7, 4, 5};
int count = 0 ;
for (int end = array.length-1; end > 0; end--) {
for (int begin = 1; begin <= end; begin++) {
count ++ ;
if (array[begin] < array[begin - 1]) {
int temp = array[begin];
array[begin] = array[begin - 1];
array[begin - 1] = temp;
}
}
}
System.out.println(" count = " + count);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + "_");
}
count = 28
3_4_5_5_6_7_7_8_
2,优化1
如果序列已经完全有序,可以提前终止冒泡排序
Integer[] array = {7, 3, 5, 8, 6, 7, 4, 5};
int count = 0 ;
for (int end = array.length -1; end > 0; end--) {
boolean sorted = true ;
for (int begin = 1; begin <=end; begin++) {
count ++ ;
if (array[begin] < array[begin - 1]) {
int temp = array[begin];
array[begin] = array[begin - 1];
array[begin - 1] = temp;
sorted = false ;
}
}
if(sorted) break;
}
2,优化2
如果序列尾部已经局部有序,可以记录最后1次交换的位置,减少比较次数
Integer[] array = {7, 3, 5, 8, 6, 7, 4, 5};
int count = 0 ;
for (int end = array.length -1; end > 0; end--) {
int sortedIndex = 1 ;
for (int begin = 1; begin <=end; begin++) {
count ++ ;
if (array[begin] < array[begin - 1]) {
int temp = array[begin];
array[begin] = array[begin - 1];
array[begin - 1] = temp;
sortedIndex = begin ;
}
}
end = sortedIndex;
}
3,优化方式:鸡尾酒排序,也叫双向冒泡排序,看到别人的 ,优不优,我没研究
public static Integer[] sort(Integer[] arr){
//依次将最大的数放置到数组末尾,将第二大的数放到倒数第二位...
boolean changed;
for(int i = 0;i < arr.length/2;i++){
changed = false;
//从前往后,比较相邻两个数,把大的放在后边.之前已放置成功的可以不再参与比较
for(int j = i;j < arr.length-1-i;j++){
if(arr[j]>arr[j+1]) {
swap(arr,j,j+1);
changed =true;
}
}
if(!changed){
break;
}
for(int j = arr.length-1-i; j > i; j--){
if(arr[j]<arr[j-1]) {
swap(arr,j,j-1);
changed = true;
}
}
if(!changed){
break;
}
}
return arr;
}
public static void swap(Integer[] arr, int pos1, int pos2){
int temp = arr[pos1];
arr[pos1] = arr[pos2];
arr[pos2] = temp;
}
◼ 最坏、平均时间复杂度:O(n2)
◼ 最好时间复杂度:O(n)
◼ 空间复杂度:O(1)
网友评论