【数据结构】之七大排序（更新中）

朱雀 2023-10-07 11:16 32阅读 0赞

## 排序： ##

1、稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序。

2、非稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。

3、时间复杂度：一个算法执行所消耗的时间。

### **1：冒泡排序** ###

**说明：**  
冒泡的意思就是从水底往上面冒泡（我们把数组第一个元素看做水底），对于数组来说，是通过比较和换位，每次把最大（最小）的一个元素移动到顶上来，然后剩下的再次冒泡排序。  
**做法：（通俗易懂的说法）**  
从第一个元素开始，与相邻的后一个元素比较大小，若本身比较大则换位，把大的换到后面，一次循环比较完最后一个元素为止，然后再次重复循环，直到所有元素都按从小到大排序为止。  
**特点：**  
最好时间：O(n) 最坏时间O(n^2),  
平均时间O(n^2) 辅助存储空间O(1) 稳定性：稳定

//冒泡排序法，从小到大排序
    #include<stdio.h>
    void bubbleSort(int arr[],int length)
    {
        
    	int i,j,temp;
    	for(i=0;i<length-1;i++)//循环n-1轮
    	{
        
    			for(j=0;j<length-1-i;j++)
    			{
        //每轮把最大的1个放到了最后面
    					if(arr[j]>arr[j+i])
    					{
        
    					temp=arr[j];
    					arr[j]=arr[j + 1];
    					arr[j + 1]=temp;
    			    	}
    			}
    	}
    }
    int main()
    {
        
    	int length=10;
    	int arr[10]={
        2,6,3,5,4,7,9,8,1,10};
    	int i;
    	printf("\n排序前:");
    	for(i=0;i<length;i++)
    		{
        
    		printf(" %d ",arr[i]);
    		}
    	bubbleSort(arr,length);
    	printf("\n排序后:");
    	for(i=0;i<length;i++)
    		{
        
    		printf(" %d ",arr[i]);
    		}
    	return 0;
    }

### 2:选择排序 ###

**说明**（跟全部的数作比较）  
首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置(如果第一个元素就是最小元素那么它就和自己交换)。其次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。这种方法我们称之为选择排序。  
**特点：**  
最好时间：O(N^2) 最坏时间：O(N^2)  
平均时间:O(N^2) 辅助存储空间：O(1) 稳定性：不稳定

#include<stdio.h>
    //选择排序 从小到大排序
    #include<stdio.h>
    void selectsort(int arr[],int len)
    {
        
    int i,j,temp;
    for(i=0;i<len-1;i++)
    	{
        
    		 for(j=i+1;j<len;j++)
    		 {
        
    		 if(arr[i]>arr[j])
    		    {
        
    		 	temp=arr[i];
    		 	arr[i]=arr[j];
    		 	arr[j]=temp;
    			 }		
    		 }	
    	 } 
     }
    int main()
    {
        
    	int len=10;
    	int arr[10]={
        1,0,6,5,9,8,4,2,3,7};
    	printf("\n排序前:");
    	for(int i=0;i<len;i++)
    	{
        
    	printf(" %d ",arr[i]);		
    	}	
    	selectsort(arr,len);
    	printf("\n排序后:");
    	for(int i=0;i<len;i++)
    	{
        
    	printf(" %d ",arr[i]);		
    	}	
    	return 0;		
    }

### **3：快速排序：** ###

**说明：（如果还是不懂的话还准备了优质的文章讲解：**[不要问我快速排序][Link 1]）  
每次都把当前数据化为两部分，每次排序保证前面部分都小于后面部分，然后在对两部分分别快速排序。

那么怎么划分两部分呢，以从小到大排序为例，第一个数为基准，然后从尾到头找小于基准的数，从头到尾找大于基准的数，找到就换位。

则首尾相遇时，必然相遇点左侧的都小等于基准，右侧的都大于等于基准，然后把基准放到中间合适位置，则实现了右边全部大于左边。

//分割操作：方法一，单向调整
    #include<stdio.h> 
    int partion(int arr[], int left, int right)
    {
        
       int temp,K;//K存放主元
       int i,j;
       i = left;
       K = arr[right];
       for(j = left;j < right;j++)
       {
        
           if(arr[j] < K)
           {
          //交换值
               temp = arr[i];
               arr[i] = arr[j];
               arr[j] = temp;
               i++;
           }
       }
       arr[right] = arr[i];
       arr[i] = K;
       return i;//把主元的下标返回
    }
    //快速排序
    void QuickSort(int arr[], int left, int right)
    {
        
       int center;
       int i,j;
       int temp;
       if(left < right)
       {
        
          center = partion(arr,left,right);
          QuickSort(arr,left,center-1);//左半部分
          QuickSort(arr,center+1,right);//右半部分
       }
    }

