排序算法总结

今天药忘吃喽~ 2021-12-13 15:01 264阅读 0赞

### 1.冒泡排序 ###

> 　冒泡算法思想：  
> 　　1.从左到右依次比较相邻的元素。如果第一个比第二个大，就交换他们两个,等全部执行完,最后的元素就是最大的数,这            时候完成了第一波冒泡。  
> 　　2.继续从左到右比较相邻的元素,步骤和第一步相同,但是最后一个元素不参与比较,以此类推

> 　  冒泡排序是由两个for循环构成，第一个for循环表示总共需要多少轮比较，第二个for循环表示每轮参与比较的元素下标  
> 　  冒泡排序性能分析：  
>     　　假设所有的数组元素个数为N，则第一轮需要比较N-1次，第二轮N-2次,以此类推,总需排序次数的公式为：  
>     　　（N-1）+（N-2）+...+1 = N\*（N-1）/2  
>     　　当 N 的值很大时,忽略幂数较小的加减法,比较次数约为N2/2次。  
>     　　假设数据是随机的，那么每次比较可能要交换位置，可能不会交换，假设概率为50%，那么交换次数为 N2/4。但如             果初始数据是逆序的，那么每次比较都要交换位置。  
>     　　交换和比较次数都和N2 成正比。由于常数不算大 O 表示法中，忽略 2 和 4，那么冒泡排序运行都需要 O(N2) 时间               级别。

public static String deploy(int[] numbers){
            StringBuffer sb = new StringBuffer();
            Ints.asList(numbers).forEach(i -> sb.append(i +","));
            return sb.toString();
        }
    
    
        static int[] numbers = {5,3,9,4,7,6,1,3,4,7,8,7};
    
        // 经典冒泡排序
        public static void main(String[] args) {
    
            // 增加saveLength,是末尾已经排好序的数字不再参与排序
            int saveLength = 1;
    
            int count = 0;
    
            for (int i = 1; i < numbers.length; i++) {
                // 增加这个判断,是还未参与排序的数字,没必要再进行排序了,
                // 因为在进行该数字排序时,其整个数字顺序已经是排好的了
                boolean jduge = true;
    
                for (int j = 0; j < numbers.length-saveLength; j++) {
                    if (numbers[j] > numbers[j + 1]) {
                        int tmp = numbers[j];
                        numbers[j] = numbers[j + 1];
                        numbers[j + 1] = tmp;
                        jduge = false;
                    }
                    System.out.println(++count + " : "+deploy(numbers));
                }
    
                if (jduge){
                    break;
                }
                saveLength++;
            }
            System.out.println(deploy(numbers));
        }
    
    
        //末尾已经排好序的不再参与,仍可优化
        public static void main(String[] args) {
            int saveLength = 1;
            int count = 0;
            for (int i = 1; i < numbers.length; i++) {
    
                for (int j = 0; j < numbers.length-saveLength; j++) {
                    if (numbers[j] > numbers[j + 1]) {
                        int tmp = numbers[j];
                        numbers[j] = numbers[j + 1];
                        numbers[j + 1] = tmp;
                    }
                    System.out.println(++count + " : "+deploy(numbers));
                }
                saveLength++;
            }
            System.out.println(deploy(numbers));
        }
    
    
    
    
        //基本比较算法,拥有可优化空间
        public static void main(String[] args) {
            int count = 0;
            for (int i = 1; i < numbers.length; i++) {
                for (int j = 0; j < numbers.length-1; j++) {
    
                    if (numbers[j] > numbers[j + 1]) {
                        int tmp = numbers[j];
                        numbers[j] = numbers[j + 1];
                        numbers[j + 1] = tmp;
                    }
    
                    System.out.println(++count + " : "+deploy(numbers));
                }
            }
            System.out.println(deploy(numbers));
        }

### 2.选择排序 ###

> 选择排序思想：  
> 　　1.从待排序元素中，找到最小的元素  
> 　　2.如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换,此后第一个元素不再参与对比,以此类推

> 　选择排序次数：N\*（N-1）/2，和冒泡排序相同,但选择排序至多只进行了N次交换,而冒泡排序的交换次数是N2。  
>     当N值很大时,比较次数是主要的,所以和冒泡排序一样,用大O表示是O(N2)时间级别。但是选择排序交换的次数少，所以       选择排序比冒泡排序快

### 3.插入排序 ###

> 每一步将一个待排序的元素，插入到前面已经排好序的有序元素中去,直到所有元素排序完毕

> 　　插入排序总共参与比较次数为 1+2+3+...+N-1 = N\*（N-1）/2。  
> 　　当 N 的值很大时,忽略幂数较小的加减法,比较次数约为N2/2次,假设数据是随机的，那么每次比较可能要交换位置，可           能不会交换，假设概率为50%，那么交换次数为 N2/4  
> 　　复制的次数大致等于比较的次数，但是一次复制与一次交换的时间耗时不同，所以相对于随机数据，插入排序比冒泡           快一倍，比选择排序略快。  
> 　　但是如果要进行逆序排列，那么每次比较和移动都会进行，这时候并不会比冒泡排序快。