【排序】排序这样写才对Ⅰ –插入排序与选择排序

Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法……感兴趣就关注我吧！你定不会失望。

🌈个人主页：主页链接

🌈算法专栏：专栏链接

     我会一直往里填充内容哒！

🌈LeetCode专栏：专栏链接 

    目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目，也会当天做完发出

🌈代码仓库：Gitee链接

🌈点击关注=收获更多优质内容🌈

目录

0.排序的概念及常见的算法:

0.1排序的概念:

0.2常见的算法:

1.直接插入排序:

1.1直接插入排序代码实现:

2.希尔排序:

2.1希尔排序代码实现:

3.选择排序:

3.1单路选择代码实现:

3.2双路选择代码实现:

4.堆排序:

4.1堆排序代码实现:

完结撒花:

0.排序的概念及常见的算法:

0.1排序的概念:

————————————————————————————————————————–

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

————————————————————————————————————————–
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

————————————————————————————————————————–
内部排序：数据元素全部放在内存中的排序。

————————————————————————————————————————–
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序
————————————————————————————————————————–

总的来说就是:让一串的数据,按照使用者想要的顺序尽行展示.

0.2常见的算法:

常见的排序算法有这些.将会分成几个章节讲完,感兴趣的uu们可以关注下我的排序专栏,方便和后期观看.

这章重点讲前两种排序:插入排序与选择排序.

1.直接插入排序:

顾名思义,其的运行原理为:选出一个数,不断与其之前的数据比较.在排升序的前提下,若目标值比其前一个小,则继续往前比较.比到目标值比齐前一个大为止.其时间复杂度为O(N^2)

这个排序与我们之前玩过的抽牌很像,想想是不是这样. 那我们直接来写写代码看看.

1.1直接插入排序代码实现:

void insertsort(int *a,int n)
{
    for(int j=1;j<n;j++)
    {
        int tmp=a[j];
        int end=j-1;
        while(end>=0)
        {
            if(tmp<a[end])
            {
                a[end+1]=a[end];
                end--;
            }
            else break;
        }
        a[end+1]=tmp;
    }
}

 注意这里需要先将a[j]的值,也就是目标值存储起来,否则在end后移的过程中,会将a[j]覆盖

2.希尔排序:

希尔排序不是一种新的排序.其是在插入排序的基础上改进的一种排序.其时间复杂度不稳定,

一般为O(N^1.25)–O(1.6N^1.25)

其核心思想为:

先将待排序数组的间隔gap位进行插入排序.之后gap不断缩减.最后仍然是做插入排序,也可以将直接插入排序看作为gap为一的希尔排序,当gap<1时停止

(这里因为已经有序了,所以就没有展现出gap为一的情况)

我们拿插入排序的代码来看看:

        也就是j依然每次往前移一位.在直接插入排序中,end初始为j-1,end每次跳一位.

                                                    在这里初始值为j-gap且每次跳gap位.

需要注意gap的取值可以任意,但需要满足最后会变成1的情况.也就是直接插入排序,临位调整的情况.(一般取值为:len/2或者len/3+1)

2.1希尔排序代码实现:

void shellsort(int *a,int n)
{
    int gap=n/2;
    while(gap>=1)
    {
        for(int j=0;j<n;j++)
        {
            int tmp=a[j];
            int end=j-gap;
            while(end>=0)
            {
                if(tmp<a[end])
                {
                    a[end+gap]=a[end];
                    end-=gap;
                }
                else break;
            }
            a[end+gap]=tmp;
        }
        gap/=2;
    }
}

3.选择排序:

依然顾名思义,其就是选择出一个最大/最小的值放在其左边/右边,然后不断缩减区间 ,即可完成.其时间复杂度为:O(N^2),我们一般不使用他

 这里给出两种代码方案:

3.1单路选择代码实现:

选择最小的放在左边

void selectsort(int *a,int n)
{
    for(int i=0;i<n;i++)
    {
        int min=a[i];
        for(int j=i+1;j<n;j++)
        {
            if(a[j]<min)
            {
                swap(a[j],min);
            }
        }
        a[i]=min;
    }
}

3.2双路选择代码实现:

从两个方向选择最大最小,然后依次放在左右,并缩减区间.

这里有个问题,若发生最大的值在左边,第一次交换完会改变,max值指向的内容

 所以要进行一次判定,若max==left,则说明真正的max被换到了刚刚min的位置,此时我们需要让max=min

void selectsort(int *a,int n)
{   
    int left=0,right=n-1;
    while(left<=right)
    {
        int max=right,min=left;
        for(int i=left+1;i<right;i++){
            if(a[max]<a[i])
            {
                max=i;
            }
            else if(a[min]>a[i])min=i;
        }
        swap(a[min],a[left]);
        if(max==left)max=min;
        swap(a[max],a[right]);
        left++,right--;
    }
}

4.堆排序:

这里前面介绍过了,就不再赘述.uu可以看 这篇文章 其时间复杂度为O(N*logN)

4.1堆排序代码实现:

void heapSort(HDataType *a,int n)
{
	/*for (int i = 1; i < n; i++)
	{
		UpAdjust(a, i);
	}*/
	for (int i = (n - 1 - 1 / 2); i >= 0; i--)
	{
		DownAdjust(a, n,i);
	}
 
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[end], &a[0]);
		end--;
		DownAdjust(a, end,0);
		
	}
}	

完结撒花：

🌈本篇博客的内容【排序这样写才对Ⅰ –插入排序与选择排序】已经结束。

🌈若对你有些许帮助，可以点赞、关注、评论支持下博主，你的支持将是我前进路上最大的动力。

🌈若以上内容有任何问题，欢迎在评论区指出。若对以上内容有任何不解，都可私信评论询问。

🌈诸君，山顶见！