**特点**：  
最好时间：O(NlogN) 最坏时间：O(N^2)  
平均时间:O(NlogN) 辅助存储空间：O(logN) 稳定性：不稳定

### 4：插入排序 ###

插入排序又分为直接插入排序和希尔排序  
**直接插入：**  
**说明：**（跟前面的数作比较）  
插入排序就是在一个有序的序列中，插入一个数，这个序列照样有序。  
第一个数默认有序，这个序列的第二个数和第一个比较，若是第二个比第一个小就交换位置，那么前两个就是有序的了。然后循环序列中的第三个数，第三个数首先和第二个比较，若是小于第二个，交换位置，大于在不换位置。再和第一个比较，若比第-个小，和第一个交换位置，若比第一个大，不变。一直这样循环下去，直至最后一个。  
**特点**：  
最好时间：O(N) 最坏时间：O(N^2)  
平均时间:O(N^2) 辅助存储空间：O(1) 稳定性：稳定

void insertSort(int arr[],len){
        
    		int j;
    		for(int i=1;i<len;i++){
        
    			int tmp=arr[i];
    			for(j=i;j>0&&tmp<a[j-1];j--){
        
    				arr[j]=arr[j-1];
    			}
    			arr[j]=tmp;
    		}
    	}

**希尔排序：**  
**说明：**  
设待排序对象序列有 n 个对象, 首先取一个整数 gap < n 作为间隔, 将全部对象分为 gap 个子序列, 所有距离为 gap 的对象放在同一个子序列中, 在每一个子序列中分别施行直接插入排序。然后缩小间隔 gap, 例如取 gap = gap/2，重复上述的子序列划分和排序工作。直到最后取 gap == 1, 将所有对象放在同一个序列中排序为止。  
希尔排序方法又称为缩小增量排序。  
**特点**：  
最好时间： 最坏时间：取决于增量序列  
平均时间:O(n1.3) 辅助存储空间：O(1) 稳定性：不稳定  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3_size_16_color_FFFFFF_t_70]

### 5：归并排序： ###

**说明：**  
归并排序是建立在二路归并和分治法的基础上的一个高效排序算法。  
等分分解:将有序序列不断地等分分裂，直到每个区间都只有一个数据为止.  
合并:将两个区间合并为一个有序的区间，一直合并知道只有一个区间为止.

**特征:**  
最好时间：O（NlogN） 最坏时间：O（NlogN）  
平均时间:O(NlogN) 辅助存储空间：O(N) 稳定性：稳定  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3_size_16_color_FFFFFF_t_70 1]

/将有序数组a[]和b[]合并到c[]中  
    void MemeryArray(int a[], int n, int b[], int m, int c[])  
    {
          
        int i, j, k;  
      
        i = j = k = 0;  
        while (i < n && j < m)  
        {
          
            if (a[i] < b[j])  
                c[k++] = a[i++];  
            else  
                c[k++] = b[j++];   
        }  
        while (i < n)  
            c[k++] = a[i++];  
      
        while (j < m)  
            c[k++] = b[j++];  
    }

### 6:堆排序 ###

**说明：**  
堆排序具有（大顶堆跟小顶堆）  
将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列。

堆：堆是具有特殊性质的二叉树

每个结点都大于其左右儿子的的二叉树叫大顶堆

每个结点都小于其左右儿子的二叉树叫做小顶堆  
**做法：**  
从最后一层开始移动元素，把一层上的最小（最大）的数与这一层的根做交换，每一次都用此做法做一遍则为一次排序。  
**特征：**  
最好时间：O（NlogN） 最坏时间：O（NlogN）  
平均时间:O(NlogN) 辅助存储空间：O(1) 稳定性：不稳定  
***例子：***  
**大顶堆：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3_size_16_color_FFFFFF_t_70 4]  
**小顶堆**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3_size_16_color_FFFFFF_t_70 5]

## 排序时间复杂度与稳定性表： ##

辅助存储空间即为：空间复杂度  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3_size_16_color_FFFFFF_t_70 6]

[Link 1]: https://mp.weixin.qq.com/s?__biz=Mzg2NzA4MTkxNQ==&mid=2247485191&idx=1&sn=45a43bd77495566db53b419ae82136f5&source=41#wechat_redirect
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200317195717457.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200317200259471.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200317201707645.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200317201721604.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200317201734737.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200317201806496.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200317182835911.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3,size_16,color_FFFFFF,t_70