实现插入、希尔、直接选择排序

落日映苍穹つ 2023-06-13 04:42 21阅读 0赞

\*\*1.\*\*插入排序  
核心：拿到当前元素，把当前元素插入到前方的有序顺序的合适位置  
\[0,bound) 已排序区间  
\[bound,size) 待排序区间  
时间复杂度 O(n^2) 空间复杂度 O(1) 稳定  
两个特点：1.如果序列很短，插入排序很高效  
2.如果序列很有序，那么排序也会很高效

//插入排序
        public static void insertSort(int[] array) {
        
            for (int bound = 1; bound < array.length; bound++){
        
                //bound 下标对应的元素就是待插入元素
                int tmp = array[bound];
                int cur = bound - 1;
                for(; cur >= 0; cur--) {
        
                    if(array[cur] < tmp){
        
                        array[cur + 1] = array[cur];
                    } else {
        
                        break;
                    }
                }
                array[cur + 1] = tmp;
            }
        }

**2.希尔排序**  
先把数组分成若干组，定义一个gap，假设gap  
例：9 5 2 7 3 8 6 1 10 13 -1 20  
第一步;gap = 3，将数列分成三组  
9 7 6 13  
5 3 1 -1  
2 8 10 20  
对每一组 比较 排序  
6 7 9 13  
\-1 1 3 5  
2 8 10 20  
得到新的数列：6 -1 2 7 1 8 9 3 10 13 5 20  
第二步：gap = 2 重复第一步，得：1 -1 2 3 5 7 6 8 9 13 10 20  
第三步：gap = 1,只剩一组，对这组进行插入排序

平均时间复杂度 O(n^1.3)  
最坏时间复杂度 O(n^2)  
空间复杂度 O(1)  
不稳定

//希尔排序
        public static void shellSort(int[] array) {
        
            int gap = array.length;
            while(gap > 1) {
        
                insertSortGap(array,gap);
                gap = gap/2;
            }
            insertSortGap(array,1);
        }
    
        private static void insertSortGap(int[] array,int gap) {
        
            for(int bound = 1; bound < array.length; bound++){
        
                int tmp = array[bound];
                int cur = bound - gap;
                for (; cur >= 0; cur -= gap) {
        
                    if(array[cur] > tmp) {
        
                        array[cur + gap] = array[cur];
                    } else {
        
                        break;
                    }
                }
                array[cur + 1] = tmp;
            }
        }

3.直接选择排序（打擂台法）  
时间复杂度 O(n^2)  
空间复杂度 O(1) 不稳定

//直接选择排序
        public static void seleceSort(int[] array) {
        
            for(int bound = 0; bound < array.length; bound++) {
        
                for(int cur = bound + 1; cur <array.length; cur++) {
        
                    if(array[cur] < array[bound]){
        
                        swap(array,cur,bound);
                    }
                }
            }
        }
        public static void swap(int[] array, int x, int y) {
        
            int tmp = array[x];
            array[x] =array[y];
            array[y] = tmp;
        }