C语言-数据结构-各种排序算法

ゝ一纸荒年。 2022-05-14 07:18 218阅读 0赞

## main函数 ##

#include "stdio.h"
    #include "stdlib.h"
    #include "malloc.h"
    #include "stdbool.h"
    #include "string.h"
    #include "QuickSort.h" 
    #include "InsertionSort.h" 
    #include "BubbleSort.h"
     
    
    
    #define N_a 8
     
    int main()
    {
    	int a[N_a] = {4,8,3,6,0,1,32,4}; 
    	int i;
    //	QuickSort(a, 0, 5); //第二个参数表示第一个元素的下标 第三个参数表示最后一个 
    //	InsertionSort(a, 0, 5);
    //	InsertionSort_Halve(a, 0, N_a-1);
    //	InsertionSort_Shell2(a, 0, N_a-1);
    	BubbleSort(a, 0, N_a-1);
    	for(i=0; i <= N_a-1; i++)
    	{
    		printf("%d ",a[i]);
    	} 
    	printf("\n");
    	
    	
    	
    	
    	printf("\n\n\nHello World!!!\n");
    	return;
    }

## 冒泡排序 ##

BubbleSort.h

#ifndef __BUBBLESORT_H_
    #define __BUBBLESORT_H_
    #include "stdio.h"
    #include "stdlib.h"
    #include "malloc.h"
    #include "stdbool.h"
    #include "string.h"
    
    
    typedef int myType;
    
    //函数声明区
    bool BubbleSort(myType*a, int low, int high);
    
    //函数实现区
    
    
    void swap(myType *a, myType*b)
    {
    	*a = *a^*b;
    	*b = *a^*b;
    	*a = *a^*b;
    } 
    bool BubbleSort(myType*a,int low, int high) //平均复杂度为O(n^2),最坏O(n^2) 
    {
    	int i,j;
    	bool flag;
    	for(i=low; i<high; i++)
    	{
    		flag = false;
    		for(j=high; j>i; j--)
    		{
    			if(a[j-1] > a[j])//逆序
    			{	
    				swap(a+j-1, a+j);
    				flag = true;
    			} 
    		}
    		if(!flag)return;  //确定后面全是顺序可以退出
    	} 
    } 
    
    #endif

## 直接插入 ##

InsertionSort.h  
注意希尔排序有bug,没时间啦,

#ifndef __INSERRTIONSORT_H_
    #define __INSERRTIONSORT_H_
    
    //声明头文件
    #include "stdio.h"
    #include "stdlib.h"
    #include "malloc.h"
    #include "stdbool.h"
    #include "string.h"
    
    
    //函数申明区
    void InsertionSort (int *a, int low, int high); //直接插入排序 
    void InsertionSort_Halve(int *a, int low, int high); //折半插入排序 
    void InsertionSort_Shell(int *a, int low, int high); 
    
    //函数实现区
    
    /* 直接插入排序 */ 
    // 插入排序（insertion sort）— O(n2)
    // 遍历数组，遍历到i时，a0,a1...ai-1是已经排好序的，
    // 取出ai，从ai-1开始向前和每个比较大小，如果小于，
    // 则将此位置元素向后移动，继续先前比较，如果不小于，
    // 则放到正在比较的元素之后。可见相等元素比较是，
    // 原来靠后的还是拍在后边，所以插入排序是稳定的。
    void InsertionSort (int *a, int low, int high) 
    { // 4,2,8,3,6,0,1
    	int i, j, val;
    	for(i=low+1; i<=high; i++)
    	{
    		if(a[i-1] > a[i])		//依次将a[0]~a[n]插入到前面已经排序好的序列
    		{
    			val = a[i];
    			for(j=i-1; val<a[j];j--) //将 i 与 i的上一个数字依次进行比较 
    			{
    				a[j+1] = a[j]; 
    			}
    			a[j+1] = val;
    		}	
    	}
    	return;
    }
    
    /* 折半插入排序 */   //减少了比较次数,约O(log2^n)
    //时间复杂度依然是O(n^2) 
    //折半插入排序是怎么做的呢？非常简单。取已经排好序的数组的中间元素，
    //与插入的数据进行比较，如果比插入的数据大，那么插入的数据肯定属于
    //前半部分，否则属于后半部分。这样，不断遍历缩小范围，很快就能确
    //定需要插入的位置。这就是所谓“折半”。
    void InsertionSort_Halve(int *a, int low, int high) 
    { // 4,2,8,3,6,0,1
    	int i, j, val;
    	int L,H,Mid; //折半查找范围 
    	for(i=low+1; i<=high; i++)
    	{
    		val = a[i];
    		L = 0;
    		H = i-1; 
    		while(L <= H) //折半查找,默认为升序		
    		{
    			Mid = (L+H)/2;
    			if(a[Mid] > val) 
    				H = Mid - 1; 
    			else
    				L = Mid + 1;
    		}
    		for(j=i-1; j>=H+1; j--)
    			a[j+1] = a[j];
    		a[H+1] = val;
    	
    	}
    	return;
    } 
    
    /* 希尔排序 */  //空间复杂度为O(1), 时间复杂度为O(n^1.3) 
    //Shell排序也是对直接插入排序的改进。它实质上是一种分组插入方法
    //　　对于n个元素的数组，假设增量为 h：
    //　　第一趟　　：　　从第1个元素开始，每隔h取一个元素，那么最后可以得到n/h个元素，
    //	  一边取，一边通过直接插入将这h个元素排序
    //　　第二趟　　：　　从第2个元素开始，每隔h取一个元素，跟第一趟一样。　　
    //　　...
    //　　第h趟　　 ：　　从第h个元素开始，每隔h取一个元素，跟第一趟一样。
    // 　　（此时，整个数组还不是有序的）
    //　　然后，减少h的值，重复上面的操作，直到h减小为1，排序完成。
    void InsertionSort_Shell(int *a, int low, int high) 
    {	// 4,2,8,3,6,0,1
    //前后增量为dk不是1
    	int dk = (high-low)/2; //5
    	int i,j,val;
    	for(dk; dk>=1; dk=dk/2)
    	{
    		for(i = dk; i<=high; i++)//5-9
    		{
    			if(a[i]<a[i-dk])//5-0 
    			{
    				val = a[i];//5
    				for(j=i-dk; j>=0&&val<a[j]; j-=dk)//0-
    				{
    					a[j+dk] = a[j];
    				}
    				a[j+dk] = val;
    			}
    		}
    	} 
    	
    }
    
    #endif

