文章目录
- 冒泡排序
- 插入排序
- 希尔排序
- 选择排序
- 堆排
- 快速排序
- 递归版
- 前后指针版
- 用栈实现快排
- 归并排序
- 用循环方式归并
冒泡排序
冒泡排序应该是最先学到的一种排序算法，也是最简单的一种排序算法。
思路就是，从最前面开始两两比较大的放后面。但是要注意一个问题每走一趟就把这趟最大的放后面了，所以要控制一下单趟和多趟。这里用两个循环解决。
//冒泡排序
void BubbleSort(int* a, int n)
{
for (int j = 0; j < n; j++)
{
// 单趟
int flag = 0;
for (int i = 1; i < n - j; i++)
{
if (a[i - 1] > a[i])
{
swap(&a[i - 1], &a[i]);
flag = 1;
}
}
if (flag == 0)
{
break;
}
}
}
时间复杂度：最坏情况：O(N^2)
最好情况：O(N)
空间复杂度：O(1)
插入排序
先思考单趟，设定end位置的下一个位置为tmp，并把tmp位置的值用一个临时变量存起来。然后进入循环，如果tmp的值小于end位置的值就让end位置的值覆盖end+1位置的值，让end的值往后走，end下标位置–。如果tmp位置的值大于end位置的值就把tmp位置的值放入end位置的后面，这里的循环判断条件是end>0。这是单趟的思路，然后用for循环让end从下标为0位置开始，用这个单趟的思路走多趟进行排序。
//插入排序
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;
}
}
时间复杂度：最坏情况下为O(NN)，此时待排序列为逆序，或者说接近逆序
最好情况下为O(N)，此时待排序列为升序，或者说接近升序。
空间复杂度：O(1)*
希尔排序
希尔排序跟插入排序有异曲同工之处，但是希尔排序是对插入排序的优化，在希尔排序中用到了gap，gap值随着排序的进行会减小当gap>1时都是预排序。当gap==1时数组就接近有序了，然后在对这个序列进行一次插入排序这时排序就很快了。
每次走gap步其他和插入排序思路一样。要注意一下i的范围的取值，i要小于n-gap，如果i超过了n-gap走到了n-gap后面的位置i再加gap的话就越界了。i++多组并行走gap步优化预处理的过程。随着gap值的变化gap会越来越小，gap为1时预处理完毕，其实gap为1时就相当于插入排序。
//希尔排序
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 0)
{
gap = gap / 3 + 1;
}
//进入循环多组并行
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = i + gap;
while (end > 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end--;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
时间复杂度：O(n^(1.3-2))
选择排序
定义begin位置也就是下标为0位置为最大和最小位置。从begin+1位置开始遍历数组，如果有值大于maxi位置的值，就赋这个位置下标为最大位置。如果有值小于mini位置的值，就赋这个位置下标为最小位置。然后把最大值与之前end位置的值交换位置，最小位置的值与之前begin位置的值交换位置。这次交换完之后，因为while循环判断条件是begin<end继续重复上面步骤。
//选择排序
void SelecSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
int maxi = begin;
int mini = begin;
for (int i = begin + 1; i < n; i++)
{
while (a[i] > a[maxi])
{
maxi = i;
}
while (a[i] < a[mini])
{
mini = i;
}
}
swap(&a[begin], &a[mini]);
if (begin == maxi)
{
maxi = mini;
}
swap(&a[end], &a[maxi]);
begin++;
end--;
}
}
时间复杂度为O(n^2)
堆排
堆排在之前二叉树中的文章中有具体实现步骤，下面是二叉树的文章：
添加链接描述
//向上调整建堆
void AdjustDown(int* a, int n, int parent)
{
// 先假设左孩子小
int child = parent * 2 + 1;
while (child < n) // child >= n说明孩子不存在，调整到叶子了
{
// 找出小的那个孩子
if (child + 1 < n && a[child + 1] > a[child])
{
++child;
}
if (a[child] > a[parent])
{
swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//堆排
void HeapSort(int* a, int n)
{
// 向下调整建堆 O(N)
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
// O(N*logN)
int end = n - 1;
while (end > 0)
{
swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
}
}
快速排序
递归版
选出一个key作为其他值比较的值，一般是最左边或者最右边的值。把最左边的下标和最右边的下标定义为begin和end。左边找大于key的值右边找小于key的值。然后让左边找到的值与右边找到的值交换位置，如果不大于key的值或者不小于key的值左边继续往右走右边继续往左走。当begin和end相遇的时候，把相遇位置的值与key位置的值交换位置。然后把key的位置换到begin和end相遇位置，这样这个区间就成[left,key1]key[key+1,right]。接着让左区间和右区间继续递归。
void QuickSort1(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int keyi = left;
int begin = left;
int end = right;
while (begin < end)
{
//右边找小
while (begin<end && a[end] > a[keyi])
{
end--;
}
//左边找大
while (begin < end && a[begin] < a[keyi])
{
begin++;
}
swap(&a[begin], &a[end]);
}
//把keyi位置换到中间
swap(&a[keyi], &a[end]);
keyi = begin;
//递归接着进行排序
QuickSort1(a, left, keyi - 1);
QuickSort1(a, keyi + 1, right);
}
}
如果这个要排序的数组非常长，end要找比key小的但这个数组是升序的。end就得从这个数组的最右边走很长一段距离才能找到小。这时我们可以用三数取中来优化算法。
三数取中就是找到left的值和right的值和left和它俩中间的值，比较谁是中间值。中间值的当key。
//三数取中
int GetMidi(int* a, int left, int right)
{
int midi = (left + right) / 2;
if (a[left] < a[midi])
{
if (a[midi] < a[right])
{
return midi;
}
else if (a[left] < a[right])
{
return right;
}
else
{
//a[left]>a[right]
return left;
}
}
else //(a[left]>a[midi])
{
if (a[right] < a[midi])
{
return midi;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}
小区间优化：
这里这个递归是和而二叉树类似的，最下面一层的值占整个二叉树的%50，有好多就浪费掉了。当我们递归到一定程度时，可以采用插入排序来进行优化。
if ((right - left + 1) < 5)
{
InsertSort(a + left, right - left + 1);
}
优化后代码：
void QuickSort1(int* a, int left, int right)
{
if (left >= right)
{
return;
}
if ((right - left + 1) < 5)
{
InsertSort(a + left, right - left + 1);
}
else
{
//三数取中
int midi = GetMidi(a, left, right);
swap(&a[left], &a[midi]);
int keyi = left;
int begin = left;
int end = right;
while (begin < end)
{
//右边找小
while (begin<end && a[end] > a[keyi])
{
end--;
}
//左边找大
while (begin < end && a[begin] < a[keyi])
{
begin++;
}
swap(&a[begin], &a[end]);
}
//把keyi位置换到中间
swap(&a[keyi], &a[end]);
keyi = begin;
//递归接着进行排序
QuickSort1(a, left, keyi - 1);
QuickSort1(a, keyi + 1, right);
}
}
前后指针版
选出一个key，一般是最左边或是最右边的。prev指针指向序列开头，cur指针指向prev+1。若cur指向的内容小于key，则prev先向后移动一位，然后交换prev和cur指针指向的内容，然后cur指针++；若cur指向的内容大于key，则cur指针直接++。如此进行下去，直到cur到达end位置，此时将key和++prev指针指向的内容交换即可。经过一次单趟排序，最终也能使得key左边的数据全部都小于key，key右边的数据全部都大于key。
然后也还是将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作
int QuickSort2(int* a, int left, int right)
{
int key = left;
int mind = GetMidi(a, left, right);
swap(&a[mind], &a[left]);
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
if (a[cur] < a[key] && ++prev != cur)
swap(&a[prev], &a[cur]);
cur++;
}
swap(&a[key], &a[prev]);
QuickSort2(arr, begin, keyi - 1);
QuickSort2(arr, keyi + 1, end);
}
用栈实现快排
把区间放入栈中，注意栈是先进后出所以先入right后入left。然后取出这个区间进行进行排序，找到key的位置。[left,key-1]key[key+1,right],让右区间入栈然后让左区间入栈，取出左区间进行排序找到新的key然后重复上述过程，类似递归的思想。左区间完了搞右区间。
int QuickSort2(int* a, int left, int right)
{
int key = left;
int mind = GetMidi(a, left, right);
swap(&a[mind], &a[left]);
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
if (a[cur] < a[key] && ++prev != cur)
swap(&a[prev], &a[cur]);
cur++;
}
swap(&a[key], &a[prev]);
return prev;
}
#include"Stack.h"
//用栈实现快排
void QuickSortNonR(int* a, int left, int right)
{
ST st;
STInit(&st);
STPush(&st, right);//9
STPush(&st, left);//0
while (!STEmpty(&st))
{
int begin = STTop(&st);
STPop(&st);//0
int end = STTop(&st);
STPop(&st);//9
//[left,key-1]key[key+1,right]
int key = QuickSort2(a, begin, end);
if (key + 1 < right)
{
STPush(&st, right);
STPush(&st, key + 1);
}
if (left < key + 1)
{
STPush(&st, key + 1);
STPush(&st, left);
}
}
STDestroy(&st);
}
归并排序
创建一个tmp数组，把之后归并的数据先放入这个tmp数组中然后再放入原数组中。把begin到end区间找中间值分割开来。int mid = (begin + end) / 2; //[begin,mid][mid+1,end]。
然后让两个数组进行比较，小的放到tmp数组中。有可能其中一个数组比较完之后另一个还有值，所以得判断一下，把剩余的值放入tmp中。
这个也需要递归。
//归并排序
void _MergeSort(int* a, int* tmp, int begin, int end)
{
if (begin >= end)
return;
int mid = (begin + end) / 2;
//[begin,mid][mid+1,end]
_MergeSort(a, tmp, begin, mid);
_MergeSort(a, tmp, mid + 1, end);
int begin1 = begin;
int end1 = mid;
int begin2 = mid + 1;
int end2 = end;
int i = begin;
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, (end - begin + 1) * sizeof(int));
}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc error");
return;
}
_MergeSort(a, tmp, 0, n - 1);
free(tmp);
tmp == NULL;
}
用循环方式归并
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
// gap每组归并数据的数据个数
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
// [begin1, end1][begin2, end2]
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
// 第二组都越界不存在，这一组就不需要归并
if (begin2 >= n)
break;
// 第二的组begin2没越界，end2越界了，需要修正一下，继续归并
if (end2 >= n)
end2 = n - 1;
int j = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[j++] = a[begin1++];
}
else
{
tmp[j++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[j++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[j++] = a[begin2++];
}
memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
}
printf("
");
gap *= 2;
}
free(tmp);
tmp = NULL;
}
这里先一一归并然后两两归并然后四四归并，依此类推。gap每组表示归并数据的个数，比方说这个gap组中有两个值，就是这两个值进行归并，这gap组中有四个值，就两两归并。i代表每组的归并的起始位置。每循环一次就要让gap*2，这样才能满足每组归并数据的个数。
这里有一个问题需要注意：
第二组都越界不存在，这一组就不需要归并
if (begin2 >= n)
break;
第二的组begin2没越界，end2越界了，需要修正一下，继续归并
if (end2 >= n)
end2 = n – 1;
