C语言数据结构——交换排序

痛定思痛。 2023-10-06 18:01 102阅读 0赞

定义排序算法的数据元素的数据结构如下：

typedef struct
    {
        
    	KeyType key;
    }DataType;

## 一、冒泡排序 ##

> 算法思想：依次比较相邻的两个记录的关键字，若两个记录是反序的(即前一个记录的关键字大于后前一个记录的关键字)，则进行交换，直到没有反序的记录为止。  
> （1）首先将L->R\[0\]与L->R\[1\]的关键字进行比较，若为反序(L->R\[0\]的关键字大于L->R\[1\]的关键字)，则交换两个记录；然后比较L->R\[1\]与L->R\[2\]的关键字，依此类推，直到L->R\[n-2\]与L->R\[n-1\]的关键字比较后为止，称为一趟冒泡排序，L->R\[n-1\]为关键字最大的记录。  
> （2）然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作。  
> 一般地，第i趟冒泡排序是对L->R\[0 … n-i\]中的记录进行的，因此，若待排序的记录有n个，则要经过n-1趟冒泡排序才能使所有的记录有序。

### 冒泡排序算法的排序过程 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70]

### 冒泡排序算法 ###

Void BubbleSort(DataType a[],int n)
    {
        
    	int i, j, flag =1;
    	DataType temp;		
    	for(i = 1;i < n && flag == 1; i++)
    	{
         
    		//flag标记一趟冒泡如果没有发生交换，则已经排好序，提前结束循环
    	  	flag = 0;
    	  	for(j = 0;j < n  - i; j++)
    	 	{
        	
    			if(a[j].key>a[j+1].key)
    			{
        
    				flag = 1;
    				temp = a[j];
    				a[j] = a[j+1] ；
    				a[j+1] = temp;
    	  		}
    		}
    	}
    }

## 二、快速排序 ##

> 基本思想：  
> 从待排序列中任取一个元素 (例如取第一个) 作为中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表；  
> 然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个。此时便为有序序列了。

### 一趟快速排序方法 ###

从序列的两端交替扫描各个记录，先从右端扫描，将关键字小于基准关键字的记录依次放置到序列的前边；然后从左端扫描，将关键字大于基准关键字的记录从序列的最后端起，依次放置到序列的后边，直到扫描完所有的记录。  
设置指针low，high，初值为第1个和最后一个记录的位置。  
设两个变量i，j，初始时令i=low，j=high，以 R\[low\].key作为基准(将R\[low\]保存在temp中) 。  
① 从j所指位置向前搜索：将temp.key与R\[j\].key进行比较：  
若temp.key≤R\[j\].key ：令j=j-1，然后继续进行比较， 直到i=j或temp.key>R\[j\].key为止；  
若temp.key>R\[j\].key ：R\[j\]R\[i\]，腾空R\[j\]的位置， 且令i=i+1；  
② 从i所指位置起向后搜索：将temp.key与R\[i\].key进行比较：  
若temp.key≥R\[i\].key ：令i=i+1，然后继续进行比较， 直到i=j或temp.key<R\[i\].key为止；  
若temp.key<R\[i\].key ：R\[i\]R\[j\]，腾空R\[i\]的位置， 且令j=j-1；  
③ 重复①、②，直至i=j为止，i就是temp(基准)所应放置的位置。

### 快速排序算法一次快速排序过程 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70 1]

### 快速排序算法实现 ###

void QuickSort(DataType a[],int low, int high)
    {
        
    int i=low,j=high;
    DataType temp=a[low];	
    while(i<j)
    {
        
    	while(i < j && temp.key <= a[j].key) j--; //在数组的右端扫描
    	if(i < j)
    	{
        
    	 	a[i] = a[j];
    		i++;
    	}
    	while(i < j && a[i].key < temp.key) i++; //在数组的左端扫描
    	if(i < j)
    	{
        
    		a[j] = a[i];
    		j--;
    	}
    }
    a[i]=temp;
    if(low<i) QuickSort(a,low,i-1);
    if(i<high) QuickSort(a,j+1,high);
    }

### 快速排序算法各次快速排序过程 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210622150742799.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210622150935619.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210622151033131.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng==,size_16,color_FFFFFF,t_70