## 快速排序 ##

QuickSort.h

#ifndef __QUICKSORTT_H_
    #define __QUICKSORTT_H_
    
    //声明头文件
    #include "stdio.h"
    #include "stdlib.h"
    #include "malloc.h"
    #include "stdbool.h"
    #include "string.h"
    
    //函数申明区
    
    int FindPos_Fixed_low(int *a,int low, int high);//查找 
    void QuickSort(int *a, int low, int high);//快排 
    
    //函数实现区
    
    /* 寻找low元素的位置,返回low  */ 
    int FindPos_Fixed_low(int *a,int low, int high)
    {
    	int val = a[low];
    	while( low < high )
    	{
    		while(low < high && a[high] >= val ) --high;  //low < high 这句话不能删除 如序列6 0 2 4 9 7 10 
    		a[low] = a[high];
    		while(low < high && a[low] <= val ) ++low;
    		a[high] = a[low];
    	}  //终止while之后low和high一定相等 
    	a[low] = val;
    	return low;
    }
    
    /* 快速排序 */ 
    void QuickSort(int *a, int low, int high)
    {
    	int pos;
    	if(low < high)
    	{
    		pos = FindPos_Fixed_low(a, low, high); //定low 第一个元素位置,固定 
    		QuickSort(a, low, pos-1);	 
    		QuickSort(a, pos+1, high);
    	}	
    	return;
    }
    
    #endif
    
    
    /* 查找数字a中low到high 中第一个元素的位置*/ 
    
    //	9  0  8  10 -5 2 13 7
    //	L                   H
    //	先val = a[0]
    //	比较H位 跟 val ,当H位小于 val , 将H位赋值给L
    //	7  0  8  10 -5 2 13 7
    //	L                   H
    //	
    //	
    //	L位开始向右移动,找比val 大的数, 找到后
    //	7  0  8  10 -5 2 13 7
    //	         L          H
    //	将L指向的赋值给H
    //	7  0  8  10 -5 2 13 10
    //	         L          H
    //	
    //	H在向左移动,接着找比val小的数
    //	7  0  8  10 -5 2 13 10
    //	         L     H  
    //	将H赋值给L
    //	7  0  8  2  -5 2 13 10
    //	         L     H      
    //	L向右移动, 找到比val大的
    //	此时右移动于H重合
    //	 
    //	7  0  8  2  -5 2 13 10
    //	               H
    //				   L
    //	此时将Val赋值给L位置
    //	7  0  8  2  -5 9 13 10
    //	第一轮结束