数据结构与算法排序

港控/mmm° 2022-05-19 13:14 191阅读 0赞

### **数据结构与算法 排序** ###

**一、简述**

**       记-排序方法。冒泡排序、选择排序、快速排序、直接插入排序。**

**        排序方法优劣比较：**

**       **![70][]

注：排序稳定性：如果待排序的表中存在多个关键字相同的元素，经过排序后这些相同关键字的元素的相对次序保持不变，则称这种排序方法是稳定的。反之有可能发生变化的则为不稳定。（例如按年龄排序，A与B的年龄相同，排序前A在B的前面，排序后A一定在B的前面，如此称为稳定。）

**二、冒泡排序**

**       例如有N个数需要排序，第1趟比较N个数，相邻的两个数进行比较，较大值者后移(从小到大排序)，一趟比较结束后，这一趟比较的数当中的最大值成为最后一个数；第2趟比较剩下的N-1个数，其中的最大值成为第N-1个数；以此类推，一共比较N-1趟。**

![70 1][]

**       测试代码：**

#include <stdio.h>
    
    #define LENGTH	10	//元素个数
    
    void bubble_sort(int arr[], int len)
    {
    	int i, j, tmp, print; 
     	for (i = 0; i < len; i++)			/*变量i代表比较的趟数，每趟将未排序中的最大值放到最后*/
        {
        	for (j = 0; j < len-1-i; j++)	/*变量j代表每趟两两比较的次数*/
        	{
        		if (arr[j] > arr[j+1])        /*比较相邻的两值，大者后移*/   
    		    {
    		        tmp = arr[j];				/*利用中间变量实现两个值互换*/
    		        arr[j] = arr[j+1];
    		        arr[j+1] = tmp;
    		    }
    		} 
    		
    	 	printf("第%d趟比较后：", i);
    	    for (print = 0; print < LENGTH; print++)
    	    {
    	    	printf("%d ", arr[print]);            /*将排序后的顺序输出*/
    		} 
    		printf("\n"); 
    		 
    	} 
    } 
    
    int main()
    {
        int i, arr[10];					/*定义变量及数组*/
        printf("请输入10个数:\n");
        for (i = 0; i < 10; i++)
        {
        	scanf("%d", &arr[i]);				/*从键盘中输入10个数*/
    	}
       
        bubble_sort(arr, LENGTH);
    	 
        printf("排序后的顺序是:\n");
        for (i = 0; i < 10; i++)
        {
        	printf("%d ", arr[i]);            /*将排序后的顺序输出*/
    	} 
    	printf("\n");
    	return 0;
    }

**       运行结果：**

**        **![70 2][]

改进：有时候比较了前几次就排好序了(某一趟比较中没有发生交换，即没有反序，说明已经是顺序的)，就不用继续比较，以节约资源。

测试代码：

#include <stdio.h>
    
    #define LENGTH	10	//元素个数
    
    void bubble_sort(int arr[], int len)
    {
    	int i, j, tmp, print,is_exchange; 
     	for (i = 0; i < len; i++)			/*变量i代表比较的趟数，每趟将未排序中的最大值放到最后*/
        {
        	is_exchange = 0; 
        	for (j = 0; j < len-1-i; j++)	/*变量j代表每趟两两比较的次数*/
        	{
        		if (arr[j] > arr[j+1])        /*比较相邻的两值，大者后移*/   
    		    {
    		        tmp = arr[j];				/*利用中间变量实现两个值互换*/
    		        arr[j] = arr[j+1];
    		        arr[j+1] = tmp;
    		        is_exchange = 1; //标志为发生交换 
    		    }
    		} 
    		
    	 	printf("第%d趟比较后：", i);
    	    for (print = 0; print < LENGTH; print++)
    	    {
    	    	printf("%d ", arr[print]);            /*将排序后的顺序输出*/
    		} 
    		printf("\n"); 
    		
    		if(is_exchange == 0)//没有发生交换，说明已经是排好序的 
    		{
    			return; 
    		} 
    		 
    	} 
    } 
    
    int main()
    {
        int i, arr[10];					/*定义变量及数组*/
        printf("请输入10个数:\n");
        for (i = 0; i < 10; i++)
        {
        	scanf("%d", &arr[i]);				/*从键盘中输入10个数*/
    	}
       
        bubble_sort(arr, LENGTH);
    	 
        printf("排序后的顺序是:\n");
        for (i = 0; i < 10; i++)
        {
        	printf("%d ", arr[i]);            /*将排序后的顺序输出*/
    	} 
    	printf("\n");
    	return 0;
    }

