排序算法汇总

今天药忘吃喽~ 2022-08-09 00:42 187阅读 0赞

排序是计算机数据处理中很重要的也很常见的运算，排序操作在处理过程中会占用很多时间，为提高计算机运行效率，人们提出了不断改进各种各样的计算机算法。

【算法汇总】

按照待排序数据的存放位置可以将排序分为内部存储（内存）和外部存储（外存）两大类：

![20150928174014739][]

稳定性和算法的时间复杂度是评判算法优劣的两个依据：

稳定性：相同键值的两个记录在排序前后相对位置的变化情况，如果位置改变为不稳定，反之稳定。

排序算法的时间复杂度可以从键值的比较次数和记录的移动次数两个方面进行分析 ：

![SouthEast][]

【类C语言代码】

1. 排序算法要把待排序的信息用存储结构代码储存起来：

typedef struct      //结构体数据类型可以放不同数据类型的数据
    {
            int key;   //价值项--排序依据
            ItemType Otheritem;//其他内容项目
    }RecordType
    typedef RecordType List[n+1];//n序列中带排序记录的总数，<span style="font-size:18px;"> list变量第0个记录用于暂存某个记录值（“岗哨”）或者搁置不用</span>

2. 直接插入算法：

![SouthEast 1][]

Void StraightInsertSort(List R,int n)
    {
    	Int I,j
    	For(i=2;i<=n;i++)   //从第2个记录起进行插入
    {
    	R[0]=R[i];     //第i个记录复制为岗哨
    j=i-1;     
    while(R[0].key<R[j].key)   //与岗哨比较，键值不大于岗哨键值
    {
    	R[j+1]=R[j];
    	j--;
    }
    R[j+1]=R[0];
    }
    }

3. 冒泡排序

![SouthEast 2][]

Void BubbleSort(List R,int n)
    {
    	Int I,j,temp,endsort;
    	For(i=1;j<=n-1;i++)
    	{
    		Ensort=0;
    		For(j=1;j<=n-i-1;j++)
    		{
    			If(R[j].key>R[j+1].key){
                            Temp=R[j];
                            R[j]=R[j+1];R[j+1]=temp;
                            Endsort=1;
                            }
                     }
                    If(ensort==0);break;
           }
    }

4. 快速排序

![SouthEast 3][]

完成一轮交换：

Int QuickPartition(List R,int low,int high)
    {
    	X=R(low);
       While(low<high)
    {
         While((low<high)&&(R[high].key>=x.key))  high--;
         R[low]=R[high];
         While((low<high)&&(R[high].key<=x.key))) low++;
         R[high]=R[low];
    }
       R[low]=x;
       Return low;
    }

利用迭代器完成所有交换：

Void QuickSort(list R,int low,int high)
    {
       If(low<high)
       {
          Temp=QuickPartition(R,low,high); //分成两拨再进行排序
          QuickSort(R,low,temp-1);
          QuickSort(R,temp+1,high);
       }
    }

【总结】

在这些例题中，相对困难的是对算法的理性认识抽象为代码的过程：首先我们要理解待排序数据的内部组成部分，然后判定数组是否需要定义最大存储量，数组的下标从哪里开始存放数值。

[20150928174014739]: /images/20220731/eb0a4e75cfb64cb68037204da495e846.png
[SouthEast]: /images/20220731/d36104457d004d5f8005b53dea5d17f8.png
[SouthEast 1]: /images/20220731/d7aaf4947e3f4b80995d46205cf4eb05.png
[SouthEast 2]: /images/20220731/8561d3faa3de46e8b6145d892a1088c8.png
[SouthEast 3]: /images/20220731/db8677040a034033a946364577292c27.png