排序---冒泡排序、选择排序、插入排序实现和性能分析

傷城~ 2023-06-18 06:52 138阅读 0赞

### 文章目录 ###

*   *  冒泡排序
     *   *   *  性能分析
     *  选择排序
     *   *   *  性能分析
     *  插入排序
     *   *   *  性能分析

## 冒泡排序 ##

public class BubbleSort { 
        public static void main(String[] args) { 
            int[] arr = new int[10];
            Random random = new Random();
            for(int i = 0; i < 10; i++) { 
                arr[i] = random.nextInt(10);
            }
            Arrays.stream(arr).forEach(System.out::print);
            bubbleSort(arr);
            System.out.println("");
            Arrays.stream(arr).forEach(System.out::print);
        }
        
        public static void bubbleSort(int[] arr) { 
            int length = arr.length;
            int temp;
            
            for(int i = 0; i < length - 1; i++) { 
                boolean tag = true;
                for(int j = 0; j < length - i - 1; j++) { 
                    if(arr[j] > arr[j + 1]) { 
                        temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                        tag = false;
                    }
                }
                if(tag) { 
                    break;
                }
            }
        }
    }

#### 性能分析 ####

1.  **空间复杂度为O(1)**，即原地排序算法。
2.  为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是**稳定的排序算法**。
3.  假设待排序的数组已经有序，则只需要一次冒泡操作就结束了，因此**最好情况时间复杂度为O(n)**；  
    假设待排序的数组为倒序，则需要n次冒泡操作，第i次需要进行n-i-1次比较操作，因此**最坏情况时间复杂度为O(n^2)**；  
    在分析平均时间复杂度之前，需要知道“有序度”和“逆序度”这两个概念，这里不做介绍。对于一个完全有序的数组，有序度为n\*(n-1)/2，对于一个逆序的数组，有序度为0。冒泡排序的每一次比较和交换结束后，数组的有序度就会+1。因此，假设对包含n个元素的数组排序，最好情况下，n个元素有序，有序度为n\*(n-1)/2，不需要交换操作，最坏情况下，n个元素逆序，有序度为0，需要做n\*(n-1)/2次交换操作。平均时间复杂度的计算可以取中间值n\*(n-1)/4，即进行n\*(n-1)/4次比较操作，所以**平均情况下的时间复杂度就是O(n^2)。**

## 选择排序 ##

public class SelectSort { 
        public static void main(String[] args) { 
            int[] arr = new int[10];
            Random random = new Random();
            for(int i = 0; i < 10; i++) { 
                arr[i] = random.nextInt(10);
            }
            Arrays.stream(arr).forEach(System.out::print);
            selectSort(arr);
            System.out.println("");
            Arrays.stream(arr).forEach(System.out::print);
        }
    
        public static void selectSort(int[] arr) { 
            int length = arr.length;
            int min;
            int temp;
    
            for(int i = 0; i < length - 1; i++) { 
                min = i;
                for(int j = i + 1; j < length; j++) { 
                    if(arr[j] < arr[min]) { 
                        min = j;
                    }
                }
    
                if(min != i) { 
                    temp = arr[i];
                    arr[i] = arr[min];
                    arr[min] = temp;
                }
            }
        }
    }

#### 性能分析 ####

1.  **空间复杂度为O(1)**。
2.  **不稳定的**，如5，8，5，2，9这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素2，与第一个5交换位置，那第一个5和中间的5顺序就变了，所以就不稳定了。
3.  **最好情况时间复杂度、最坏情况和平均情况时间复杂度都为O(n^2)。**

## 插入排序 ##

public class InsertSort { 
        public static void main(String[] args) { 
            int[] arr = new int[10];
            Random random = new Random();
            for(int i = 0; i < 10; i++) { 
                arr[i] = random.nextInt(10);
            }
            Arrays.stream(arr).forEach(System.out::print);
            insertSort(arr);
            System.out.println("");
            Arrays.stream(arr).forEach(System.out::print);
        }
    
        public static void insertSort(int[] arr) { 
            int length = arr.length;
            int index;
            int item;
    
            for(int i = 1; i < length; i++) { 
                index = i - 1;
                item = arr[i]; //待插入的元素
    
                while(index >= 0 && item < arr[index]) { 
                    arr[index + 1] = arr[index];
                    index--;
                }
    
                arr[index + 1] = item;
            }
        }
    }

#### 性能分析 ####

1.  **空间复杂度为O(1)**。
2.  在插入排序中，对于值相同的元素，可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是**稳定的**排序算法。
3.  假设待排序的n个元素有序，则每次将第i个元素往前i-1个已经有序的元素中插入时，一次比较即可找到插入的位置，因此**最好情况时间复杂度为O(n)**；  
    假设待排序的n个元素逆序，则每次将第i个元素往前i-1个已经有序的元素中插入时，每次都需要遍历完前i-1个元素才能找到插入位置，因此**最坏情况时间复杂度为O(n^2)**；  
    往有序数组中插入一个元素的平均时间复杂度为O(n)，所以，对于插入排序操作，每次将第i个元素插入到前i-1个元素中时，找插入的位置的时间复杂度为O(i-1)，所以**平均时间复杂度为O(n^2)**。