运行结果：

![70 3][]

**三、直接选择排序**

例如有N个数，第1趟从待排序的N数当中选出最小值最为第1个数，第2趟从剩下未排序的N-1个数中选出最小值最为第2个数，以此类推，直到全部将N个数排序。

![70 4][]

测试代码：

#include <stdio.h>
    #define LENGTH	10	//定义数组元素个数 
    
    void select_sort(int arr[], int len)//选择排序 
    {
    	int i, j, k, tmp, print;
    	for (i = 0; i < len-1; i++)			/*变量i代表比较的趟数，每趟将未排序中的最小值放到前面*/
        {
        	k = i;//k用来记住每趟中最小值元素的数组索引，比较完一趟再进行交换 
        	for (j = i+1; j < len; j++)	/*变量j代表每趟两两比较的次数*/
        	{
        		if (arr[j] < arr[k])    /*大者后移*/   
    		    {
    		    	k = j; 
    		    }
    		} 
    		
    		if (k != i)   /*将无序区的最小值放到有序区*/   
    	    {
    	        tmp = arr[i];				/*利用中间变量实现两个值互换*/
    	        arr[i] = arr[k];
    	        arr[k] = tmp;
    	    }
    	    
    	    printf("第%d趟比较后：", i);
    	    for (print = 0; print < LENGTH; print++)
    	    {
    	    	printf("%d ", arr[print]);            /*将排序后的顺序输出*/
    		} 
    		printf("\n"); 
    	} 
    }
    
    int main()
    {
        int i, arr[LENGTH];   
        printf("请输入%d个数:\n", LENGTH);
        for (i = 0; i < LENGTH; i++)
        {
        	scanf("%d", &arr[i]);				/*从键盘中输入LENGTH个数*/
    	}
    	
    	select_sort(arr, LENGTH); 
        
        printf("排序后的顺序是:\n");
        for (i = 0; i < LENGTH; i++)
        {
        	printf("%d ", arr[i]);            /*将排序后的顺序输出*/
    	} 
    	
    	printf("\n");
    	return 0;
    }

运行结果：

![70 5][]

四、快速排序

快速排序是由冒泡排序改进而来的。

一趟快速排序的划分过程是采用从两头向中间扫描，同时交换与基准元素逆序的元素。具体做法是：设两个标识i和j，它们初始化分别指向无序区中的第一个元素和最后一个元素。假设无序区中的元素为arr\[begin\],arr\[begin+1\],...,arr\[end\]。则i的初始值为begin，j的初始值为end；首先将arr\[begin\]的值赋给中间变量tmp作为基准，然后令j自end起向左(向begin方向)扫描，直至arr\[j\]<tmp,然后将arr\[j\]的值赋给arr\[i\]。然后令i自i+1向右(向end方向)扫描，直至arr\[i\]>tmp,然后将arr\[i\]的值赋给arr\[j\]。然后令j自j-1向右..;然后令i自i+1向右。。。这样重复操作直到i==j，此时arr\[begin\],arr\[begin+1\],...,arr\[i-1\]这些关键字都小于tmp，而所有的.arr\[i+1\],...,arr\[end\]的关键字都大于tmp，此时可以将tmp中的元素赋给arr\[i\]。

![70 6][]

![70 7][]

![70 8][]

测试代码

#include <stdio.h>
    
    static int index = 0;
    
    void Print(int arr[],int len)
    {
    	int i;
    	for(i=0;i<len;++i)
    	{
    		printf("%d ",arr[i]);
    	}
    	printf("\n");
    }
    
    void quick_sort(int arr[],int begin,int end)//将arr[begin]...arr[end]进行快速排序 
    {
    	int i = begin,j = end;
    	int tmp;
    	if(begin<end)
    	{
    		tmp = arr[begin];//取arr[begin]作为基准 
    		while(i!=j)//从两端向中间扫描，直至i==j 
    		{
    			while(j>i && arr[j] >= tmp)//从右向左扫描，找到第一个小于tmp的arr[j] 
    			{
    				--j;
    			}
    			
    			arr[i] = arr[j];//找到第一个小于tmp的arr[j]，将arr[j]赋给arr[i] 
    			
    			while(i<j && arr[i] <= tmp)//从左向右扫描，找到第一个大于tmp的arr[i]
    			{
    				++i;
    			}
    			arr[j] = arr[i];//找到第一个大于tmp的arr[i]，将arr[i]赋给arr[j] 
    		}
    		
    		arr[i] = tmp;//arr[i]归位 
    		printf("第%d趟：", index++);
    		Print(arr, 10);//打印当前排序后的元素 
    		
    		quick_sort(arr,begin,i-1);//对左区间进行递归快速排序 
    		quick_sort(arr,i+1,end);//对右区间进行递归快速排序
    	}
    }
    
    int main(int argc,char* argv[])
    {
    	int arr[] = {6, 8, 7, 9, 0, 1, 3, 2, 4, 5};
    	printf("before sort:");
    	Print(arr, sizeof(arr)/sizeof(arr[0]));
    	quick_sort(arr,0,sizeof(arr)/sizeof(arr[0] - 1));
    	printf("after  sort:");
    	Print(arr, sizeof(arr)/sizeof(arr[0]));
    	return 0;
    }

