数据结构笔记（排序-1）

柔情只为你懂 2023-06-22 04:20 4阅读 0赞

# 查找排序 #

## 排序 ##

### 前提 ###

函数头有一个统一规范的格式  
void X\_Sort ( ElementType A\[\] ,int N )  
X为排序算法的名称

\*N为正整数  
\*只讨论基于比较的排序  
\*只讨论内部排序（假设内存空间充分大，所有的数据都可以一次性导到内存空间）  
\*稳定性：任意两个相等的数据，排序前后的相对位置不发生改变

##### 没有一种排序是任何情况下都表现最好的。 #####

#### 冒泡排序 ####

void Bubble_Sort(ElementType A[] , int N)
    { 
    	for(P = N-1;P>=0;P--)
    	{ 
    		flag = 0;
    		for(i=0;i<P;i++)  /*一趟冒泡*/
    		{ 
    			if(A[i] > A[i+1])
    			{ 
    				Swap(A[i],A[i+1]);
    				flag = 1;  /*标识发生了交换*/
    			}
    		}
    		if(flag == 0) break;   /*全程无交换*/
    	}
    }

最好情况： 顺序T = O（N）  
最坏情况： 逆序T = O (N2)

#### 插入排序 ####

void Insertion_Sort( ElementType A[] , int N)
    { 
    	for( P=1; P<N; P++)
    	{ 
    		Tmp = A[P];   /*摸下一张牌*/
    		for(i=P;i>0&&A[i-1]>Tmp;i--)
    			A[i] = A[i-1];   /*移出空位*/
    		A[i] = Tmp;   /*新牌落位*/
    	}
    }

最好情况：顺序T = O(N)  
最坏情况：逆序T = O(N2)  
稳定的

#### 逆序对 ####

对于下标 i < j ,如果A\[i\] > A\[j\],则称（i，j）是一对逆序对（inversion）

交换两个相邻元素正好消去一个逆序对  
插入排序：T（N，I） = O（N+I）  
N元素的个数，逆序对的个数  
如果序列基本有序，则插入排序简单且高效  
**定理：任意N个不同元素组成的序列平均具有N（N-1）/4个逆序对。  
定理：任何仅以交换相邻两元素的来排序的算法，其平均时间复杂度为Ω（N2）。**

要提高算法效率，我们必须：  
每次消去不止一个逆序对  
每次交换相隔较远的2个元素。

#### 希尔排序 ####

希尔排序(Shell’s Sort)是插入排序的一种又称“**缩小增量排序**”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是**非稳定排序**算法。该方法因D.L.Shell于1959年提出而得名。  
希尔排序是把记录按下标的一定增量**分组**，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。  
增量为1时就是前面讲的直接插入排序。

算法

void ShellSort(datatype R[],int n,int d[],int t)
    { 
    	int i,j,k,h;
    	for(k=0;k<t;k++)
    	{ 
    		h=d[k];
    		for(i=h+1;i<=n;i++)
    		{ 
    			if(R[i].key<R[i-h].key)
    			{ 
    				R[0] = R[i];
    				for(j=i-h;j>0&&R[0].key<R[j].key;j=j-h)
    					R[j+h]=R[j];
    				R[j+h]=R[0];
    			}
    		}
    	}
    }