【数据结构】7大基于比较的排序（插入排序、希尔排序、选择排序、堆排序）

拼搏现实的明天。 2024-04-18 13:31 21阅读 0赞

>  *  排序：所谓排序，就是把一串有记录的数组，按照降序或者非降序进行排列（一般默认非降序）
>  *  稳定性：能保护排序过程中相等的数据相对顺序不变
>  *  稳定的排序：具备稳定性

# 1.插入排序（直接插入排序） #

**基本定义：**直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一 个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

**具体过程：**利用减治算法

每次从无序区间中选择第一个数，插入到有序的区间中的合适位置，一共需要进行size-1次（size次也可以）;

确定好有序区间和无序区间的具体范围；

**插入过程：**每次把无序区间的第一个数，在有序区间中遍历（从后往前遍历）  
1）找到合适的位置

2）搬移原有数据，为该数据腾出位置

代码如下：

//插入排序
        public static void insertSort(int [] array){
            for(int i=0;i<array.length-1;i++){
                int key=array[i+1];
                int j;
                for(j=i;j>=0&&key<array[j];j--){
                    array[j+1]=array[j];
                }
                array[j+1]=key;
            }
        }

> 时间复杂度：
> 
> 最好：O(n)（完全有序） 平均：O(n^2) 最坏：O(n^2) (完全逆序)

插入排序，越接近有序，执行时间效率越高

> 空间复杂度：O(1)

稳定性：稳定

# 2.希尔排序 #

**基本定义：**希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数grep，把待排序文件中所有记录分成grep个 组，所有距离为个grep的倍数记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工 作。当到达=1时，所有记录在统一组内排好序。它是一种特殊的插入排序。

分组进行插排

gap(为分的组数)

**gap=gap/3+1;或者gap=gap/2;**

//希尔排序
        public static void shellSort(int [] array){
           int gap=array.length;
           while(true){
               gap=gap/3+1;
               insertSortWithGap(array,gap);
               if(gap==1){
                   return;
               }
           }
        }
    
        public static void insertSortWithGap(int [] array,int gap){
            for(int i=0;i<array.length-gap;i++){
                int key=array[i+gap];
                int j;
                for(j=i;j>=0&&key<array[j];j-=gap){
                    array[j+gap]=array[j];
                }
                array[j+gap]=key;
            }
        }

> 时间复杂度：
> 
> 最好：O(n） 平均：O(n^1.3-1.4) 最坏：O(n^2)
> 
> 空间复杂度：O(1)
> 
> 稳定性：不稳定（相等的两个数被分到了不同组里，无法保证）

# 3.选择排序 #

减治算法

## 基本思想： ##

**思想：**每次遍历无序区间（直接遍历或者利用堆），找到无序区间的最大的数，把最大的数放到无序区间的最后边，一直选择n-1(n)数之后，数据完全有序

**直接选择排序:**  
在元素集合array\[i\]--array\[n-1\]中选择关键码最大(小)的数据元素 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换 在剩余的array\[i\]--array\[n-2\]（array\[i+1\]--array\[n-1\]）集合中，重复上述步骤，直到集合剩余1个元素

//选择排序
        public static void selectSort(int [] array){
            for(int i=0;i<array.length-1;i++){
                int max=0;
                for(int j=0;j<array.length-i;j++){
                    if(array[j]>=array[max]){
                        max=j;
                    }
                }
                swap(array,max,array.length-i-1);
            }
        }
        private static void swap(int [] array,int i,int j){
            int count=array[i];
            array[i]=array[j];
            array[j]=count;
        }

> 时间复杂度：O(n^2) 数据不敏感
> 
> 空间复杂度：O（1）
> 
> 稳定性：不稳定

# 4.堆排序 #

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是 通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

**思想：**首先要先建一个大堆，这时第一个元素就为堆里面最大的元素了，然后进行循环，把堆顶的元素和堆后面无序区间的最后一个元素交换，无序区间的范围为：\[0,array.lenght-i),交换之后无序区间的范围为\[0.array.lenght-i-1),无序区间的长度为array.length-i-1;然后在调整堆，继续循环

//堆排序,建大堆
        public static void heapSort(int [] array){
            createHeap(array,array.length);
            for(int i=0;i<array.length-1;i++){
                //无序区间：[0,array.length-i)
                swap(array,0,array.length-i-1);
                //无序区间：[0,array.length-i-1)
                //无序区间的长度： array.length-i-1
                heapifyMax(array,array.length-i-1,0);
            }
        }
    
        //向下调整大堆
        public  static void heapifyMax(int[] array, int size, int index) {
            while(true){
                int left=index*2+1;
                if(left>=size){
                    return;
                }
                int max=left;
                if(left+1<size&&array[left+1]>=array[left]){
                    max=left+1;
                }
                if(array[max]<=array[index]){
                    return;
                }
                swap(array,index,max);
                index=max;
            }
        }
        //创建一个大堆
        public static void createHeap(int[] array, int size) {
            int parent=(size-2)/2;
            for(int i=parent;i>=0;i--){
                heapifyMax(array,array.length,i);
            }
        }