后续的几篇博客是对看完《啊哈算法》后的一个复习整理，书中对各类算法有一个思想和基本代码框架的介绍，对于算法们进一步的应用，相关的题目没有涉及。博客内容比较浅显。后续深入学习的，另会涉及题目
简易桶排序#include
int main()
{
int a[1000] = {0};
int t, i, j;
int n;
scanf("%d", &n); //输入有多少个数需要排序
for (i = 0; i < n; i++)
{
scanf("%d", &t);
a[t]++;
}
for (i = 0; i < 1000; i++)
for (j = 0; j < a[i]; j++)
printf("%d ", i);
return;
}
巧妙之处：存储数的不是数组元素的值，而是数组元素的角标，元素的值用来记录该数出现了几次。
不足之处：如果需要排序的数非常大，那空间复杂度就很差，容易溢出；另外，因为是遍历整个数组，所以有很多无效遍历；最严重的是，如果需要排序的数为浮点数或者负数，上述排序就不适用了。
易错之处：如果说数的范围都在0~1000，设1000为m，一共有n个数要排序。那么它的时间复杂度不是O(nm)，而是O(n+m)，并不是每一次外循环都会完全遍历n次内循环，内部只遍历n次。
真正的桶排序并没有这么简单，它就能处理元素为浮点数的情况，此处不提。
冒泡排序_bubblesort#include
int Swap(int *e1, int *e2)
{
int temp = *e1;
*e1 = *e2;
*e2 = temp;
}
int main()
{
int a[1000] = {0};
int n, i, j;
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
for (i = 0; i < n - 1; i++)//只用排n-1次，最后只剩下未归位的角标为0的第一个元素，已经排好。
for (j = 0; j < n - 1 - i; j++)//别少-i，因为从后往前数共i个元素都是排好序的，不用遍历
{
if (a[j] > a[j + 1])
Swap(&a[j], &a[j + 1]);
}
for (i = 0; i < n; i++)
printf("%d ", a[i]);
return 0;
}
特征：双重for循环遍历，初学较为常见，时间复杂度为O(N^2)，因为是用数组元素的值来存储数值，所以可以对浮点型数据排序。
缺点：时间复杂度太高，大部分题目会超时。
描述：Donald E. Knuth（一图灵奖大佬）：“冒泡排序除了他迷人的名字和导致某些有趣的理论问题这一事实之外，似乎没有什么值得推荐的。”
冒泡冒泡，就想水中的气泡从水底往水面上浮一样（排序的数从前头往后头走，最终确定最后的元素的位置。）
快排_quicklysort 1.0#include
#include
int a[100001];//宏定义
int n;
void quicklysort(int left, int right)//两个哨兵的位置
{
if (left > right)//想想递归的尽头是如何结束的
return;
int i, j, t, temp;
i = left;//i哨兵在左
j = right;//j哨兵在右
temp = a[left];//设定基准数，为输入数字串的最左边的数
while (i != j)//哨兵未相遇
{
while(a[j] >= temp && j > i)//哨兵j先动,先判断，再移动
j--;
while (a[i] <= temp && j > i)//哨兵i后动，也是先判断，再移动
i++;
if (i < j)//交换哨兵找到的不符合顺序的两值
{
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
a[left] = a[i];//运行到这两步说明哨兵已经碰面，找到了适中的位置，将基准数与其交换
a[i] = temp;
quicklysort(left, i - 1);//重点！递归调用，将基准数以左的数重新设立基准数和哨兵，进行一系列操作。
quicklysort(i + 1, right);//基准数以右的数同理
return;//都进行完了即排序完成！
}
int main()
{
int i;
scanf("%d", &n);//表示后面输入几个数
for (i = 0; i < n; i++)
scanf("%d", &a[i]);//将输入的数存入数组
quicklysort(0, n - 1);//快排
for (i = 0; i < n; i++)
printf("%d ", a[i]); //将排好序的数输出。
printf("\n");
return 0;
}
巧妙之处：1.0的快排在以前的博客中有提到过，运用了递归思想，每一次递归能完成一个数的归位，但它的时间复杂度不同情况下不一样，最坏的时间复杂度是O(N^2)，最优时间复杂度为O(NlogN)，最坏的情况是每一次归位的temp仍在边缘，导致每一次递归只有一边是有效的，另一边left==right无效。最好的情况是每一次temp都能在中间归位，那么两边都能很好的递归。
2.0#include
#include
int p[2];
void Swap(int *e1, int *e2)
{
int temp = *e1;
*e1 = *e2;
*e2 = temp;
}
void partition(int *arr, int left, int right)
{
int p_l = left - 1;
int p_r = right;
int flag = arr[right];
while (left < p_r)
{
if (arr[left] < flag)
Swap(&arr[left++], &arr[++p_l]);
else if (arr[left] > flag)
Swap(&arr[left], &arr[--p_r]);
else
left++;
}
Swap(&arr[right], &arr[p_r]);
p[0] = p_l + 1;
p[1] = p_r;
}
void quicklysort(int *arr, int left, int right)
{
if (left >= right)
return;
// int temp = left + rand() % (right - left + 1);//3.0
//Swap(&arr[temp], &arr[right]);
partition(arr, left, right);
quicklysort(arr, left, p[0] - 1);
quicklysort(arr, p[1] + 1, right);
}
int main()
{
int a[1000];
int n, i;
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
quicklysort(a, 0, n - 1);
for (i = 0; i < n; i++)
printf("%d ", a[i]);
return 0;
}
看上去似乎比1.0复杂，其实框架是一样的，都是递归。而1.0的i，j标兵向中间移动相遇的过程化成了partition部分。这一部分的思想灵活运用了荷兰国旗问题的解法，荷兰国旗问题可以看上一篇博客：
(1条消息) 荷兰国旗问题_Upping.的博客-CSDN博客
2.0比较1.0我们可以发现，因为partition（荷兰国旗）会将符合条件（==num）的数都放在中间，而再次进递归参数有中间（==num）区间的左边界-1，和有边界+1，我们用了p[2]这个数组来存放中间区域的边界，p[0]存放左边界，p[1]存放右边界。
结合1.0每次确定一个数的思想，我们可以类推发现2.0能在某些情况下**一次递归就归位一批数（**当然这些数的值都是相等的），在有一些元素相等的排序中，会比1.0快一些。
3.0如2.0代码process中被注释掉的一段，就是3.0优于前两者的地方。我们会发现，无论是1.0还是2.0都有可能碰到最差情况，即每一次归位的temp都都打在边缘，使得后续一边的递归无效。为什么会出现最差情况？归根结底是选的参照temp的位置都是固定的，如果我们让它随机起来，那么最差情况就是妥妥的概率事件了，不会因题目特意设计的特殊数据而超时。（但不可否认，还是有出现最差情况的可能，但此时的时间复杂度已经不能用最差情况来估计了。
归并排序_mergesort#include
void merge(int *arr, int L, int M, int R)
{
int p1 = L;
int p2 = M + 1;
int i = 0, help[200];
while (p1 <= M && p2 <= R)
help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
while (p1 <= M)
help[i++] = arr[p1++];
while (p2 <= R)
help[i++] = arr[p2++];
for (i = 0; i < R - L + 1; i++)
arr[L + i] = help[i];
}
void sort(int *arr, int L, int R)
{
if (L == R)
return;
int mid = L + ((R - L) >> 1);
sort(arr, L, mid);
sort(arr, mid + 1, R);
merge(arr, L, mid, R);
}
int main()
{
int a[1000];
int n, i;
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
sort(a, 0, n - 1);
for (i = 0; i < n; i++)
printf("%d ", a[i]);
return 0;
}
原来有一篇博客讲了归并排序和小和问题，回去看的时候发现以前因为自己的指针知识有遗漏，导致那段代码有问题，以现在为主。
当思路可以参考原博客：
(1条消息) 归并排序+Master公式+小和问题_Upping.的博客-CSDN博客
这里再次列出求时间复杂度的Master公式：
Master公式：T(N)=aT(N/b)+O(N^d)*
①当d
③当d>logb a时，时间复杂度为O(n^d)
（在上面博客链接里有具体介绍）
我们不难发现，整个归并排序，sort部分第一层递归有两个子问题，分别是排序左边和右边，所以有2T(N/2)，即a=2（两个子问题），b=2（等规模的子问题的规模关系），而其他语句的时间复杂度——即merge过程，为O(2N)，所以d=1=log2 2，即归并排序的时间复杂度为O(NlogN)。
堆排序#include
#include
void Swap(int *e1, int *e2)
{
int temp = *e1;
*e1 = *e2;
*e2 = temp;
}
void siftdown(int *arr, int index, int heapsize)
{
int left = index * 2 + 1;
if (left < heapsize)
{
int largest = left + 1 < heapsize && arr[left + 1] > arr[left] ? left + 1 : left;
largest = arr[largest] > arr[index] ? largest : index;
if (largest == index)
return;
Swap(&arr[largest], &arr[index]);
index = largest;
left = index * 2 + 1;
}
}
void siftup(int *arr, int index)
{
while (arr[index] > arr[(index - 1) / 2])
{
Swap(&arr[index], &arr[(index - 1) / 2]);
index = (index - 1) / 2;
}
}
void heapsort(int *arr, int heapsize)
{
int i;
for (i = heapsize / 2 - 1; i >= 0; i--)
siftdown(arr, i, heapsize);
// for (i = 0; i < heapsize; i++)
// siftup(arr, i);
Swap(&arr[0], &arr[--heapsize]);
while (heapsize > 0)
{
siftdown(arr, 0, heapsize);
Swap(&arr[0], &arr[--heapsize]);
}
}
int main()
{
int a[1000];
int n, i;
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
heapsort(a, n);
for (i = 0; i < n; i++)
printf("%d ", a[i]);
return 0;
}
在堆 *** 作heapify中有siftup和siftdown两种方法，都能将一个无序的堆变成小根堆或者大根堆。以上注释掉的部分是用siftdown转变小根堆，开始这一步骤用heapify会稍微快些。
值得注意的是如果排序要求为升序，初排就为小根堆，让最小的数放在堆顶，然后和堆的最后一个结点交换，heapsize–，即将排好序的数从后往前放，等全部放好后，就是从小到大的顺序了。同理，降序就初排大根堆。
堆排序的时间复杂度也为O(NlogN)。堆排序只是堆结构的基本用法，而heapify是堆的核心思想。后续还会提到。
总结我们再一起来看看这些排序算法的时间复杂度和空间复杂度：
| 算法\复杂度 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 简易桶排序 | O(M+N),M为数据范围 | O(M) |
| 冒泡排序 | O(N^2) | O(N) |
| 快速排序 | 平均O(NlogN),最差(N^2) | O(logN) |
| 归并排序 | O(NlogN) | O(N) |
| 堆排序 | O(NlogN) | O(1) |
需要思考的点：快排的空间复杂度，因为快排中有递归和分治的思想，当计算机计算左边递归时开辟并使用了一块空间，等左边递归完后这块空间会被及时释放，马上又能被右边利用，而不用两边都开辟空间。
还有堆排序，不难发现整个堆排序都是用有限几个变量，也没有用递归。两两找到对方来进行比较都巧妙地依靠了树结构的性质，即父节点等于（子节点-1）/2,左子节点等于父节点*2+1，右子节点等于左子节点+1。所以它的空间复杂度仅为O(1)。
感谢你能看到这里，希望你有所收获，祝好！
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）