常见排序算法代码实现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;
}