一、选择排序
选择排序的基本思想是每次循环将最大的元素和最小的元素选出来放在两端，走过整个数组后就可以完成排序。
从而我们需要定义一个从左开始走的循环变量left，和从右开始走的循环变量right，还需要用于比较的最小值，最大值。
每次我最小值最大值的从left先开始，遍历数组，找到比最小值还小的就更新，同理更新最大值。
void SelectSort(int* a, int n)
{
//每次都选出最小的元素和最大的元素
//定义一个left和right
int left = 0;
int right = n - 1;
while (left < right)
{
int min = left;
int max = right;
for (int i = left;i <= right;i++)
{
if (a[i] < a[min])
{
//找到比min还小的就更新
min = i;
}
if (a[i] > a[max])
{
//找到比max大的就更新
max = i;
}
}
swap(&a[left], &a[min]);
//这个地方需要注意，我们上面交换了left和最小值，如果说最大值所在的位置就是left，这会导致我们下面交换失败，所以需要判断一下。
if (max == left)
{
max = min;
}
swap(&a[right], &a[max]);
left++;
right--;
}
}
这个算法的时间复杂度是O（N^2），空间复杂度是O(1)。
二、冒泡排序
冒泡排序是一种交换排序，从头开始遍历，如果前一个元素比后一个元素大，就交换。单次循环后就可以把最大的元素排到最后，在考虑前n-1个元素，再进行一次排序，不断进行下去，就可以排完整个数组。
int exchange = 0;
void MergeSort(int* a, int n)
{
//先考虑单趟的排序
//每次都把最大的冒到后面
for (int j = 0;j < n;j++)
{
for (int i = 0;i < n - j -1;i++)
{
if (a[i] > a[i + 1])
{
swap(&a[i], &a[i + 1]);
exchange = 1;
}
}
if (0 == exchange)
{
break;
}
}
}
定义全局变量exchange的目的是用于判断单次循环是否进行了交换，如果没有进行交换，那么exchange一直都会是0，说明此时数组已经有序了，直接break跳出循环即可。
这个算法的时间复杂度也是O（N^2）,空间复杂度O（1）。
三、快速排序
这个排序的性能是所有排序中最好的，这个算法会以三种方法实现，后两种方法主要是对第一种方法的改进。
快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法。它的实现方式实际上和二叉树的前序遍历十分相似，后面解释。 其基本思想是： 任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右 子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止 。 我们先定义用于遍历数组的变量left和right，每次都让他们从begin和End的地方开始，当然最开始从数组的头和尾开始。 依照我们上面说过的，左边做基准值让右边先走，右边的变量去找比基准值小的，左边的变量去找比基准值大的数，找到了就交换。 循环完就让他们停下来的位置和基准值交换。这样每次循环都能保证大的数在基准值的右边，小的数在基准值的左边。 然后我们去递归基准值的左区间和右区间，不断递归就可以排完。void QuickSort(int* a, int begin,int End)
{
//先选取一个基准值，还有left，right 让left和right分别往后走。但是选取左为基准值的时候要让右先走。
//这样保证了最后停下来的位置的键值一定是比基准值小的，否则交换无意义。
if (begin >= End)
{
return;
}
int left = begin;
int Basevalue = left;
int right = End;
while (left < right)
{
while (left < right && a[right] >= a[Basevalue])
{
right--;
}
while (left < right && a[left] < a[Basevalue])
{
left++;
}
//
swap(&a[left], &a[right]);
}
swap(&a[Basevalue], &a[left]);
QuickSort(a, Basevalue, left - 1);
QuickSort(a, left + 1, End);
}
