一、选择排序
算法思想：
在要排序的一组数中，选出最小的一个数与第 一个位置的数交换； 然后在剩下的数当中再找最小的与第二个位 置的数交换，如此循环 到倒数第二个数和最后一个数比较为止。 选择排序是不稳定的。算法复杂度 O(n2)--[n 的平方]
void select_sort(int *x, int n)
{
int i, j, min, t;
for(i = 0; i < n - 1; i++)
{
min = i;
for(j = i + 1; j < n; j++)
{
if(*(x + j) < *(x + min))
{
min = j;
}
}
if(m != i)
t = *(x + i);
*(x + i) = *(x + m);
*(x + m) = t;
}
return ;
}
二、直接插入排序
算法思想：
在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排 好顺序的，现在要把第 n 个数插到前面的有序 数中，使得这 n 个数 也是排好顺序的。如此反复循环，直到全部排 好顺序。 直接插入排序是稳定的。算法时间复杂度 O(n2)--[n 的平方]
void insert_sort(int *n, int n)
{
int i, j, t;
for(i = 1; i < n; i++)
{
t = *(x + i);
for(j = i - 1; j >= 0 && t <*(x + j); j--)
{
*(x + j + 1) = *(x + j);
}
*(x + j + 1) = t;
}
}三、冒泡排序
算法思想：
在要排序的一组数中，对当前还未排好序的范 围内的全部数，自上 而下对相邻的两个数依次进行比较和调整，让 较大的数往下沉，较 小的往上冒。即：每当两相邻的数比较后发现 它们的排序与排序要 求相反时，就将它们互换。 下面是一种改进的冒泡算法，它记录了每一遍 扫描后最后下沉数的 位置 k，这样可以减少外层循环扫描的次数。 冒 泡 排 序 是 稳 定 的 。 算 法 时 间 复 杂 度 O(n2)--[n 的平方]
void Bubble_sort(int *a, int n）
{
int i = 0, j = 0;
for(i = 0; i < n - 1; i++)
{
for(j = 0; j < n - 1 - i; j++)
{
if(*(a + j) > *(a + j + 1))
{
*(a + j) ^= *(a + j + 1);
*(a + j + 1) ^= *(a + j);
*(a + j) ^= *(a + j + 1);
}
}
}
return ;
}void bubble_sort(int *x, int n)
{
int j, k, h, t;
for(h = n - 1; h > 0; h = k)
{
for(j = 0, k = 0; j < h; j++)
{
if(*(x + j) > *(x +j + 1))
{
t = *(x + j);
*(x + j) = *(x + j + 1);
*(x + j + 1) = t;
k = j;
}
}
}
}
四、希尔排序
算法思想简单描述：
在直接插入排序算法中，每次插入一个数，使 有序序列只增加 1 个节点， 并且对插入下一个数没有提供任何帮助。如果 比较相隔较远距离（称为 增量）的数，使得数移动时能跨过多个元素， 则进行一次比较就可能消除 多个元素交换。D.L.shell 于 1959 年在以他名 字命名的排序算法中实现 了这一思想。算法先将要排序的一组数按某个 增量 d 分成若干组，每组中 记录的下标相差 d.对每组中全部元素进行排 序，然后再用一个较小的增量 对它进行，在每组中再进行排序。当增量减到 1 时，整个要排序的数被分成 一组，排序完成。
下面的函数是一个希尔排序算法的一个实现， 初次取序列的一半为增量， 以后每次减半，直到增量为 1。
希尔排序是不稳定的
void shell_sort(int *x, int n)
{
int h, j, k, t;
for(h = n/2; h > 0;h=h/2)
{
for(j = h; j < n; j++)
{
t = *(x + j);
for(k = j - h;(k >=0 && t < *(x + k)); k -= h)
{
*(x + k + h) = *(x + k);
}
*(x + k + h) = t
}
}
}五、快速排序
算法思想简单描述：
快速排序是对冒泡排序的一种本质改进。它的 基本思想是通过一趟 扫描后，使得排序序列的长度能大幅度地减少。 在冒泡排序中，一次 扫描只能确保最大数值的数移到正确位置，而 待排序序列的长度可能只 减少 1。快速排序通过一趟扫描，就能确保某 个数（以它为基准点吧） 的左边各数都比它小，右边各数都比它大。然 后又用同样的方法处理 它左右两边的数，直到基准点的左右只有一个 元素为止。它是由 C.A.R.Hoare 于 1962 年提出的。
显然快速排序可以用递归实现，当然也可以用 栈化解递归实现。下面的 函数是用递归实现的，有兴趣的朋友可以改成 非递归的。
快速排序是不稳定的。最理想情况算法时间复 杂度 O(nlog2n)，最坏 O(n2)
void quick_sort(int *x, int low, int high)
{
int i, j, k;
if(low < high)
{
i = low;
j = high;
t = *(x + low);
while(i < j)
{
while(i < j && *(x + j) > t)
{
j--;
}
if(i < j)
{
*(x + i) = *(x + j);
i++;
}
while(i < j && *(x + i) <= t)
{
i++;
}
if(i < j)
{
*(x + j) = *(x + i);
j--;
}
}
*(x + i) = t;
quick_sort(x, low, i - 1);
quick_sort(x, i + 1,high);
}
}六、堆排序
算法思想简单描述：
堆排序是一种树形选择排序，是对直接选择排 序的有效改进。 堆的定义如下：具有 n 个元素的序列 （h1,h2,...,hn),当且仅当 满足（ hi>=h2i,hi>=2i+1 ） 或 （hi<=h2i,hi<=2i+1）(i=1,2,...,n/2) 时称之为堆。在这里只讨论满足前者条件的堆。
由堆的定义可以看出，堆顶元素（即第一个元 素）必为最大项。完全二叉树可以 很直观地表示堆的结构。堆顶为根，其它为左 子树、右子树。 初始时把要排序的数的序列看作是一棵顺序 存储的二叉树，调整它们的存储顺序， 使之成为一个堆，这时堆的根节点的数最大。 然后将根节点与堆的最后一个节点 交换。然后对前面(n-1)个数重新调整使之成 为堆。 依此类推，直到只有两个节点 的堆，并对它们作交换，最后得到有 n 个节点 的有序序列。
从算法描述来看，堆排序需要两个过程，一是 建立堆，二是堆顶与堆的最后一个元素 交换位置。所以堆排序有两个函数组成。一是 建堆的渗透函数，二是反复调用渗透函数 实现排序的函数。 堆 排 序 是 不 稳 定 的 。 算 法 时 间 复 杂 度 O(nlog2n)。
void sift(int *x, int n, int s)
{
int t, k, j;
t = *(x+s); /*暂存开始元素*/
k = s; /*开始元素下标*/
j = 2*k + 1; /*右子树元素下标*/
while (j<n)
{
if (j<n-1 && *(x+j) < *(x+j+1))/*判断
是否满足堆的条件：满足就继续下一轮比较，
否则调整。*/
{
j++;
}
if (t<*(x+j)) /*调整*/
{
*(x+k) = *(x+j);
k = j; /*调整后，开始元素也随之调整
*/
j = 2*k + 1;
}
else /*没有需要调整了，已经是个堆了，
退出循环。*/
{
break;
}
}
*(x+k) = t; /*开始元素放到它正确位置*/
}
/*
功能：堆排序
输入：数组名称（也就是数组首地址）、数组
中元素个数
*/
void heap_sort(int *x, int n)
{
int i, k, t;
int *p;
for (i=n/2-1; i>=0; i--)
{
sift(x,n,i); /*初始建堆*/
}
for (k=n-1; k>=1; k--)
{
t = *(x+0); /*堆顶放到最后*/
*(x+0) = *(x+k);
*(x+k) = t;
sift(x,k,0); /*剩下的数再建堆*/
}
}
标签：int,void,笔试,++,算法,--,排序 From： https://blog.csdn.net/qq_60098634/article/details/141500040