- 排序 -- 选择排序、冒泡排序和堆排序
- 一、选择排序
- 1.排序思想
- 2.代码示例
- 3.特性总结
- 二、冒泡排序
- 1.排序思想
- 2.代码示例
- 3.特性总结
- 二、堆排序
- 1.排序思想
- 2.代码示例
- 3.特性总结
- 总结
一、选择排序 1.排序思想
每次从序列中选出最小（或最大）的数据，放在整个序列的起始位置，直到全部序列的元素都排完。
代码如下：
//交换
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
void SlectSort(int* a, int sz)
{
assert(a);
int begin = 0;
int end = sz - 1;
while (begin < end)
{
//单躺排序：每次选取最大和最小两个元素进行交换
int mini = begin;//最小元素的下标
int 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]);
//如果begin和maxi重叠，需要修正一下maxi
//这种情况是begin和maxi都指向同一个数，此时mini先发生交换，mini和begin位置的数就发生了交换，导致maxi指向的就不是最大的数了，
//最大的数被换到了mini的位置，所以要修正
if (begin == maxi)
{
maxi = mini;
}
Swap(&a[end], &a[maxi]);
begin++;
end--;
}
}
3.特性总结
1.直接选择排序的效率较低；
2.时间复杂度：O(N^2);
3.空间复杂度：O(1);
4.稳定性：不稳定。
当出先上图第二行这种情况时，最小的数1会被换到序列开头，和4交换，那么两个4之间的相对顺序就会发生改变，所以不稳定。
冒泡排序的思想：将较大的数向序列的尾部移动，将较小的数向序列的头部移动，每次单躺排序都能将当前序列中最大的数沉底，最终形成有序序列。
代码如下：
//交换
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
void BubbleSort(int* a, int sz)
{
for (int i = 0; i < sz - 1; i++)
{
//单躺排序
int flag = 0;//交换标志
for (int j = 0; j < sz - i - 1; j++)//将相邻两数中较大的数放到后面
{
if (a[j] > a[j + 1])
{
Swap(&a[j], &a[j + 1]);
flag = 1;
}
}
if (flag == 0)//如果本次单躺排序为发生交换，则说明整个序列已经有序，跳出循环
{
break;
}
}
}
3.特性总结
1.冒泡排序是一种相对简单易理解的排序；
2.时间复杂度：O(N^2)；
3.空间复杂度：O(1)；
4.稳定性：稳定。
堆排序的基本思想是：利用堆的特性，堆一定是完全二叉树，小堆的父亲节点一定小于等于孩子节点，大堆的父亲节点一定大于等于孩子节点，建好堆后，就可以选出最大或最小的数出来，进行排序。
排升序：建大堆
排降序：建小堆
原因：排升序如果建小堆，第一次建堆后，取出最小的数，剩下的数关系就乱了，还需要继续建堆，时间复杂度为O(N^2)，效率低，没有利用到堆的优势；如果建大堆，每次建堆后将最大的数取出来，和数组中最后一个数据进行交换，然后最大的数不看做堆的一部分，这时只需再向下调整一次，就可以选出次大的数，时间复杂度为O(N * logN)。
代码如下：
向下调整算法：
//交换
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//堆排序
//向下调整算法
void AdjustDown(HPDataType* a, int size, int parent)
{
int child = parent * 2 + 1;
while (child < size)
{
//选出左右孩子中大的那一个
if (a[child + 1] > a[child] && (child + 1 < size))
{
++child;
}
//孩子跟父亲比较
if (a[child] > a[parent])
{
Swap(&a[parent], &a[child]);
parent = child;
child = child * 2 + 1;
}
else
{
break;
}
}
}
向上调整算法：
void AdjustUp(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)//孩子到根节点是最后一个结点
{
if (a[child] > a[parent])//孩子大于父亲就交换，这是建大堆
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (parent - 1) / 2;
}
else
{
break;
}
}
}
堆排序：
//排升序：建大堆
//排降序：建小堆
void HeapSort(int* a, int n)
{
//建堆方式1：每次插入都向上调整
//O(N * logN)
//for (int i = 0; i < n; i++)
//{
// AdjustUp(a, i);
//}
//建堆方式2：每次插入都向下调整
//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--;
}
}
3.特性总结
1.堆排序使用堆来选最大或最小的数，效率高了很多；
2.时间复杂度：O(N * logN)；
3.空间复杂度：O(1)；
4.稳定性：不稳定。
总结
本文简单介绍了三种排序方式：选择排序、冒泡排序和堆排序。
