基本排序算法
冒泡排序
方法介绍
冒泡排序，又被称为气泡排序或泡沫排序。 它会遍历若干次要排序的数列，每次遍历时，会从前往后一次比较相邻两个数的大小，如果前者比后者大，则交换它们的位置，如果后者比前者大，则继续遍历。这样，一次遍历之后，数组中最大的元素就会处于数组的末尾。同理，第二次遍历后，数组第二大的元素则会处在最大的元素前一位。重复上述操作，知道整个数组有序为止。
图文说明
代码实现
void bubble_sort(int* arr,int sz)
{
int i = 0;
int flag = 1;
for (i = 0; i < sz-1; i++)
{
int j = 0;
//一趟冒泡排序之后，数组中最大的元素就在数列的末尾
for (j = 0; j < sz - i - 1; j++)
{
if (arr[j] > arr[j + 1])//如果左边的数比右边的数大，就交换
{
flag = 0;
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
if (flag == 1)//如果已经有序，提前跳出循环
break;
}
}快速排序
方法介绍
选择数组中的一个数作为基准值，通过一趟排序将整个数组分为两个部分，其中一部分的数据都比这个基准值小，另一部分的数据都比这个基准值大。同理，再按照此方法，对两部分的数据进行排序，整个排序过程以递归的方式进行。 更加详细的介绍可以跳转到：深入理解——快速排序-CSDN博客
下面是一段伪代码：
图文说明
代码实现
//left=0 左边界
//right=length-1 右边界
void Quicksort(int* arr, int left, int right)
{
if (left < right)
{
int l = left;
int r = right;
int base = arr[left];//基准数
while (l < r)
{
while (l<r && arr[r]>=base)
{
r--;//从右向左找第一个小于base的数
}
if (l < r)
arr[l] = arr[r];//右边的数小于base，就与arr[l]交换
while (l < r && arr[l] <= base)
l++;//从左向右找第一个大于base的数
if (l < r)
arr[r] = arr[l];//左边的数大于base，就与arr[r]交换
}
arr[l] = base;
Quicksort(arr, left, r-1);//对左边的子数列按照同样的方法进行排序
Quicksort(arr, r+1, right);//对右边的子数列按照同样的方法进行排序
}
}选择排序
方法介绍
首先在未排序的数组中找到最大或者最小的元素，然后将其放在起始位置，同理，在未排序的数组中继续寻找最大或最小的数，将其放在已排序（每次找到的元素构成的数列）的数列的末尾。
图文介绍
代码实现
#define LENGTH(arr) (sizeof(arr)/sizeof(arr[0]))
void select_sort(int* arr, int n)
{
int i, j, min;
for (i = 0; i < n; i++)
{
min = i;
for (j = i + 1; j < n; j++)
{
if (arr[j] < arr[min])
{
min = j;
}
}
//如果min！=i，则交换arr[i],arr[min]
//保证arr[0]到arr[i]之间是有序的
if (min != i)
{
int tmp = arr[min];
arr[min] = arr[i];
arr[i] = tmp;
}
}
}直接插入排序
方法介绍
把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。（适用于少量元素的排序）
可以类比为打扑克牌时，对扑克牌进行的排序。
下面是一段伪代码：
图文介绍
代码实现
//arr[] 待排序的数组
//n 数组长度
void Insert_sort(int arr[], int n)
{
int i, j, k;
//0~i-1为一个有序区间
for (i = 1; i < n; i++)
{
//无序区的第一个数据为arr[i],为arr[i]在前面的有序区间内找一个合适的位置，将其插入
for (j = i - 1; j >= 0; j--)
if (arr[j] < arr[i])//如果有序区内有数比arr[i]小，就跳出循环，直接插入
break;
//找到了位置
if (j != i - 1)
{
//比arr[i]大的数据往后移
int temp = arr[i];
for (k = i-1; k > j; k--)
arr[k + 1] = arr[k];
//将arr[i]放在合适的位置
arr[k + 1] = temp;
}
}
}希尔排序
方法介绍
希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。该方法又称缩小增量排序。 对于n个待排序的数列，取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列，所有距离为gap的倍数的记录放在同一个组中；然后，对各组内的元素进行直接插入排序。 这一趟排序完成之后，每一个组的元素都是有序的。然后减小gap的值，并重复执行上述的分组和排序。重复这样的操作，当gap=1时，整个数列就是有序的。 更加详细的介绍可以跳转到：深入理解希尔排序-CSDN博客
图文介绍
代码实现
//分组插入
// 假设数组为1，3，4，5，6，7，8
// 步长为2，组内相邻两个数下标的差为2
// 则被分为两组
// 一组是1，4，6，8
// 一组是3，5，7
//a 待排序的数组
//n 数组长度
void group_sort(int a[], int n, int i, int gap)
{
int j;
for (j = i + gap; j < n; j += gap)
{
//如果a[j]<a[j-gap](子列中两个相邻的元素),则寻找a[j]的位置，并将后面的数据后移
if (a[j] < a[j - gap])
{
int tmp = a[j];
int k = j - gap;
while (k >= 0 && a[k] > tmp)
{
a[k + gap] = a[k];
k -= gap;
}
a[k + gap] = tmp;
}
}
}
void shell_sort(int a[], int n)
{
int i, gap;
//gap为步长，每次减小为原来的一半
for (gap = n / 2; gap > 0; gap /= 2)
{
//共gap个组，对每一个组进行直接插入排序
for (i = 0; i < gap; i++)
{
group_sort(a, n, i, gap);
}
int m = 0;
for (m = 0; m < n; m++)
{
printf("%d ", a[m]);
}
printf("\n");
}
}桶排序
方法介绍
假设待排序的数组arr中共有N个整数，并且已知数组a中数据的范围[0, MAX)。在桶排序时，创建容量为MAX的桶数组buckets，并将桶数组元素都初始化为0；将容量为MAX的桶数组中的每一个单元都看作一个"桶"。 在排序时，逐个遍历数组arr，将数组arr的值，作为"桶数组buckets"的下标。当a中数据被读取时，就将桶的值加1。例如，读取到数组arr[3]=5，则将buckets[5]的值+1。
图文介绍
代码实现
int buckets[100000];
int arr[2000000];
void bucket_sort(int* a, int n, int max)
{
int i, j;
//计数
for (i = 0; i < n; i++)
{
buckets[a[i]]++;
}
//排序
for (i = 0, j = 0; i <= max; i++)
{
while ((buckets[i]--) > 0)
{
a[j++] = i;
}
}
}注：部分插图非原创