#include <stdio.h>
void PrintContext(char sort[], int size)
{
for(int i=0;i<size;i++)
{
printf("%d ", sort[i]);
}
printf("\n");
}
//冒泡排序
//Reverse 0:正向排序
//Reverse 1:反向排序
void OrderBubbleSort(char sort[], int size, int Reverse)
{
for(int i=0; i<size; i++)
{
for(int j=0; j<size -i-1; j++)
{
if(0 == Reverse)
{
if(sort[j] > sort[j+1])
{
char tmp;
tmp = sort[j+1];
sort[j+1] = sort[j];
sort[j] = tmp;
}
}
else
{
if(sort[j] < sort[j+1])
{
char tmp;
tmp = sort[j+1];
sort[j+1] = sort[j];
sort[j] = tmp;
}
}
}
}
}
int main()
{
char sort1[8] = {1,3,4,2,5,6,8,7};
char sort2[10] = {1,3,4,2,10,9,5,6,8,7};
printf("sort1:");
PrintContext(sort1, sizeof(sort1));
printf("sort1 Order:");
OrderBubbleSort(sort1, sizeof(sort1),0);
PrintContext(sort1, sizeof(sort1));
printf("sort1 ReverseOrder:");
OrderBubbleSort(sort1, sizeof(sort1),1);
PrintContext(sort1, sizeof(sort1));
printf("sort2:");
PrintContext(sort2, sizeof(sort2));
printf("sort2 Order:");
OrderBubbleSort(sort2, sizeof(sort2),0);
PrintContext(sort2, sizeof(sort2));
printf("sort2 ReverseOrder:");
OrderBubbleSort(sort2, sizeof(sort2),1);
PrintContext(sort2, sizeof(sort2));
return 0;
}运行结果
sort1:1 3 4 2 5 6 8 7
sort1 Order:1 2 3 4 5 6 7 8
sort1 ReverseOrder:8 7 6 5 4 3 2 1
sort2:1 3 4 2 10 9 5 6 8 7
sort2 Order:1 2 3 4 5 6 7 8 9 10
sort2 ReverseOrder:10 9 8 7 6 5 4 3 2 1
(2).快速
#include <stdio.h>
void PrintContext(char sort[], int size)
{
for(int i=0;i<size;i++)
{
printf("%d ", sort[i]);
}
printf("\n");
}
void ExChangeNum(char sort[], char num1, char num2)
{
char tmp;
tmp = sort[num1];
sort[num1] = sort[num2];
sort[num2] = tmp;
}
//快速排序
void QuickSort(char sort[], int start, int end)
{
if(start > end)
return ;
int start_loop = start;
int end_loop = end;
char Base = sort[start];
while(start_loop < end_loop)
{
while(start_loop < end_loop && sort[end_loop] >= Base)
{
end_loop=end_loop-1;
}
while(start_loop < end_loop && sort[start_loop] <= Base)
{
start_loop = start_loop+1;
}
if(start_loop < end_loop)
ExChangeNum(sort,start_loop, end_loop);
}
ExChangeNum(sort,start, start_loop);
QuickSort(sort, start, end_loop-1);
QuickSort(sort, end_loop+1, end);
}
int main()
{
char sort1[8] = {1,3,4,2,5,6,8,7};
char sort2[10] = {3,1,4,2,10,9,5,6,8,7};
printf("sort1:");
PrintContext(sort1, sizeof(sort1));
printf("sort1 Order:");
QuickSort(sort1, 0, sizeof(sort1)-1);
PrintContext(sort1, sizeof(sort1));
printf("sort2:");
PrintContext(sort2, sizeof(sort2));
printf("sort2 Order:");
QuickSort(sort2, 0, sizeof(sort2)-1);
PrintContext(sort2, sizeof(sort2));
return 0;
}运行结果
sort1:1 3 4 2 5 6 8 7
sort1 Order:1 2 3 4 5 6 7 8
sort2:3 1 4 2 10 9 5 6 8 7
sort2 Order:1 2 3 4 5 6 7 8 9 10希尔排序本质上也是直接插入排序，但是会先进行预排序，使原序列更接近有序序列，最后将预排之后的序列进行直接插入排序。
序列：arr1[] = {9，8，7，6，5，4，3，2，1，0}，如果用直接插入排序，那么需要往后移动元素的次数为n*(n-1)/2，也就是45次；
序列呢：arr2[] = {0，1，2，3，5，4，8，7，6，9}；，用直接插入排序，需要移动元素的次数仅为4次。
希尔排序就是根据步长设置，先分区域排序，减少元素移动次数
一个数组为{9,7,8,4,6,1,3,2}，有数组我们可知这个数组中的元素个数为8个
(1)第一次步长：step = n(数组元素个数) / 2(这里/号为c语言中的取整符号) => 8/2=4;
先9与6，7和1，8和3，4和2比
{6,1,3,2,9,7,8,4}
（2）第二次步长：step = step(这里的step为第一次的step的值)/2 => 4/2 = 2；
再6，3，9，8比，1，2，7，4比
{3，1，6，2，8，4，9，7}
（3）第三次步长：step = step(这个同上)/2 => 2/2 = 1；
最后所有比
{1，2，3，4，6，7，8，9}
#include <stdio.h>
void arr_out(int a[8])
{
int i = 0;
for(i = 0;i < 8;i++)
{
printf("%d ",a[i]);
}
printf("\n");
}
void arr_sort(int *p,int n)
{
int step = 0;//步长
int temp = 0;//用来保存第二段数据
int i,j;
for(step = n / 2;step > 0;step /= 2)
{
for(i = step;i < n;i++)
{
temp = p[i];
for(j = i - step;j >= 0 && p[j] > temp;j -= step)
{
p[j + step] = p[j];
//当满足条件时第一次j+step = i;后面的j+step = 上一次j的值
}
p[j + step] = temp;
}
}
}
int main()
{
int a[8] = {9,7,8,4,6,1,3,2};
arr_sort(a,8);//排序函数
arr_out(a);//输出函数
return 0;
}
3.选择排序
(1).简单选择
比较简单，不详细描述
(2).堆：以下4步，完成堆排序
1).数组转化为二叉树
父节点下标为k(k>0)，那么其左孩子下标为2*k，右孩子下标为2*k+1
leftchild=parent×2+1;
rightchild=parent×2+2;
parent=(child-1)/2。
2).最大堆排序 （Heapify）
从左右孩子中选择最大的孩子结点，与父结点交换，并递归调整交换后的孩子结点
3).创建最大堆（CreateHeap）
单对一个节点进行最大堆调整并不能使整个二叉树形成最大堆，所以我们需对末尾节点的父节点依次向前进行最大堆排序，从而使得二叉树形成最大堆。
4)、堆排序
根节点为最大值，将其与末尾子节点交换
对根节点进行最大堆调整，以交换的末尾节点不参与调整 ，使根节点为下一个最大值
不断变换，缩小最大堆调整范围，只剩根节点，完成节点排序
#include <stdio.h>
#define size 10
void Swap(int *num, int i, int j)
{
int temp;
temp = num[i];
num[i] = num[j];
num[j] = temp;
}
// 最大堆调整
void Heapify(int *num, int len, int k)
{
if (k < len)
{
int root = k; // 根结点
int lchild = 2*k + 1; // 左孩子结点
int rchild = 2*k + 2; // 右孩子结点
// 查找左右孩子结点中的最大结点
if (lchild < len && num[root] < num[lchild])
{
root = lchild;
}
if (rchild < len && num[root] < num[rchild])
{
root = rchild;
}
// 交换最大结点到根结点
if (root != k)
{
Swap(num, root, k);
// 每次交换都可能影响到对应孩子结点子树的顺序
// 所以需要对交换后的孩子结点子树进行最大堆调整
Heapify(num, len, root);
}
}
}
// 创建最大堆
void CreateHeap(int *num, int len)
{
int i;
// 最后一个结点下标
int last = len - 1;
// 最后一个结点的父结点下标
int parent = (last - 1) / 2;
// 从最后一个结点的父结点到根结点，依次进行最大堆调整
for (i = parent; i >= 0; i--)
{
Heapify(num, len, i);
}
}
// 堆排序
void HeapSort(int *num, int len)
{
// 创建最大堆并进行最大堆调整
CreateHeap(num, len);
printf("最大堆调整!\n");
int i;
// 依次取出根结点（最大值）
for (i = len - 1; i >= 0; i--)
{
// 将最大堆的根结点（最大值）换到最后一个结点
Swap(num, i, 0);
// 交换后二叉树的根结点发生了改变，故还需对根结点做最大堆调整（已交换的末尾结点不参与调整）
// 而此时根结点小于所有父结点，因而在调整时只需考虑最大孩子的分支即可
Heapify(num, i, 0);
}
}
int main()
{
int i, num[size] = {8, 4, 3, 1, 6, 9, 5, 7, 2, 0};
HeapSort(num, size);
for (i = 0; i < size; i++)
{
printf("%d ", num[i]);
}
printf("\n");
return 0;
}
4.归并排序
(1).二路归并
二路归并的步骤是先拆分，再合并，具体步骤如下
{ 5,9,8,6,1,3,2,4 }
=>{5,9,8,6} {1,3,2,4}
=>{5,9} {8,6} {1,3} {2,4}
=>{5} {9} {8} {6} {1} {3} {2} {4}
=>{5,9} {6,8} {1,3} {2,4}
=>{5,6,8,9} {1,2,3,4}
=>{1,2,3,4,5,6,8,9}
(2).多路归并
和二路归并类似，不做具体描述
二.非比较排序
1.计数排序
2.桶排序
3.基数排序