直接选择排序：
思路：从数组中挑出最小（最大）的数，与数组第一位（最后一位）交换位置，然后依次进行，直到最后两个元素比较完毕为止。
实现：
- 声明一个中间变量
max，用于存放最大值；声明一个变量m，用于存放最大值对应的序号。 - 外侧循环次数是
n-1，n是数组元素个数，意思是挑出n-1个最大值，剩下的自然是最小值。 - 内测循环次数是变化的，因为一旦最大值挑出来，放到末尾，就不需要再比较了，所以内测循环的循环次数是
n-1-i，并且从j=1开始。这里的n-1是指两两比较，n个数两两比较，只能比较n-1次；这里的i是指，已经挑出的最大值个数，也就是外侧循环的循环变量；这里的j=1是因为后面我们将总是从max=arry[0]开始，所以第一个数不需要从0开始，从第一个数开始即可。 - 首先在内循环外声明变量
m=0，然后声明中间变量max=arry[m]。在内循环的循环体中进行比较，如果遇到比max大的值，记住它的序号m=j，并且储存该值max=arry[j]，直到j=n-1-i。
C语言代码
#include <stdio.h>
// 直接排序 ，用最大值排序
int main()
{
// 待排序数组
int arry[]={5,4,3,6,7,2,1};
// 储存数组大小的变量
int n=0;
n=sizeof(arry)/sizeof(arry[0]);
// 外循环，循环 n-1次
for (int i=0;i<n-1;i++)
{
// 声明m和max，并赋初值
int m=0;
int max=arry[m];
// 内循环，循环n-1-i次，从1开始
for (int j=1;j<=n-1-i;j++)
{
if (max<arry[j])
{
// 储存最大值
m=j;
max=arry[j];
}
// 全部比较之后，将最大值放在最后一位
if (j==n-1-i)
{
arry[m]=arry[n-1-i];
arry[n-1-i]=max;
}
}
// 用于输出每一趟排序过后数组的情况
printf("第%d趟排序：",i+1);
for (int j=0;j<=n-1;j++)
{
printf("%4d",arry[j]);
}
printf("\n");
}
return 0;
}
输出情况：
可以看到，在第4趟就已经排好顺序，但依旧进行了5、6这两趟，或许还有优化的可能。
冒泡排序：
思路：也是两两比较，但不是直接找到最大值，而是类似调整顺序。相邻的两个数比较大小，大的右移，小的左移；然后再将右移后的数与后一位比较，大的右移，小的左移，以此类推。
实现：
- 声明一个中间变量
m，用于存放比较的值。 - 外循环要循环
n-1次，因为是最后一个数字不用排序，n是数组中数字的个数。 - 内循环只需要循环
n-1次，因为数字是两两比较。 - 内循环的循环体内进行比较和位移，从
arry[0]和arry[1]的比较开始，如果前者大于后者，则m=arry[0]，arry[0]=arry[1]，arry[1]=arry[0]，这样就完成了交换顺序。
C语言代码
#include <stdio.h>
// 冒泡排序 ，用最大值排序
int main()
{
// 待排序数组
int arry[]={5,4,3,6,7,2,1};
// 储存数组大小的变量
int n=0;
n=sizeof(arry)/sizeof(arry[0]);
// 外循环，循环 n 次
for (int i=0;i<n;i++)
{
// 声明 m ，并赋初值
int m=0;
// 内循环，循环 n-1 次
for (int j=0;j<n-1;j++)
{
if (arry[j]>arry[j+1])
{
// 交换顺序
m=arry[j];
arry[j]=arry[j+1];
arry[j+1]=m;
}
}
// 用于输出每一趟排序过后数组的情况
printf("第%d趟排序：",i+1);
for (int j=0;j<=n-1;j++)
{
printf("%4d",arry[j]);
}
printf("\n");
}
return 0;
}
输出情况：
插入排序：
思路：类似于打牌，手上初始有一张牌，后面摸牌，摸到比初始牌大的，放右边，否则放左边；继续摸牌，这张牌再与已有的两张牌比较、排序，以此类推。
实现：
- 声明一个数组
arry1，大小为n，也就是需要排序的数字个数，用来存放排好序的数字，它可以视作手上的牌。 - 外循环只需要
n-1次，因为arry1[0]就是待排序数组的第一个数字，也就是牌堆最上面的牌；n-1次意思是还有n-1个数字没有排序，或者说还有n-1张牌没有摸。 - 外循环的循环体进行分类和排序：比左端牌面小的直接放在最左端，注意要从最后一张牌开始往后移一位，给新牌这个空档；比左端牌面大的进行比较后再插入，需要一个变量
m记录比较的位置，当新牌比第m-1张牌大，但小于第m张牌时，新牌放在m位；需要注意，第m张牌及其右边的的牌也是要后移一位，给新牌留出空档。
C语言代码
#include <stdio.h>
// 插入排序
int main()
{
// 待排序数组
int arry[]={5,4,3,6,7,2,1};
// 储存数组大小的变量
int n=0;
n=sizeof(arry)/sizeof(arry[0]);
// 手牌数组
int arry1[n];
arry1[0]=arry[0];
// 外循环，循环 n-1 次
for (int i=1;i<n;i++)
{
// 摸的牌与手牌比较
// 比左边比更小的小牌放左边
if (arry[i]<=arry1[0])
{
for (int j=i-1;j>=0;j--)
{
arry1[j+1]=arry1[j];
}
arry1[0]=arry[i];
}
// 大一点的放牌堆里比较
else
{
int m=0;
// 现在有 i 张牌 ，最大序号是 i-1 ，要注意这点
while (arry[i]>arry1[m] && m<i)
{
m++;
}
for (int j=i-1;j>=m;j--)
{
arry1[j+1]=arry1[j];
}
arry1[m]=arry[i];
}
// 用于输出每一趟排序过后数组的情况
printf("第%d趟排序：",i);
for (int j=0;j<=i;j++)
{
printf("%4d",arry1[j]);
}
printf("\n");
}
return 0;
}
C语言代码-不额外声明数组
#include <stdio.h>
// 插入排序
int main()
{
// 待排序数组
int arry[]={5,4,3,6,7,2,1};
// 储存数组大小的变量
int n=0;
n=sizeof(arry)/sizeof(arry[0]);
// 外循环，循环 n-1 次
for (int i=1;i<n;i++)
{
// 摸的牌与手牌比较
// 比左边比更小的小牌放左边
if (arry[i]<=arry[0])
{
int m;
m=arry[i];
for (int j=i-1;j>=0;j--)
{
arry[j+1]=arry[j];
}
arry[0]=m;
}
// 大一点的放牌堆里比较
else
{
int m=0;
// 现在有 i 张牌 ，最大序号是 i-1 ，要注意这点
while (arry[i]>arry[m] && m<i)
{
m++;
}
// m位置以后的后移一位
int temp=0;
temp=arry[i];
for (int j=i-1;j>=m;j--)
{
arry[j+1]=arry[j];
}
arry[m]=temp;
}
// 用于输出每一趟排序过后数组的情况
printf("第%d趟排序：",i);
for (int j=0;j<=i;j++)
{
printf("%4d",arry[j]);
}
printf("\n");
}
return 0;
}
输出情况：
看代码，对于已经是有序数组的“手牌”来说，我们进行的大小比较是一个一个去比，这显然是低效的。对于有序数组，比较大小可以考虑二分法的思想，当然，那时候位置的记录也需要改变。利用二分法思想的插入排序是《折半插入排序》，来自于这位大佬的博客：https://www.cnblogs.com/penghuwan/p/7975841.html
希尔排序：
思路：希尔排序像是多段式的插入排序，把一个数组中等间隔的若干个数挑出来为一组，形成若干组，分别使用插入排序；然后减小间隔，再次把数组中等间隔的若干个数挑出来为一组，形成若干组，直到这个间隔减为1，也就是这个有一定次序的数组，对它进行插入排序，这和前面的直接插入排序是一样的，整个数组就排好了顺序。（很绕，看了好多次都不太明白）
一点解释：希尔数组代表了一种解决问题的想法，因为直接插入排序排有序数列是很快的，于是考虑怎样减少工作量，使得在直接插入排序时的数列已经基本有序，希尔算法就是这一想法的实现。其中，这个所谓的“等间隔”，是“步长”。步长的取法是有说法的，当然可以使用二分法，这就是原作者给出的，但是有两个步长序列可以直接使用，它们避免了一些特殊情况下的额外比较：
// 一个是由Sedgewick提出的{1, 5, 19, 41, 109, 209, 505, 929, 2161...}，公式为：n = 4^i - 3*2^i + 1
// 一个是由Hibbard提出的{1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191...}，公式为：n = 2^i - 1
// Sedgewick提出的的序列是目前最好用的
具体使用时，从序列中挑选小于等于数组长度一半的最大值作为步长。例如：
// 待排序数组
arry[10]={9,8,7,6,5,4,3,2,1,0};
// 将数组按照步长等分，步长小于数组半长的最大值是5
// 这样能分出5组
arry1[0]=arry[0];
arry1[1]=arry[5];
// 将数组按照步长等分，步长小于数组半长的最大值是3
// 这样能分出3组
arry1[0]=arry[9];
arry1[1]=arry[6];
arry1[2]=arry[3];
arry1[3]=arry[0];
实现：
- 首先声明一个数组，存放步长序列。
- 外循环的次数是初始步长到步长为
1时，位置在步长序列中的变化再加1。比如初始步长是3，则它到步长为1，在步长序列中的变化是1，所以外循环的循环次数是1+1=2。 - 次一级的外循环，它的循环次数是分出的数组的个数，也即是步长。比如一个有10个数字的数组，初始步长为
3，可以分出{0,3,6,9}，{1,4,7}，{2,5,8}这三个数组，它们都需要进行插入排序。 - 内循环进行插入排序，和插入排序的不同是，内循环中用到的循环，其增量应当是
step[i]，而不是1。
C语言代码
#include <stdio.h>
// 希尔排序
int main()
{
// 待排序数组
int arry[]={5,4,3,6,7,2,1};
// 储存数组大小的变量
int n=0;
n=sizeof(arry)/sizeof(arry[0]);
// 初始化步长变量
int i=0;
int step[13]={1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191};
while (step[i]<=n/2)
{
i++;
}
// 初始步长的位置
i--;
// 外循环，循环 i+1 次
for (i;i>=0;i--)
{
printf("步长为%d时的排序：\n",step[i]);
// 按步长循环，其实步长的大小就是等距数组的个数
for (int j=0;j<step[i];j++)
{
printf("----------第%d个分数组：\n",j+1);
// 以 j 为首元素的小数组的其他元素，在arry中的间隔是 step[i]
// 这里进行插入排序
for (int k=j+step[i];k<n;k+=step[i])
{
// 直接从插入排序-不带数组的代码中复制即可 ，注意换掉循环变量
{
// 比左边比更小的小牌放左边
// 注意，数组元素间的序号差是 step[i] ，而不是 1
if (arry[k]<=arry[j])
{
int m;
m=arry[k];
// “后移 ”数组后面的数
for (int l=k-step[i];l>=0;l-=step[i])
{
arry[l+step[i]]=arry[l];
}
arry[j]=m;
}
// 大一点的放牌堆里比较
else
{
int m=j;
// 现在有 k/step[i] 张牌 ，m不能超过k
while (arry[k]>arry[m] && m<k)
{
m+=step[i];
}
// m位置以后的后移一位
int temp=0;
temp=arry[k];
for (int l=k-step[i];l>=m;l-=step[i])
{
arry[l+step[i]]=arry[l];
}
arry[m]=temp;
}
}
// 用于输出每一趟排序过后数组的情况
printf("第%d趟插入排序：",k/step[i]);
for (int l=j;l<n && l<=k;l+=step[i])
{
printf("%4d",arry[l]);
}
printf("\n");
}
}
}
return 0;
}
输出情况：
希尔排序真是看得我一头包，我感觉它太过于麻烦，提升却不是很明显，不是很喜欢。但是它解决问题的思想却是很有用，很令人得到启发的，和前面的字符串匹配一样，我们可以对数据进行一定程度的预处理，让算法处理自己擅长的数据。
希尔算法主要看了本站这位大佬的博文，写得非常清楚：https://www.cnblogs.com/ludashi/p/6031379.html
快速排序：
思路：思路类似于二分法，从待排序数组中取任一个数，作为基准，然后把大于基准的数放在其右边，把小于该基准的数放在其左边；分好之后，该数字不动，它左边的数组和右边的数组继续执行这种分割，直到分无可分，排序就完成了。
实现：
- 因为用到递归，所以利用函数来完成，函数接受两个指针
a和b，一个用于传递数组的第一个元素的地址，一个传递数组第二个元素的地址，函数不返回任何值。 - 函数内声明一个变量
len，用于存放数组的长度，也就是b-a+1。 - 把第1个数作为基准，即
base=arry[0];。其余数与它比较，大的放在右侧，小的放在左侧。需要注意的是比较方式不同，两个边界指针也在向中间靠拢，换句话说，左指针在比较之后右移一位，而右指针在比较之后左移一位；而与base进行比较的，正是我们左右指针所指的数，这样就能实现“遍历”，并且“左”半部分和“右”半部分的交换也可以通过左右指针完成。 - 注意，函数调用自己之前应当满足条件，也就是左右指针没有超界
C语言代码-详细注释和输出
#include <stdio.h>
// 快速排序
void shu_chu(int arry[],int size)
{
for (int j=0;j<size;j++)
{
printf("%4d",arry[j]);
}
printf("\n");
}
// 排序函数，可以拿来递归
int pai_xu(int * left,int * right,int arry[])
{
// 取第一个数作为基准
int base;
base=*left;
// 储存两个端点指针
int *a=left,*b=right;
printf("______*left=%d______*right=%d\n",*left,*right);
// 其余的数如果比它大，放在右边；比他小，放在左边；
// 判断依据是左指针小于右指针
// 不加这个外层的while () 也可以，但是效率低，递归次数增加，有很多都是无用递归
while (left<right)
{
// 因为 base= arry[0]，在最左端，所以先挑比他小的数
// 从最右端比起
while (left<right)
{
if (*right < base)
{
// 如果 *right 小，把它放在左指针处，左指针 +1 ，下次从左端向右端比较
printf("*right=%d小于base=%d，*left=%d被*right=%d替换\n",*right,base,*left,*right);
*left=*right;
left++;
break;
}
else
{
// 如果 *right 大，不动，右指针 -1
// 这里的 right--; 必须注意，很容易出错
printf("*right=%d大于base=%d，左移一位再比较\n",*right,base);
right--;
}
}
printf("-------*right=%d小于base=%d，下一轮从左端比较-------\n",*right,base);
// 再比较左端
while (left<right)
{
if (*left > base)
{
// 如果 *left 大，把它放在右指针处 ，右指针 -1 ，下次从右端向左比较
printf("*left=%d大于base=%d，*right=%d被*left=%d替换\n",*left,base,*left,*right);
*right=*left;
right--;
break;
}
else
{
// 如果 *left 小，不动，左指针 +1
printf("*left=%d小于base=%d，右移一位再比较\n",*left,base);
left++;
}
}
printf("-------*left=%d大于base=%d，下一轮从右端比较-------\n",*left,base);
}
*left=base;
printf("mid=%d\n",base);
printf("================================================\n");
// 准备递归
left++;
right--;
// 左右指针都超界，退出循环，如果只有一个超界，另一个还要比较，所以不能用 &&
// 对于单边超界的，不管就行了
if (right<=a && left>=b)
{
return 0;
}
// 只有右指针超左边界，左指针在边界内，用左指针
if (left<b && left>a)
{
pai_xu(left,b,arry);
}
// 只有左指针超右边界，右指针在边界内，用右指针
if (right>a && right<b)
{
pai_xu(a,right,arry);
}
}
int main()
{
int arry[]={5,4,3,6,7,2,1};
int *left= &arry[0],*right= &arry[sizeof(arry)/sizeof(int)-1];
shu_chu(arry,sizeof(arry)/sizeof(int));
pai_xu(left,right,arry);
shu_chu(arry,sizeof(arry)/sizeof(int));
return 0;
}
C语言代码
#include <stdio.h>
// 快速排序
// 输出函数
void shu_chu(int arry[],int len)
{
for (int j=0;j<len;j++)
{
printf("%8d",arry[j]);
}
printf("\n");
}
// 排序函数
int pai_xu(int * left,int * right,int arry[],int len)
{
shu_chu(arry,len);
int base;
base=*left;
int *a=left,*b=right;
while (left<right)
{
while (left<right)
{
if (*right < base)
{
*left=*right;
left++;
break;
}
if (*right >= base) right--;
}
while (left<right)
{
if (*left > base)
{
*right=*left;
right--;
break;
}
if (*left <= base) left++;
}
}
*left=base;
printf("--->基准值是：%d<---\n",base);
shu_chu(arry,len);
printf("==========\n");
// 准备递归
left++;
right--;
if (right<=a && left>=b) return 0;
if (left>a && left<b) pai_xu(left,b,arry,len);
if (right>a && right<b) pai_xu(a,right,arry,len);
return 0;
}
int main()
{
int arry[]={5,4,3,6,7,2,1};
int *left= &arry[0],*right= &arry[sizeof(arry)/sizeof(int)-1];
pai_xu(left,right,arry,sizeof(arry)/sizeof(int));
return 0;
}
输出情况：
可以看到，在基准值为4时，已经拍好了顺序，但是后面仍然对2和3进行了比较，或许还有改进的余地。
先写这么多，后面还有“堆排序”、“归并排序”和“基数排序”等，都要用到“二叉树”这个概念，以后学习了再记
主要参考本站的这几篇博文：
这位大佬的内容图文并茂，很形象地讲解了来龙去脉，让我小白也能看懂，极力推荐：
https://www.cnblogs.com/jingmoxukong/p/4329079.html
这位大佬的内容逻辑清晰，是我容易接受的风格，但是图好像都挂了：
https://www.cnblogs.com/maybe2030/p/4715042.html