使用java，javasript，python实现冒泡排序的三个版本

分手后的思念是犯贱 2023-01-15 03:55 84阅读 0赞

## 概要 ##

冒泡排序是最简单的一种排序方式，最基础的实现用嵌套的两层for循环即可实现。但是即便是最简单的冒泡排序也存在着很大的优化空间，我们可以对两层循环分别进行优化。

首先来看一下两层for循环的作用：

外层for循环是`对比较趟数`的控制  
内层for循环时对每一趟`比较次数`的控制

存在的优化空间是：

对于外层循环，如果数组已经有序，就不需要再进行外层循环了，需要一个标记来进行跟踪数组是否已经有序。而有序的标志是某一趟不再进行数据交换了。

对于内层循环，由于冒泡排序每一次是把最大的放到最后，所以后面的元素是有序的，因此可以记下每一趟停止比较的位置，后续不需要再往后进行比较。

## Python实现 ##

### 基础冒泡 ###

def dubble(list):
        for i in range(len(list)-1):
            for j in range(len(list)-1):
                if list[j] > list[j+1]:
                    list[j],list[j+1] = list[j+1],list[j]
    
        return list
    
    list = [4,2,6,9,1,7,3,5,8]
    print(dubble(list))

### 第一次优化，减少外层循环次数 ###

def dubble(list):
        for i in range(len(list)-1):
            label = 'true'
            for j in range(len(list)-1):
                if list[j] > list[j+1]:
                    list[j],list[j+1] = list[j+1],list[j]
                    label = 'false'
            if label == 'true':
                return list
    
        return list
    
    list = [4,2,6,9,1,7,3,5,8]
    print(dubble(list))

### 第二次优化，减少内层循环次数 ###

def dubble(list):
        lastExchangeLabel = len(list)-1
        for i in range(len(list)-1):
            label = 'true'
            for j in range(lastExchangeLabel):
                if list[j] > list[j+1]:
                    list[j],list[j+1] = list[j+1],list[j]
                    label = 'false'
                    lastExchangeLabel = j
            if label == 'true':
                return list
    
        return list
    
    list = [4,2,6,9,1,7,3,5,8]
    print(dubble(list))

## Java实现 ##

### 基础冒泡 ###

import java.lang.reflect.Array;
    import java.util.Arrays;
    
    public class Bubble { 
        public static void sort(int array[]){ 
            for(int i=0;i<array.length;i++){ 
                for(int j=0;j<array.length-i-1;j++){ 
                    int tmp = 0;
                    if (array[j] > array[j+1]){ 
                        tmp = array[j];
                        array[j] = array[j+1];
                        array[j+1] = tmp;
                    }
                }
            }
        }
        public static void main(String[] args){ 
            int[] array = new int[]{ 5,8,6,3,9,2,1,7};
            sort(array);
            System.out.println(Arrays.toString(array));
        }
    }

### 第一次优化，减少外层循环次数 ###

import java.util.Arrays;
    
    public class Bubble02 { 
        public static void sort(int array[]){ 
            for(int i=0;i<array.length;i++){ 
                // 减少外层循环的次数
                boolean isSorted = true;
                for(int j=0;j<array.length-i-1;j++){ 
                    int tmp = 0;
                    if (array[j] > array[j+1]){ 
                        tmp = array[j];
                        array[j] = array[j+1];
                        array[j+1] = tmp;
    
                        isSorted = false;
                    }
                }
    
                if (isSorted){ 
                    break;
                }
            }
        }
        public static void main(String[] args){ 
            int[] array = new int[]{ 5,8,6,3,9,2,1,7};
            sort(array);
            System.out.println(Arrays.toString(array));
        }
    }

### 第二次优化，减少内层循环次数 ###

import java.util.Arrays;
    
    public class Bubble03 { 
        public static void sort(int array[]){ 
            // 减少内层循环的次数
            int lastExchangedIndex = 0;
            int sortBorder = array.length - 1;
            for(int i=0;i<array.length;i++){ 
                // 减少外层循环的次数
                boolean isSorted = true;
                for(int j=0;j<sortBorder;j++){ 
                    int tmp = 0;
                    if (array[j] > array[j+1]){ 
                        tmp = array[j];
                        array[j] = array[j+1];
                        array[j+1] = tmp;
    
                        isSorted = false;
    
                        lastExchangedIndex = j;
                    }
                }
    
                sortBorder = lastExchangedIndex;
    
                if (isSorted){ 
                    break;
                }
            }
        }
        public static void main(String[] args){ 
            int[] array = new int[]{ 5,8,6,3,9,2,1,7};
            sort(array);
            System.out.println(Arrays.toString(array));
        }
    }

## javascript实现 ##

### 基础冒泡 ###

### 第一次优化，减少外层循环次数 ###

### 第二次优化，减少内层循环次数 ###