c语言数据结构-排序（冒泡+选择+插入+希尔）_编写冒泡选择插入希尔排序的程序

 (创作不易，感谢有你，你的支持，就是我前行的最大动力，如果看完对你有帮助，请留下您的足迹），（如果您没有看懂文章或者对本文有意见，请您私信帮助我，我一定认真修改）

目录

冒泡排序：

选择排序：

插入排序：

希尔排序：

---

冒泡排序：

原理：基于交换的排序，每一轮将序列中的最大值（最小值）放到数组的尾部。使用循环重复操作，（每轮排序都会少一个最大值或最小值），当最后只剩下一个数据的时候整个序列就已经排好序了。

 代码思路：从第一个数开始，每一次在数组中选两个数继续比较，如果前面的数大于后面的数，就将两者交换位置，第一次是1，2两个位置比较，第二次就是2,3两个位置比较，以此类推

//采用两层循环实现的方法
//arr是待排序数组的首地址，n是数组元素个数
void bubblesort1(int* arr, int n)
{
	if (n < 2)
		return ;//数组个数小于2不需要排序
	int i;//排序次数
	int j;//每次排序元素位置
	int tmp;//交换位置时的临时变量
	for (i = n - 1; i > 0; i--)//一共进行n-1次
	{
		for (j = 0; j < i; j++)//每次比较0和i之前的元素，i之后已经排好
		{
			if (arr[j] > arr[j + 1])//如果前面大于后面，则交换位置
			{
				tmp = arr[j + 1];
				arr[j + 1] = arr[j];
				arr[j] = tmp;
			}
		}
	}
}

直接使用两层循环去实现，外层循环主要作用改变次数，保存最小值（最大值），内存循环的主要作用是找到发生冲突的元素，如果发生冲突就交换两个数据。当两层循环的结束的时候整个序列就自然排好序了 

 此外，还有一种方法：

//采用递归的方法
void bubblesort2(int* arr, int n)
{
	if (n < 2)
		return;//数组个数小于2不需要排序
	int j;//每次排序元素位置
	int tmp;//交换位置时的临时变量
	for (j = 0; j < n-1; j++)//每次比较0和n-1之前的元素，n-1之后已经排好
	{
		if (arr[j] > arr[j + 1])//如果前面大于后面，则交换位置
		{
			tmp = arr[j + 1];
			arr[j + 1] = arr[j];
			arr[j] = tmp;
		}
	}
	bubblesort2(arr, --n);
}

递归方法和两层循环方法相似，只是将第一次的循环以递归的形式展现 

int main()
{
	int arr[15] = { 44,3,38,5,47,15,36,26,24,2,46,4,19,50,48 };
	//bubblesort1(arr, 15);
	bubblesort2(arr, 15);
	for (int i = 0; i < 15; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	return 0;
}

 运行结果：

选择排序：

原理：基本思想和冒泡排序是一样的，选择排序相对于冒泡排序的优点就是减少交换次数。算法思想都是在序列中找到最大值（最小值），然后存放好下次进入循环就访问不到这个最大值（最小值）。当两层循环都结束的时候序列就自然排好了。

代码思路：从第一个元素开始，往后寻找，在n个数中找到最小的值，将其与第一个元素交换位置，然后从第二个元素开始继续往后寻找，在n-1个元素中找到最小的元素，与第二个元素交换位置，以此类推 

//采用两层循环实现的方法
//arr是待排序数组的首地址，n是数组元素个数
void selectsort1(int* arr, int n)
{
	if (n < 2)
		return;//数组个数小于2不需要排序
	int i;//排序次数
	int j;//每次排序元素位置
	int tmp;//每次循环时最小的元素位置
	for (i = 0; i<n-1; i++)//一共进行n-1次比较
	{
		tmp = i;
		for (j = i + 1; j < n; j++)//每次只需要比较i+1和n-1之间的元素，i之前的是已经排序号的
		{
			if (arr[j] < arr[tmp])//找到值更小的元素，记下位置
				tmp = j;
		}
		if (tmp != i)//如果此次循环的最小元素表示起始位置的元素，就交换他们的位置
		{
			int k = arr[tmp];
			arr[tmp] = arr[i];
			arr[i] = k;
		}
	}
}

同样的，与冒泡排序类似，选择排序也可以转换为递归形式： 

//采用递归的方法
void selectsort2(int* arr, int n)
{
	int j;//每次排序元素位置
	int tmp=0;//每次循环时最小的元素位置
	for (j = 1; j < n; j++)//每次只需要比较i+1和n-1之间的元素，i之前的是已经排序号的
	{
		if (arr[j] < arr[tmp])//找到值更小的元素，记下位置
			tmp = j;
	}
	if (tmp != 0)//如果此次循环的最小元素表示起始位置的元素，就交换他们的位置
	{
		int k = arr[tmp];
		arr[tmp] = arr[j];
		arr[j] = k;
	}
	selectsort2(arr + 1, --n);
}

插入排序：

原理：基本思想还是冒泡排序，不过插入排序是两边相靠的冒泡，所以在序列部分有序的情况下，插入排序的效率要比冒泡排序效率高。从序列的尾部开始往前比较，如果当前的数据小于（大于）前一个的数据就进行交换，否则进入下一次循环，直到外层循环遍历完整个序列就自然排好序了。

代码思路：从第二个元素开始，将第二个元素与前面第一个元素比较，如果比第一个元素大则位置不变，如果比他小则将第一个位置元素后移，将第二个位置的元素插入第一个位置，以此类推，让第三个元素与前面两个元素比较，如果第三个元素大于第二个位置的元素，则不变，如果小于第二个位置的元素，就将第二个位置的元素后移到第三个位置（此时第二个位置空缺），然后原来第三个元素再与第一个位置的元素比较，如果大于则顺理成章插入到第二个位置中，如果小于则第一个位置的元素后移，将原第三个位置的元素插入第一个位置

void insertsort(int *arr,int n)
{
	if (n < 2)
		return;//数组个数小于2不需要排序
	int i;//待排序的元素
	int j;//每次插入时需要后移的元素
	int tmp;//当前需要排序的元素的值
	for (i = 1; i < n; i++)
	{
		tmp = arr[i];//待排序的元素
		//从已排序的最右边开始，把大于当前排序的元素后移
		for (j = i - 1; j >= 0; j--)
		{
			if (arr[j] <= tmp)
				break;
			arr[j + 1] = arr[j];
		}
		//插入当前排序元素
		arr[j + 1] = tmp;
	}
}
int main()
{
	int arr[15] = { 44,3,38,5,47,15,36,26,24,2,46,4,19,50,48 };
	insertsort(arr, 15);
	for (int i = 0; i < 15; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	return 0;
}

 运行结果：

希尔排序：

原理：希尔排序是建立在插入排序的基础上进行优化的排序算法，所以希尔排序又叫做优化版的插入排序。

希尔排序的基本思想是把待排序的数列分为多组，然后再对每个组进行插入排序，先让数列整体大致有序，然后多次调整分组方式，使数列更加有序，最后再使用一次插入排序，使整个数列全部有序

代码思路：先将整个数组一分为二，再将每个组相同位置的元素比较大小，如果第二个组第一个元素小于第一个组第一个元素，就将两者交换位置，然后比较两个组第二个位置的元素大小，将两个组都比较完以后，再次分组，这一次将两个组各一分为二，各自比较，分到最后就变成了每个元素一一比较

//对希尔排序中的单个组进行排序
void groupsort(int*arr,int n,int pos,int step)
{
	int i;//待排序的元素
	int j;//每次插入时需要后移的元素
	int tmp;//当前需要排序的元素的值
	for (i = pos + step; i < n; i = i + step)
	{
		tmp = arr[i];//待排序元素
		for (j = i - step; j >= 0; j = j - step)
		{
			if (arr[j] <= tmp)
				break;
			arr[j + step] = arr[j];
		}
		arr[j + step] = tmp;
	}
}
//希尔排序
void shellsort(int *arr,int n)
{
	int step;//每组个数，每次减为原来的一半取整数，最后一次必定为1
	for (step = n / 2; step > 0; step = step / 2)
	{
		for (int i = 0; i < step; i++)
		{
			groupsort(arr, n, i, step);
		}
	}
}