1.什么是排序
1.1排序的概念
概念：排序的概念其实非常简单，本质上就是将一堆记录按照从大到小(降序)，从小到大(升序)来进行排序。我们日常生活中每天都有着不同的排序，比如年龄大小排序，身高的排序等等。
稳定性：假设在待排序的序列中，存在多个具有相同关键字的记录，若经过排序，这些记录顺序保持不变，即在原序列中，r[i] = r[j],且r[i]在r[j]之前，而在排序之后，r[i]仍在r[j]之前，则称这种算法是稳定的；否则称为不稳定的
例如(小明总成绩199,数学成绩100;小王总成绩199,数学成绩99)，我们一般都按照总成绩来排名，但是如果总成绩相同，我们来比较数学成绩，若数学成绩相同，以此类推。所以我们先根据数学成绩排名后，小明在小王前面，再根据总成绩排名，如果此时小明还在小王前面，此算法稳定，否则称为不稳定。
1.2排序的应用
排序的应用其实非常多，比如我们在购物平台上购买一件产品，我们通常会根据销量和综合评价来判断该产品是否符合质量等等，此时就运用了排序。再比如说上述根据成绩排名，也运用了排序的思想。总的来说，排序的应用在日常生活中无处不在。
2.常见排序算法实现
2.1插入排序
插入排序的基本思想就是：把待排序的一组记录按其排序规则的大小逐个插入到一个已经排好的有序序列中，直到所有都插入完毕，得到一个新的有序序列，比如我们在玩扑克牌时：
下面我们来看看插入排序的动图：
核心思想就是把该位置的数和前一位置比较，如果比前一位小，把前一位后移，直到找到一个位置(该位置做到，比前一位大，比后一位小)，这就是一个单趟排序。
接下来我们来看代码实现：
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}我们从起始位置开始，把第一个数当成有序，当i=0时，只排了前两个，然后不断进行i++操作，不断进行单趟排序即可。这里我们要注意，最后a[end+1] = tmp；必须要在外边进行，因为如果end--到了-1，它是不会进入while循环，也就不会进行交换了。
2.2希尔排序
其实希尔排序的核心思想与插入排序类似，只不过希尔排序选了一个gap数，来使最开始的数据接近有序，最终使gap变为1，当gap为1的时候，就是一个插入排序了
我们来看下面这组数据:
此时选择gap = 2，那么我们把上面的4 2 5 8 5看成一组数，把1 3 9 6 7看成一组数使用插入排序之后，就成了2 4 5 5 8 和 1 3 6 7 9合并之后就是 2 1 4 3 5 6 5 7 8 9，是不是比一开始的数就更接近有序了，如果gap = 3，那么就分为3组依次类推。
那么我们来看看希尔排序的代码:
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}这里使用一个while循环，判断条件是gap > 1因为我们最后一次排序的时候gap = gap / 3 + 1,保证了gap最后一定为1，就是进行插入排序。其他的和插入排序类似，只不过是把插入排序中的1换成了gap，因为我们可以从上面的图中得到，gap是几，每组数的两个数直接相对位置就差几。
2.3选择排序
选择排序的基本思想:每一次从待排序的数据中选出最小(最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
我们先来看看选择排序的代码:
void SelectSort(int* a, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
int mini = begin, maxi = begin;
for (int i = begin + 1; i <= end; i++)
{
if (a[i] < a[mini])
{
mini = i;
}
if (a[i] > a[maxi])
{
maxi = i;
}
}
Swap(&a[begin], &a[mini]);
if (maxi == begin)
maxi = mini;
Swap(&a[end], &a[maxi]);
begin++;
end--;
}
}我们先选择一个起始位置，都是begin，然后从begin + 1位置依次遍历，找到最小的和最大的数，把最小的数放到左边，把最大的数放到右边即可，这是单趟排列。但是我们要注意，如果恰巧此时最大数的位置和begin重叠了，那么我们此时交换了begin位置和mini位置数据，最大的数就被交换到了mini出，如果在交换，我们将把最小的数据放到最右边。所以如果存在maxi == begin的情况，我们要及时更新maxi的位置。
2.4堆排序
堆排序是利用建堆的思想来排序，升序建大堆，降序建小堆。为什么呢，拿小堆来举例，小堆的根位置也就是起始位置一定是整组数中最小的，然后我们把该位置和最后一个位置的数进行交换，再把根位置的数据按照小堆向下调整，就可以找到次小的数据，依次类推，就可以实现降序，大堆也是如此。
我们来看看堆排序的代码:
void HPSort(int n, int* a)
{
for (int i = (n - 2) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
for (int i = n - 1; i >= 0; i--)
{
Swap(&a[0], &a[i]);
AdjustDown(a, i, 0);
}
}堆排序的代码十分简单，我们从第一个非叶子节点开始建堆(此处以小堆为例),不断往前，最终就建好了小堆，然后从最后的数据开始，不断和堆顶数据交换，交换之后向下调整，我们就排好降序了，升序就建大堆，思想都是一致的。
2.5冒泡排序
冒泡排序作为第一个学习的排序，它的思想就是最外层循环是冒的趟数，里层循环来比较，最终单趟把最大的数冒到最后面。
我们来看看冒泡排序的动图:
一趟下来，没有被排序的数据中最大的就会被冒到最后面,下面是代码:
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n-1; i++)
{
int flag = 0;
for (int j = 0; j < n-i-1; j++)
{
if (a[j + 1] < a[j])
{
Swap(&a[j+1], &a[j]);
flag = 1;
}
}
if (flag == 0)
break;
}
}因为最终只剩下一个数，那么该数肯定就是最小的，也不用继续排序了，所以我们只需要冒n-1次，里层循环每次从0开始，没冒完一次就减一，所以我们减i即可。这里有个flag初始为0，然后如果我们没有进行交换操作，也就是已经排好序了，那么我们的flag就一直为0，此时不用再排序，直接break就好。
2.6归并排序
归并排序是建立在归并操作上的一种有效的排序算法，该算法采用了分治的思想，将已经有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序，最终合成一个有序的顺序。
下面我们来看看归并排序的动图:
本质就是拆分成最小，最小为一个数，一个数我们认为是有序的，然后两两归并，四四归并等等，最终就得到了排好序的顺序。
下面是归并排序的代码:
void _MergeSort(int* a, int* tmp, int left, int right)
{
if (left >= right)
return;
int mid = (left + right) / 2;
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
_MergeSort(a, tmp, begin1, end1);
_MergeSort(a, tmp, begin2, end2);
int i = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if(a[begin1] < a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
}
void MergeSort(int* a, int left, int right)
{
int* tmp = (int*)malloc(sizeof(int) * (right - left + 1));
if (tmp == NULL)
{
perror("malloc fail");
return;
}
_MergeSort(a, tmp, left, right);
free(tmp);
tmp = NULL;
}首先我们需要开一个大小和a数组相同的tmp数组，然后对a数组不断递归到最小单元为止，即只有一个数据，然后进行11归并，11归并完之后，进行22归并...，每单次归并完之后都要把该区间段的数据拷贝到a数组里面去，因为归并的位置不一定都从起始位置开始，因此我们都加上了left。当存在4 3这种数据个数不一样的时候，我们最后还需再进行while循环，把剩下的数直接放到数组的后面即可，因为对于升序来说，剩下的数都是比前面数大。
以上均是学习过程中的理解写出来的笔记，如果有任何错误，还请各位同学批评指正！
