以下所有排序方法均以排升序为例
一.插入排序
1.直接插入排序
1>方法介绍：假定前n个数据有序，将第n+1个数据依次与前n个数据相比，若比第i个数据小且比第i-1个数据大则插入两者之间
2>时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定
3>代码实现：
//插入排序
void InsertSort(int* a, int n)
{
//在前n个数据有效情况下，将第n+1个数据往前面插入，并保持有序
for (int j = 1; j < n; j++)
{
for (int i = j; i > 0; i--)
{
if (a[i] < a[i - 1])
{
Swap(&a[i], &a[i - 1]);
}
}
}
}
补：当数据量非常大时，直接插入排序的效率会大大降低，这时我们可以采用每次相差gap个数据进行插入排序，依次减小gap，直至gap==1,可以提高效率，这就是所谓的希尔排序
2.希尔排序
1>方法介绍：
1)预排序+直接插入排序
先选定一个gap,从第一个数据开始，按gap进行跳隔分组，对区间端点处的数据进行插入排序，依次向后进行gap间隔分组，直至遇到和第一次分组重合的元素；再减小gap的数值，重复上述操作，直至gap==1(最后依次相当于直接插入排序，不过此时数组已经接近有序，效率会大大提高)
2)对于gap的确定：大量实现表明，gap=gap/3+1最为合适，+1是为了保证最后一次gap==1
2>时间复杂度：O(N^1.3)
注：不同的书中对于希尔排序的时间复杂度描述不一样，读者记住该数值即可
空间复杂度：O(1)
稳定性：不稳定
3>代码实现：
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
//改变每次跳的间隔，不断精细化
gap = gap / 3 + 1;
//所有分组
for (int j = 0; j < gap; j++)
{
//仅针对一种划分方法
for (int i = j; i < n - gap; i += gap)
{
if (a[i] > a[i + gap])
{
Swap(&a[i], &a[i + gap]);
}
}
}
}
}二.选择排序
1.选择排序
1>方法介绍：在每一次遍历数组时找出最大值和最小值，分别放在首尾，逐渐向中间逼近
2>时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定
3>代码实现：
//选择排序
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while (begin <= end)
{
int mini = begin;
int maxi = begin;
//寻找最大值，最小值的下标
for (int i = begin+1; i <= end; i++)
{
if (a[mini] > a[i])
{
mini = i;
}
if (a[maxi] < a[i])
{
maxi = i;
}
}
Swap(&a[begin], &a[mini]);
//防止出现begin处的值被使用两次的情况
if (begin == maxi)
{
maxi = mini;
}
Swap(&a[end], &a[maxi]);
begin++;
end--;
}
}2.堆排序
1>方法介绍：
1)利用数组中的数据建大堆，交换最后一个数据与第一个数据进行调整，使前n-1个数据仍为大堆，重复操作
2)利用数组中的数据建大堆的方法：利用向下调整法(具体可参考小编二叉树的顺序结构的博客)，从非叶子节点的最后一个父节点开始向下调整
2>时间复杂度：O(N*logN)
空间复杂度：O(1)
稳定性：稳定
3>代码实现：
void AdjustDown(int* a,int size, int parent)
{
int child = parent * 2 + 1;
while (child < size)
{
if ((child+1)<size && a[child] < a[child + 1])
{
child++;
}
if (a[parent] < a[child])
{
Swap(&a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HeapSort(int* a, int n)
{
//建大堆
for (int i = (n-1-1)/2; i >=0 ; i--)
{
AdjustDown(a, n, i);
}
int end = n - 1;
while (end>0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
end--;
}
}三.交换排序
1.冒泡排序
1>方法介绍：两两比较，将大数沉底，依次进行，直至有序
2>时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定
3>代码实现：
void BubbleSort(int* a, int n)
{
for (int j = 0; j < n; j++)
{
int flag = 0;
for (int i = 0; i < n - j-1; i++)
{
if (a[i] > a[i + 1])
{
Swap(&a[i], &a[i + 1]);
flag = 1;
}
}
if (flag == 0)
{
break;
}
}
}2.快排序
1>方法介绍：
1）选定左边的数据为key，定义Left,Right两个下标，先让R先走，如果找到比key小的数据则停下来，再让L走，如果找到比key大的数据则停下来，交换这两个数据，再重复操作，直至L与R相遇，交换相遇位置的数据(一定比key小)和key。此时key左边的数据全部比key小，右边的数据全部比key大，对key左边和右边的两个数组再进行上述操作(递归实现)，若数组中只有一个数据或L大于R则停下来
2）优化1：若数组为逆序排列，则只进行右侧的递归展开，若层数太多会导致栈溢出，为了避免逆序的情况，我们可以对key的取值做文章：要么随机取key,但随机性太大，pass；要么取左中右三者中居中的数据,与左边数据交换，仍让左边数据为key
3）优化2：当数组中的数据量过少时，利用递归排序的代价太大，此时我们可以选用其他方法来排这些数据，以提高性能
2>关于相遇位置的数据小于key的解释：
若最后是L遇R：由于R先走，并且R找到比key小的数据才停下来，故R停下来的位置处的数据小于key,此时L走一直未找到比key大的数据直至与R相遇，所以相遇位置的数据小于key
若最后是R遇L：由于R先走，在最后一次R走前，L找到比key大的数据，R找到比key小的数据，两者进行交换，故L所在位置的数据是比key小的数据，之后R向前走，一直为找不到比key大的数据，直至与L相遇，所以相遇位置的数据小于key
综上所述：相遇位置的数据必定小于key
3>时间复杂度：O(N*logN)
空间复杂度：O(logN)
稳定性：不稳定
4>代码实现：
int GetMidi(int* a,int left, int right)
{
int mid = (right + left) / 2;
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[right] < a[left])
{
return left;
}
else
{
return right;
}
}
else
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[right] > a[left])
{
return left;
}
else
{
return right;
}
}
}
//当数组为逆序时，递归层次太多，可能造成栈溢出，导致性能低下
//解决方法：1.将key取头，尾，中间三者中居中的值(三数取中)
// 2.进行随机选取key(该法不确定性太大，不推荐)
//当数据太少用递归进行排序会浪费空间，故可以在最后10个数据排序时改用其他方法排序，以提高性能
void QuickSort(int* a, int left,int right)
{
if (left >= right)
{
return;
}
//小区间优化
if ((right - left + 1 ) < 10)
{
InsertSort(a+left, right - left + 1);
}
else
{
int midi = GetMidi(a, left, right);
Swap(&a[midi], &a[left]);
int keyi = left;
int begin = left;
int end = right;
while (begin < end)
{
//右边先走，找比key小的值
while (begin < end && a[keyi] < a[end])
{
end--;
}
//左边后走，找比key大的值
while (begin < end && a[keyi] > a[begin])
{
begin++;
}
//交换左右值
Swap(&a[begin], &a[end]);
}
//将相遇位置的数据与key位置的数据交换
Swap(&a[begin], &a[keyi]);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
}四.归并排序
1.方法介绍：
1)按后序遍历的思想将数组分成若干份左右小区间
2)将数组细分成若干小组，让他们在自己的小组内有序，然后再让它与相邻的组别有序，依次向上归并
3)开辟一个新数组用于盛放已排序的数据，在一次归并后需将tmp中的数据拷贝回原数组中，以保证下一组更大区间的数据归并时是有序的
2.时间复杂度：O(N*logN)
空间复杂度：O(N)
稳定性：稳定
3.代码实现：
void _MergeSort(int* a, int* tmp, int begin, int end)
{
if (begin>=end)
return;
int midi = (begin + end) / 2;
_MergeSort(a, tmp, begin, midi);
_MergeSort(a, tmp, midi+1, end);
//归并
//[begin,mid],[mid+1,end]
int begin1 = begin, end1 = midi;
int begin2 = midi + 1, end2 = end;
int i = 0;
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 + begin, tmp + begin, sizeof(end - begin + 1));
}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
_MergeSort(a, tmp, 0, n - 1);
free(tmp);
tmp = NULL;
}
注：对于快排和归并还有非递归的方法，考虑到篇幅，小编就不在这篇博客中介绍，如果有兴趣的小伙伴可以看看小编的下一篇博客了解以下哟
