常见排序算法代码实现c语言

学习数据结构常见排序算法代码实现记录
包括常见三大类排序算法实现

• 选择排序：简单选择排序，堆排序
• 插入排序：简单插入排序，希尔排序
• 交换排序：冒泡排序，两端冒泡排序，快速排序
• 归并排序
• 基数排序

代码如下

#include<stdio.h>
#include <stdbool.h>

//交换函数
void swap(int* a, int* b)
{
	int t;
	t = *a;
	*a = *b;
	*b = t;
}

//冒泡排序
void bubblesort(int a[], int n)
{
	int i, j;
	bool flag;
	//循环n-1次
	for (i = 0; i < n - 1; i++)
	{
		flag = false;//判断如果已经无逆序，跳过此次排序
		for (j = n - 1; j > i; j--)//从序列后面向前面冒泡
		{
			if (a[j - 1] > a[j])
			{
				swap(&a[j - 1], &a[j]);
			}
			flag = true;
		}
		if (flag == false) return;
	}
}

//两端冒泡法
void doublebubblesort(int a[], int n)
{
	int low = 0, high = n - 1, i;
	bool flag = true;//判断此次排序是否需要循环
	while (low < high)//跳出循环条件
	{
		flag = false;
		for (i = low; i < high; i++)//从前往后冒泡
		{
			if (a[i] > a[i + 1])
			{
				swap(&a[i], &a[i + 1]);
			}
			flag = true;
		}
		high--;//以排好一个最大元素

		for (i = high; i > low; i--)//从后往前冒泡
		{
			if (a[i] < a[i - 1])
			{
				swap(&a[i], &a[i - 1]);
			}
			flag = true;
		}
		low++;//排好一个最小元素
	}
}

//插入排序
void insertsort(int a[], int n)
{
	int temp;
	int i, j;
	for (i = 1; i < n; i++)
	{
		temp = a[i];//记录
		for (j = i; j > 0 && a[j - 1] > temp; j--)//计算移动大小
		{
			a[j] = a[j - 1];//数组元素后移
		}
		a[j] = temp;//复制到插入位置
	}
}

//选择排序
void choosesort(int a[], int n)
{
	int temp;
	int min;
	for (int i = 0; i < n - 1; i++)
	{
		min = i;//初始化最小值位置
		for (int j = i + 1; j < n; j++)//依次比较大小
		{
			if (a[min] > a[j])
			{
				min = j;//更新最小值位置
			}
		}
		if (min != i)//如果最小值位置改变，则交换
		{
			swap(&a[i], &a[min]);
		}
	}
}

//希尔排序
void shellsort(int a[], int n)
{
	int i, j, temp, dk;
	//相隔dk个距离
	for (dk = n / 2; dk >= 1; dk = dk / 2)
	{
		//插入排序，将i从dk开始，每次与i-dk位置进行比较
		for (i = dk; i < n; i++)
		{
			temp = a[i];
			for (j = i; j >= dk && a[j - dk] > temp; j -= dk)
			{
				a[j] = a[j - dk];
			}
			a[j] = temp;//复制值到插入位置
		}
	}
	/*for(i=dk; i<n; i++)
	{
	if(a[i]<a[i-dk])
	{
	temp=a[i];
	for(j=i-dk; j>0&&temp<a[j]; j-=dk)
	{
	a[j+dk]=a[j];
	}
	a[j+dk]=temp;
	}*/
}

//快速排序，划分操作
int partition(int a[], int left, int right)
{
	int pivot = a[left];//将表中第一个元素作为枢轴进行划分
	while (left < right)//循环跳出条件
	{
		//比枢轴小的元素移动到左端
		while (left < right && a[right] >= pivot)
		{
			--right;//右端值大于枢轴则跳过，向左端继续寻找小于枢轴的值
		}
		a[left] = a[right];

		//比枢轴大的元素移动到右端
		while (left < right && a[left] <= pivot)
		{
			++left;//左端值小于枢轴则跳过，向右端继续寻找大于枢轴的值
		}
		a[right] = a[left];
	}
	a[left] = pivot;//枢轴存放到最终位置
	return left;//返回存放枢轴的最终位置
}

//递归调用快速排序
void quick_sort(int a[], int left, int right)
{
	if (left < right)//跳出条件
	{
		int pivotpos = partition(a, left, right);//划分，得到枢轴位置
		quick_sort(a, left, pivotpos - 1);//对坐子表递归
		quick_sort(a, pivotpos + 1, right);//对友子表递归
	}
}

//快速排序 封装接口
void quicksort(int a[], int n)
{
	quick_sort(a, 0, n - 1);//调用
}

//调整堆函数
//将n个元素数组中a[p]为根的子堆调整为最大堆
void heapadjust(int a[], int p, int n)
{
	int parent, child, temp;
	temp = a[p];//暂存根结点的值
	for (parent = p; (parent * 2 + 1) < n; parent = child)
	{
		child = parent * 2 + 1;
		if (child != n - 1 && a[child] < a[child + 1])//沿key较大的子结点向下筛选
		{
			child++;//取parent较大的左右子结点
		}
		if (temp >= a[child]) break;//如果根结点大，找到合适位置筛选结束
		else
		{
			a[parent] = a[child];//下滤。子结点大于根结点，将a[i]调整
		}
	}
	a[parent] = temp;//原根结点被筛选修改结点的值的最终位置
}


//堆排序
void heapsort(int a[], int n)
{
	int i;
	//建立最大堆
	for (i = n / 2 - 1; i >= 0; i--)
	{
		heapadjust(a, i, n);
	}

	//删除最大堆顶
	for (i = n - 1; i > 0; i--)
	{
		swap(&a[i], &a[0]);//输出堆顶元素

		heapadjust(a, 0, i);//调整堆
	}
}

//归并排序
void mergesort(int a[], int n)
{
	int* tempa;
	tempa = malloc(n * sizeof(int));//申请空间为n的临时空间
	if (tempa)
	{
		merge_sort(a, tempa, 0, n - 1);//递归
		free(tempa);
	}
	else
	{
		printf("空间不足");
		return 1;
	}
}

//归并排序递归核心
void merge_sort(int a[], int tempa[], int low, int high)
{
	if (low < high)
	{
		int mid = (low + high) / 2;//从中间划分两个子序列
		merge_sort(a, tempa, low, mid);//左侧子序列递归
		merge_sort(a, tempa, mid + 1, high);//右侧子序列递归
		merge(a, tempa, low, mid + 1, high);//两个子序列归并
	}
}


//两个有序子序列合并函数
void merge(int a[], int tempa[], int low, int mid, int high)
{
	int leftlow, num, temp, i;

	leftlow = mid - 1;//a序列中第一个有序序列末尾
	temp = low;//tempa序列起始位置
	num = high - low + 1;//合并后的序列总长

	while (low <= leftlow && mid <= high)
	{
		if (a[low] <= a[mid])
		{
			tempa[temp++] = a[low++];//第一个序列的值复制到新数组
		}
		else
		{
			tempa[temp++] = a[mid++];//第二个序列的值复制到新数组
		}
	}

	while (low <= leftlow)
		tempa[temp++] = a[low++];//第一个序列剩下的加到新数组
	while (mid <= high)
		tempa[temp++] = a[mid++];//第二个序列剩下的加到新数组

	for (i = 0; i <= num; i++, high--) //将排好序的数组复制回原数组
		a[high] = tempa[high];
}

int main()
{
	int a[10] = { 5,4,3,2,1,0,-1,-2,6,0 };
	heapsort(a, sizeof(a) / sizeof(a[0]));
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}