排序算法（C语言版）
直接插入排序
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
//定义顺序表结构体
typedef struct {
int key;//这里可以根据实际需求添加其他数据成员
}RedType;
typedef struct {
RedType r[MAXSIZE + 1];//r[0]闲置或用作哨兵
int length;
}SqList;
//直接插入排序
void InsertSort(SqList& L) {
//对顺序表L作直接插入排序
int i, j;
for (i = 2; i <= L.length; ++i) {
if (L.r[i].key < L.r[i - 1].key) {
//将待插入元素暂存到L.r[0]中,这里把r[0]当作哨兵
L.r[0] = L.r[i];
j = i - 1;
//从后往前查找合适的插入位置,边比较边后移元素
while (j > 0 && L.r[0].key < L.r[j].key) {
L.r[j + 1] = L.r[j];
j--;
}
//插入到合适位置
L.r[j + 1] = L.r[0];
}
}
}
void PrintList(SqList L) {
for (int i = 1; i <= L.length; i++) {
printf("%d", L.r[i].key);
}
printf("\n");
}
int main() {
SqList L;
L.length = 6;
L.r[1].key = 5;
L.r[2].key = 3;
L.r[3].key = 4;
L.r[4].key = 6;
L.r[5].key = 2;
L.r[6].key = 1;
printf("Before sorting:");
PrintList(L);
InsertSort(L);
printf("After sorting:");
PrintList(L);
return 0;
}
希尔排序
#include<stdio.h>
#include<stdlib.h>
//定义顺序表中元素的结构体
typedef struct {
int key;
//这里可以根据实际需求添加其他数据成员
}RedType;
//定义顺序结构体
typedef struct {
RedType r[100 + 1];//r[0]闲置或用作暂存等用途，所以多开一位
int length;
}SqList;
//比较LT，用于比较两个元素的大小，返回1表示前者小于后者，0表示大于等于
int LT(int a, int b) {
return a < b;
}
//一趟希尔插入排序函数
void ShellInsert(SqList& L, int dk) {
int i, j;
for (i = dk + 1; i <= L.length; ++i) {
if (LT(L.r[i].key, L.r[i - dk].key)) {
//将L.r[i]暂存在L.r[0]
L.r[0] = L.r[i];
for (j = i - dk; j > 0 && LT(L.r[0].key, L.r[j].key); j -= dk)
L.r[j + dk] = L.r[j];
L.r[j + dk] = L.r[0];
}
}
}
//希尔排序函数，按给定增量序列对顺序表进行希尔排序
void ShellSort(SqList& L, int dlta[], int t) {
int k;
for (k = 0; k < t; ++k)
ShellInsert(L, dlta[k]);
}
//打印顺序表函数，方便查看排序前后顺序表中元素的情况
void PrintList(SqList L) {
for (int i = 1; i <= L.length; i++) {
printf("%d", L.r[i].key);
}
printf("\n");
}
int main(void) {
SqList L;
//初始化顺序表长度及元素
L.length = 8;
L.r[1].key = 8;
L.r[2].key = 1;
L.r[3].key = 4;
L.r[4].key = 2;
L.r[5].key = 7;
L.r[6].key = 6;
L.r[7].key = 3;
L.r[8].key = 5;
//定义增量序列，这里选择一个简
// 单示例，实际应用中可根据情况优化
// 选择
int dlta[] = { 4,2,1 };
int t = sizeof(dlta) / sizeof(dlta[0]);
printf("Before sorting：");
PrintList(L);
ShellSort(L, dlta, t);
printf("After sorting :");
PrintList(L);
return 0;
}
冒泡排序
#include<stdio.h>
#include<stdlib.h>
//定义顺序表中的元素的结构体
typedef struct {
int key;
//这里可以根据实际需求添加其他数据成员
}RedType;
//定义顺序表结构体
typedef struct {
RedType r[100 + 1];//r[0]闲置或用作暂存等用途，所以多开辟一位
int length;
}SqList;
//比较函数LT，用于比较两个元素的大小，返回1表示前者小于后者，0表示大于等于
int LT(int a, int b) {
return a < b;
}
// 冒泡排序函数
void BubbleSort(SqList& L) {
int i, j, change = 1;
for (i = 1; i < L.length && change; ++i) {
change = 0;
for (j = 1; j <= L.length - i; ++j) {
RedType temp;
if (LT(L.r[j + 1].key, L.r[j].key)) {
temp = L.r[j + 1];
L.r[j + 1] = L.r[j];
L.r[j] = temp;
change = 1;
}
}
}
}
void PrintList(SqList L) {
for (int i = 1; i <= L.length; i++) {
printf("%d", L.r[i].key);
}
printf("\n");
}
int main() {
SqList L;
// 初始化顺序表长度及元素
L.length = 8;
L.r[1].key = 8;
L.r[2].key = 1;
L.r[3].key = 4;
L.r[4].key = 2;
L.r[5].key = 7;
L.r[6].key = 6;
L.r[7].key = 3;
L.r[8].key = 5;
printf("Before sorting: ");
PrintList(L);
BubbleSort(L);
printf("After sorting: ");
PrintList(L);
return 0;
}
快速排序
#include<stdio.h>
#include<stdlib.h>
//定义顺序表中元素的结构体
typedef int KeyType;
typedef struct {
int key;
}RedType;
//定义顺序表结构体
typedef struct {
RedType r[100 + 1];//r[0]闲置或用作暂存等用途，所以多开辟一位
int length;
}SqList;
//比较函数LT,用于比较两个元素的大小，返回1表示前者小于后者，0表示大于等于
int LT(int a, int b) {
return a < b;
}
//划分函数，采用第二个版本相对简洁的实现方式，将序列划分为2部分
int Partition(SqList& L, int low, int high) {
KeyType pivotkey;
L.r[0] = L.r[low];//用子表的第一个记录做枢纽记录
pivotkey = L.r[low].key;//枢纽记录关键字
while (low < high) {
while (low < high && L.r[high].key >= pivotkey)
--high;
L.r[low] = L.r[high];//将比枢纽记录小的记录放到低端
while (low < high && L.r[low].key <= pivotkey)
++low;
L.r[high] = L.r[low];//将比枢纽记录大的记录放到高端
}
L.r[low] = L.r[0];//枢纽记录到位
return low;//返回枢纽位置
}
//递归进行快速排序的函数
void QSort(SqList& L, int low, int high) {
int pivotloc;//用于存储返回的枢纽位置
if (low < high) {
//将L.r[low....high]一分为二
pivotloc = Partition(L, low, high);
//低子表递归排序，pivotloc是一分为二的枢纽位置
QSort(L, low, pivotloc - 1);
//对高子表递归排序
QSort(L, pivotloc + 1, high);
}
}
//对外接口的快速排序函数，启动对整个顺序表的快速排序
void QuickSort(SqList& L) {
QSort(L, 1, L.length);
}
//打印顺序表函数，方便查看排序前后顺序表中元素的情况
void PrintList(SqList L) {
for (int i = 1; i <= L.length; i++) {
printf("%d", L.r[i].key);
}
printf("\n");
}
int main() {
SqList L;
// 初始化顺序表长度及元素
L.length = 8;
L.r[1].key = 8;
L.r[2].key = 1;
L.r[3].key = 4;
L.r[4].key = 2;
L.r[5].key = 7;
L.r[6].key = 6;
L.r[7].key = 3;
L.r[8].key = 5;
printf("Before sorting: ");
PrintList(L);
QuickSort(L);
printf("After sorting: ");
PrintList(L);
return 0;
}