考研学习之数据结构排序算法学习

谁借莪１个温暖的怀抱￠ 2022-12-15 15:29 127阅读 0赞

# 一.直接插入排序 #

## 1.1代码 ##

#include <stdio.h> 
    /**
    	直接插入排序 
    */
    void insertSort(int A[],int n){
    	int i,j;
    	//依次将A[2]~A[n] 插入到前面已排序的序列中 
    	for(i=2;i<=n;i++){
    		//若 A[i]关键码小于前去，将A[i]插入有序表 
    		if(A[i]<A[i-1]){
    			A[0] = A[i];//复制哨兵，A[0]不存放元素 
    			//从后往前寻找待插入的位置 
    			for(j=i-1;A[0]<A[j];--j){
    				//向后挪位置 
    				A[j+1] = A[j];
    			}
    			//复制到插入位置 
    			A[j+1] = A[0];
    		}
    	}
    	for(int i=1;i<=n;i++){
    		printf(" %d",A[i]);
    	}
    } 
    /**
    	折半插入排序 
    */
    
    int main(){
    	//第一个不存放元素  作为哨兵 
    	int A[9] = {0,49,38,65,97,76,13,27,49}; 
    	insertSort(A,8);
    	return 0;
    }

## 1.2执行过程 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70][]

## 1.3执行结果 ##

![20201018121713147.png][]

## 1.4算法分析 ##

a) 直接插入排序是一种稳定的排序算法，（稳定性是指经过排序后，能使关键字相同的元素保持原顺序中的相对位置不变）；

b) 适用于顺序存储和链式存储的线性表；

c) 最多的比较次数为n\*(n-1)/2

# 二.折半插入排序 #

## 2.1代码 ##

/**
    	折半插入排序 
    */
    void halfInsertSort(int A[],int n){
    	int i,j,low,high,mid;
    	//依次将A[2]~A[n] 插入到前面已排序的序列中 
    	for(i=2;i<=n;i++){
    		A[0] = A[i]; //将 A[i]暂存于 A[0]
    		low=1;high=i-1;//设置折半查找的范围 
    		//折半查找  默认递增有序 
    		while(low<=high){
    			mid = (low+high)/2;
    			if(A[mid]>A[0])
    				high = mid - 1;
    			else low = mid + 1;
    		} 
    		//后移元素 
    		for(j=i-1;j>=high+1;--j){
    			A[j+1] = A[j];
    		} 
    		//复制到插入位置 
    		A[high+1] = A[0];
    	}
    	for(int i=1;i<=n;i++){
    		printf(" %d",A[i]);
    	}
    }

## 2.2执行结果 ##

![20201018123500910.png][]

## 2.3算法分析 ##

折半插入排序与直接插入排序相比，仅仅减少了比较元素的次数；

对于数据量不是很大的排序表，折半插入排序往往能表现出很好的性能；

折半插入排序是一种稳定的排序算法；

适用于顺序存储的线性表；

# 三.希尔排序 #

## 3.1代码 ##

//希尔排序 
    void shellSort(int A[],int n){
    	//A[0] 只是暂存单元，不是哨兵 
    	int dk,i,j;
    	for(dk=n/2;dk>=1;dk=dk/2){
    		for(i=dk+1;i<=n;++i){
    			if(A[i]<A[i-dk]){
    				A[0] = A[i];//暂存A[i]
    				for(j=i-dk;j>0&&A[0]<A[j];j-=dk){
    					//向后挪位置 
    					A[j+dk] = A[j];
    				}
    				//复制到插入位置 
    				A[j+dk] = A[0];
    			}
    		}
    	}
    	for(int i=1;i<=n;i++){
    		printf(" %d",A[i]);
    	}
    }

## 3.2运行过程 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 1][]

## 3.3执行结果 ##

![20201018124909433.png][]

## 3.4算法分析 ##

希尔排序仅适用于顺序存储的线性表；

希尔排序的时间复杂度依赖于增量序列的函数；

# 四.冒泡排序 #

## 4.1代码 ##

/**
    	冒泡排序 
    */
    void bubbleSort(int A[],int n){
    	int i,j; 
    	for(i=0;i<=n-1;i++){ 
    		for(j=n-1;j>i;j--){
    			if(A[j-1]>A[j]){
    				//若为逆序 交换位置 
    				int temp = A[j];
    				A[j] = A[j-1];
    				A[j-1] = temp;
    			}
    		} 
    	} 
    	for(int i=0;i<=n-1;i++){
    		printf(" %d",A[i]);
    	}
    } 
    int main(){
    	int A[8] = {49,38,65,97,76,13,27,49}; 
    	bubbleSort(A,8); 
    	return 0;
    }

