(九)数据结构之简单排序算法实现：冒泡排序、插入排序和选择排序

墨蓝 2022-06-08 06:26 220阅读 0赞

## 1、冒泡排序 ##

/* 冒泡排序，按照由小到大顺序进行排序 */
    void Bubble_Sort( ElementType A[], int N )
    { 
    	int P, i;
    	int flag = 0;	/* 定义一个flag来判断带排序序列是否有序或局部有序，提高算法效率 */
    	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; /* 全程无交换*/
    	}
    }

## 2、插入排序 ##

/* 插入排序，从小到大排序， */
    void Insertion_Sort( ElementType A[], int N )
    { 
    	int i, P;
    	ElementType Tmp;
    	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; 				/* 把后续数据插入到合适的位置上去*/
    	}
    }

## 3、选择排序 ##

/* 选择排序 */
    void Selection_Sort ( ElementType A[], int N )
    {
    	int i, j, k;
    	ElementType Tmp;
    	for(i = 0; i < N; i++)
    	{
    		Tmp = A[i];
    		k = i;
    		for(j = i + 1; j < N; j++)
    		{
    			if(Tmp > A[j])  /* 找到剩下元素中最小的元素对应的下标 */
    			{
    				 k = j; 
    				 Tmp = A[j];
    			}
    		}
    		if(k != i)		// 表示当前位置和最小元素所在位置不相同
    			Swap(&A[i], &A[k]);
    	}
    }

## 4、完整示例代码 ##

### 4.1 冒泡排序和插入排序 ###

/* 简单排序算法的基本实现 */
    #include <stdio.h>
    
    /* 定义一些辅助数据结构或者类型 */
    typedef int ElementType;
    
    /* 定义一个用于交换的函数 */
    void Swap(ElementType *a, ElementType *b)
    {
    	ElementType temp;z
    	temp = *a;
    	*a = *b;
    	*b = temp;
    }
    
    /* 冒泡排序，按照由小到大顺序进行排序 */
    void Bubble_Sort( ElementType A[], int N )
    { 
    	int P, i;
    	int flag = 0;	/* 定义一个flag来判断带排序序列是否有序或局部有序，提高算法效率 */
    	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; /* 全程无交换*/
    	}
    }
    
    /* 插入排序，从小到大排序， */
    void Insertion_Sort( ElementType A[], int N )
    { 
    	int i, P;
    	ElementType Tmp;
    	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; 				/* 把后续数据插入到合适的位置上去*/
    	}
    }
    
    /* 程序入口 */
    int main()
    {
    	int i;
    	ElementType temp;
    	ElementType array[10];
    
    	printf("Input 10 numbers : ");
    	for(i = 0; i < 10; i++)
    	{
    		scanf("%d", &temp);
    		array[i] = temp;
    	}
    
    	/* 原始数据输出 */
    	printf("***********************************Origin************************************\n");
    	for(i = 0; i < 10; i++)
    		printf("%d ", array[i]);
    	printf("\n");
    
    	/* 冒泡排序后输出 */
    	printf("***********************************Bubble************************************\n");
    	Bubble_Sort(array, sizeof(array)/sizeof(array[0]));
    	for(i = 0; i < 10; i++)
    		printf("%d ", array[i]);
    	printf("\n");
    
    	printf("Input 10 numbers : ");
    	for(i = 0; i < 10; i++)
    	{
    		scanf("%d", &temp);
    		array[i] = temp;
    	}
    
    	/* 原始数据输出 */
    	printf("***********************************Origin************************************\n");
    	for(i = 0; i < 10; i++)
    		printf("%d ", array[i]);
    	printf("\n");
    
    	/* 插入排序后输出 */
    	printf("***********************************Insertion*********************************\n");
    	Insertion_Sort(array, sizeof(array)/sizeof(array[0]));
    	for(i = 0; i < 10; i++)
    		printf("%d ", array[i]);
    	printf("\n");
    
    	return 0;
    }

### 4.2 选择排序 ###

#include <stdio.h>
    
    /* 定义一些辅助数据结构或者类型 */
    typedef int ElementType;
    
    /* 定义一个用于交换的函数 */
    void Swap(ElementType *a, ElementType *b)
    {
    	ElementType temp;
    	temp = *a;
    	*a = *b;
    	*b = temp;
    }
    
    /* 选择排序 */
    void Selection_Sort ( ElementType A[], int N )
    {
    	int i, j, k;
    	ElementType Tmp;
    	for(i = 0; i < N; i++)
    	{
    		Tmp = A[i];
    		k = i;
    		for(j = i + 1; j < N; j++)
    		{
    			if(Tmp > A[j])  /* 找到剩下元素中最小的元素对应的下标 */
    			{
    				 k = j; 
    				 Tmp = A[j];
    			}
    		}
    		if(k != i)		// 表示当前位置和最小元素所在位置不相同
    			Swap(&A[i], &A[k]);
    	}
    }
    
    
    /* 程序入口 */
    int main()
    {
    	
    	int i;
    	ElementType temp;
    	ElementType array[10];
    
    	printf("Input 10 numbers : ");
    	for(i = 0; i < 10; i++)
    	{
    		scanf("%d", &temp);
    		array[i] = temp;
    	}
    
    	/* 原始数据输出 */
    	printf("***********************************Origin************************************\n");
    	for(i = 0; i < 10; i++)
    		printf("%d ", array[i]);
    	printf("\n");
    
    	/* 选择排序后输出 */
    	printf("***********************************Selection*********************************\n");
    	Selection_Sort(array, sizeof(array)/sizeof(array[0]));
    	for(i = 0; i < 10; i++)
    		printf("%d ", array[i]);
    	printf("\n");
    
    	return 0;
    }