19插入排序

插入排序

一些概念

就地排序：使用恒定的额外空间，即给定数组

内部排序：待排序数据能一次性载入内存

外部排序：待排序数据不能一次性载入内存

”稳定“的排序：看相同的关键字在排序前后相对位置的变化

处理键值对的时候（一级排序与二级排序等等）

直接插入排序

将待排序数组分成两个序列，一个有序一个无序，依次选择后者插入前者

注：并不是两个数组，而是一个数组在就地排序

时间复杂度O(n)，最坏情况下是O(n^2)

8个数据以下使用

二分插入排序

顺序地将待排序的序列中各个元素按照关键字的大小，通过二分查找插入到序列中

就地排序

时间复杂度为O(n)，最坏情况是O(n^2)

#include<stdio.h>
#include<stdlib.h>

void BInsertSort(int a[], int size)
{
    int low,high,mid;
    for(int i=1;i<size;i++)
    {
        low=0;
        high=i-1;
        int temp=a[i];
        while(low<=high)		//找到插入的位置
        {
            mid=(low+high)/2;
            if(a[mid]>temp)
                high = mid-1;
            else
                low = mid+1;
		}
        for(int j=i;j<low;j--)	//从最后一个向前移动
        {
            a[j]=a[j-1];
        }
        a[low]=temp;			//插入(low就是插入的位置)
	}
}

2-路插入排序

在二分插入的基础上另外设置一个大小相同的数组，将无序表中第一个记录加入到d[0]中，从第二个数据开始和d[0]比较，如果大于，在右边（数组开头）进行插入排序，否则在左边（数组尾端）。

（数据存储形式：环形数组）

减少移动的次数

极端情况下退化成二分插入排序

希尔排序（缩小增量排序）

把待排序数组按照下标记录的一些增量进行分组，对于每组进行直接插入排序随着增量逐渐减少，每组包含的关键组逐渐增加，当增量减少到1时完成排序

增量可以自定义，例如：

gap=length/2 (增量 = 数组长度 / 2)

gap=gap/2

增量元素不互质的情况下，可能会有最坏情况出现

选取的增量不同，复杂度也不同，需要数学推导，最坏情况依然是O(n^2)，增量优化后为3/2*n

#include<stdio.h>
#include<stdlib.h>

void shellsort(int arr[], int n)
{
    int gap;		//步长
    int k;			//记录范围
    for(gap = n/2;gap>0;gap/=2)
    {
        //直接插入排序
        for(int i=0;i<gap;i++)
        {
            //每一次加上步长，按列排序
            for(int j=i+gap;j<n;j+=gap)
            {
                if(arr[j]<arr[j-gap])
                {
                    int temp = arr[j];
                    k = j-gap;
                    while(k>=0; && arr[k]>temp)
                    {
                        arr[k+gap] = arr[k];
                        k = k-gap;
                    }
                    arr[k+gap] = temp;
                }
            }
        }
    }
}

发布于 2024-11-10