数据结构教程--李春葆版（总结）之排序-交换排序

布满荆棘的人生 2022-01-05 11:19 151阅读 0赞

**本文的主要内容来自数据结构教程--李春葆版，由“你是木头人”博主进行总结。**

### 交换排序 ###

**性质**：两两比较待排序元素的关键字，发现两个元素的次序相反时即进行交换，直到没有反序的元素为止。

### 冒泡排序 ###

//冒泡排序-稳定
    typedef struct
    {
    int key;
    }RecType;
    void BubbleSort(RecType R[],int n)
    {
             int i,j;
             RecType tmp;
             for(i=0;i<n-1;i++)
             {
                       for(j=n-1;j>i;j--)
                       {
                                if(R[j].key<R[j-1].key)
                                {
                                         tmp=R[j];
                                         R[j]=R[j-1];
                                         R[j-1]=tmp;
                                }
                       }
             }
    }

**冒泡排序过程图解：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW4xMDgzMzc2NTEx_size_16_color_FFFFFF_t_70][]

### 改进冒泡排序 ###

//改进冒泡排序-稳定
    typedef struct
    {
    int key;
    }RecType;
    void BubbleSort1(RecType R[],int n)
    {
    
             int i,j;
             bool exchange;
             RecType tmp;
             for(i=0;i<n-1;i++)
             {
                       for(j=n-1;j>i;j--)
                       {
                                exchange=false;
                                if(R[j].key<R[j-1].key)
                                {
                                         tmp=R[j];
                                         R[j]=R[j-1];
                                         R[j-1]=tmp;
                                         exchange=true;
                                }
                       }
                       if(!exchange)
                                         return;
             }
    }

**改进冒泡排序过程的图解：**![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW4xMDgzMzc2NTEx_size_16_color_FFFFFF_t_70 1][]

### 快速排序 ###

//快速排序-不稳定
    typedef struct
    {
    int key;
    }RecType;
    void QuickSort(RecType R[],int s,int t)
    {
    	int i=s,j=t;
    	RecType tmp;
    		if(s<t)
    	{
    		tmp=R[s];
    		while(j>i &&R[j].key>=tmp.key)
    			j--;
    		R[i]=R[j];
    		while(i<j&&R[i].key<=tmp.key)
    			i++;
    		R[j]=R[i];
    	}
    	R[i]=tmp;
    	QuickSort(R,s,i-1);//对左区间递归排序
    	QuickSort(R,i+1,t);//对右区间递归排序
    }

继续更新中。。。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW4xMDgzMzc2NTEx_size_16_color_FFFFFF_t_70]: /images/20211229/bd1d0f570f3d4f3dbe139eb2e059ce41.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW4xMDgzMzc2NTEx_size_16_color_FFFFFF_t_70 1]: /images/20211229/2f6db21ca2674bb89bf173c157ab6a47.png