## 4.2运行过程 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 2][]

## 4.3执行结果 ##

![20201025100833898.png][]

## 4.4算法分析 ##

每一次都是选择最小或者最大的元素

是一种稳定的排序算法

每一趟排序都会将一个元素放在最终的排序位置上

# 五.快速排序 #

## 5.1代码 ##

/**
    划分函数 将表A[low...high]划分为两个子表 
    */
    int partition(int A[],int low,int high){
    	//将表中的第一个元素设为枢轴，对表进行划分 
    	int pivot = A[low];
    	while(low < high){
    		while(low<high&&A[high]>=pivot) --high;
    		//将比枢轴小的元素移动左端 
    		A[low]=A[high];
    		while(low<high&&A[low]<=pivot) ++low;
    		//将比枢轴小的元素移动右端 
    		A[high]=A[low];
    	}
    	A[low]=A[pivot];
    	return low;
    } 
    /**
    快排递归函数 
    */
    void quickSort(int A[],int low,int high) {
    	if(low < high){//递归跳出条件 
    		int pivotpos = partition(A,low,high);
    		//依次对两个子表进行递归排序 
    		quickSort(A,low,pivotpos-1); 
    		quickSort(A,pivotpos+1,high);
    	}
    }
    int main(){
    	int A[8] = {49,38,65,97,76,13,27,49};
    	quickSort(A,0,7); 
    	for(int i=0;i<=7;i++){
    		printf(" %d",A[i]);
    	}
    	return 0;
    }

## 5.2运行过程 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 4][]

## 5.3算法分析 ##

快排是所有内部排序算法中平均性能最优的排序算法；

是一种不稳定的排序算法；

快排中并不产生有序的子序列，但是每趟排序后，会将基准元素放在最终的位置上；

# 六.简单选择排序 #

## 6.1代码 ##

/**
    	简单选择排序 
    */
    void selectSort(int A[],int n){
    	int i,j; 
    	for(i=0;i<=n-1;i++){
    		int min =i; 
    		for(j=i+1;j<n;j++){
    			if(A[j]<A[min]){
    				min = j;
    			}
    		}
    		if(min != i){
    			//若为逆序 交换位置 
    			int temp = A[i];
    			A[i] = A[min];
    			A[min] = temp;
    		} 
    	} 
    	for(int i=0;i<=n-1;i++){
    		printf(" %d",A[i]);
    	}
    } 
    int main(){
    	int A[8] = {49,38,65,97,76,13,27,49};
    	selectSort(A,8); 
    }

## 6.2执行结果 ##

![20201025114926696.png][]

## 6.3算法分析 ##

是一种不稳定的排序算法

# 七.归并排序 #

## 7.1排序过程 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 5][]

## 7.2算法分析 ##

是一种稳定的排序算法

# 八.基数排序 #

##  ##

## 8.1排序过程 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 6][]

## 8.2算法分析 ##

不基于比较和移动

是一种稳定的算法

# 九.排序算法对比 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 7][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70]: /images/20221123/976c81e5fab3491b88e7f5412f60948d.png
[20201018121713147.png]: /images/20221123/3abeb821eb964a98a0b874fd0a0d215d.png
[20201018123500910.png]: /images/20221123/d456cbd60c754bf2babe416af9fe1aad.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 1]: /images/20221123/2e624719ec5543b9a59b6111e07a4497.png
[20201018124909433.png]: /images/20221123/0de8473ac085429891d493efccfb405d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 2]: /images/20221123/2f0e9fab1244472587d57338967f1172.png
[20201025100833898.png]: /images/20221123/d38214a8ec39471cafbc494d73be41f8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 3]: /images/20221123/138f0a463281443dbc416b22b7d6dd93.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 4]: /images/20221123/810907d1334649a19c8130515225ca30.png
[20201025114926696.png]: /images/20221123/29a127983e07466f8533fd69a737b6b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 5]: /images/20221123/657786a36df4433d8066bd43dbaeba4b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 6]: /images/20221123/32ef08ee6e2b4a9888162ec892f524c5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 7]: /images/20221123/dfc82966896946038f3d014757541048.png