运行结果：

![70 9][]

五、直接插入排序 （稳定）

基本思想：把n个待排序的元素看为有序区和无序区，开始时有序区中只包含1个元素，无序区中包含有n-1个元素，排序过程中每次从无序区中取出第一个元素，将它插入到有序区中的适当位置；直到将无序区的元素都取完，排序完成。

图例：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmZlaWJ1eWk_size_16_color_FFFFFF_t_70][]

测试代码：

#include <stdio.h>
    
    void print_arr(int arr[], int len)//打印数组arr,len为数组的个数 
    {
    	int i;
    	printf("arr= ");
    	for(i=0; i<len; i++)
    	{
    		printf("%-3d ", arr[i]);
    	}
    	printf("\n");
    } 
    
    //直接插入排序，arr为待排序的数组，len为数组的长度 
    void straight_insertion_sort(int arr[], int len)
    {
    	//进行从小到大排序 
    	int i,j,save;
        for(i=1;i<len;i++)//第一个元素作为有序区第一个元素，从第二个元素开始，逐个插入有序区 
        {
            if(arr[i]<arr[i-1])//当前要插入的元素比前面的元素要小，前面的元素往后移，腾挪出一个位置，放置当前要插入的数 
            {
                save = arr[i];//因为要进行移位，会进行覆盖，所以事先保存待插入的元素值 
                for(j=i-1;j>=0 && arr[j]>save;j--)//只要比 待插入的元素值 大，都要往后移位 
                {
                    arr[j+1] = arr[j];
                }
                arr[j+1] = save;//移位结束，腾出的位置就是 放置待排序的元素 的合适位置 
            }
            //打印当前数组的元素 
            printf("第%2d趟排序,", i);
    		print_arr(arr, len);
    		printf("\n"); 
        }
    }
    
    int main(int argc, char *argv[])
    {
    	int arr[] = {118,76,98,57,67,105,43,22,35,82,1};//待排序的数组 
        int len = sizeof(arr)/sizeof(arr[0]);//求数组元素个数
        printf("排序前:    ");
    	print_arr(arr, len);//打印数组 
    	printf("\n");
    	straight_insertion_sort(arr, len);//进行直接插入排序
    	 
    	return 0;
    }

运行结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmZlaWJ1eWk_size_16_color_FFFFFF_t_70 1][]

[70]: /images/20220519/42fe0294eb8a47aaba243db9b46b90a3.png
[70 1]: /images/20220519/064882b9e5ac4374863acfedc49087f1.png
[70 2]: /images/20220519/6ca268524f92483fb129f3c98b141aa1.png
[70 3]: /images/20220519/1fc4b62d34e54fd88447033598d2ffb2.png
[70 4]: /images/20220519/882f0a0bf23f4bd992783beb6d382b11.png
[70 5]: /images/20220519/33884b46d2e040e39cb78556558bf0fd.png
[70 6]: /images/20220519/fcb00562246d48b3a17e42c0aebbee10.png
[70 7]: /images/20220519/daf1c0eea07f47a988ac33f2805b6a04.png
[70 8]: /images/20220519/e5479303d3554c5dafcbc60118afa74f.png
[70 9]: /images/20220519/afaca6391f1f4c2781c79ae66e666b81.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmZlaWJ1eWk_size_16_color_FFFFFF_t_70]: /images/20220519/421b1507d4574a4998613503ed1383b8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmZlaWJ1eWk_size_16_color_FFFFFF_t_70 1]: /images/20220519/fb6a68d3a767496aac94c48e2db7a986.png