常用排序算法（上）

目录

前言：

1.排序的概念及其运用

1.1排序的概念

1.2排序运用

1.3 常见的排序算法 

2.常见排序算法的实现 

 2.1 堆排序

2.1 1 向下调整算法

2.1 2 建堆 

2.1 3 排序 

2.2 插入排序 

  2.1.1基本思想：

2.1.2直接插入排序： 

2.1.3 插入排序实现 

2.3 希尔排序 

2.4 选择排序

  2.4.1基本思想：

2.4.2 直接选择排序:

2 .4.3 选择排序实现

---

前言：

  当我们学到数据结构时，就无法避开算法，排序是一类常见且常用的算法，在日常生活中，我们在网上购物，筛选价格时用到了排序，查看该商品销量的高低时用到了排序，而这些功能都是我们程序员使用排序算法将其转化成代码实现的。既然排序如此重要，我们当然要好好把排序学好了。

1.排序的概念及其运用

1.1排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不断地在内外存之间移动数据的排序。

1.2排序运用

  排序的重要性在前面我们已经讲解，在这里就不再过多赘述。

 

 

1.3 常见的排序算法 

  在学习排序算法之前，我们应该了解常见的排序算法有哪些，排序一般分为插入排序，选择排序，交换排序，归并排序，而细分的话可以分成下面的样子：

2.常见排序算法的实现 

 2.1 堆排序

 堆排序我们在学习二叉树堆时，已经讲过了，将它放在这里，一是复习一遍堆排序，二是将这些排序都总结在一起，方便我们查看。堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

    简单来说，堆排序的算法就是先建一个堆，如果我们要排升序就建大堆，将堆最大的那个数——也就是根节点中的那个数与堆尾交换，这样最大的数就排到最后一位了，此时的数组已经不是堆了，我们使用向下调整算法重新建堆，这样数组中第二大的数就在根结点中了，我们再将它和堆倒数第二个位置的数交换，这样第二大的数就在数组倒数第二的位置了，像这样一种走到根节点，我们也就完成了排序的操作。

2.1 1 向下调整算法

    第一个双亲结点默认是数组中下标为0的位置，我们需要算出它的孩子结点，而公式也个很简单，双亲*2+1就是这个结点的左孩子，双亲*2+2就是这个结点的右孩子。假设我们建的是大堆，双亲结点比孩子结点小就交换，我们默认这棵树是完全二叉树，所以大多数结点都有两个孩子，我们需要选出两个孩子结点中大的那个与双亲结点交换位置，交换完就刷新双亲结点和子节点的下标，而前提是两个结点都在数组中，所以有：

int child = parent * 2 + 1;
//假设左孩子就是要交换的那个孩子
if (child + 1 < n && a[child + 1] > a[child])
{child++;
}
//如果某个结点比左孩子小，而右孩子比左孩子大，
//就让该节点的右孩子与自己交换位置

  我们设置一个循环，如果某个结点的孩子的下标大于等于n，说明我们已经完成了交换，就不进入循环，如果发现这是一个堆，就跳出循环：

void AdjustDown(int* a, size_t n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] > a[child]){child++;}if (a[parent] < a[child]){Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}}

2.1 2 建堆 

 给我们一组无序的数字，我们采用从后往前向下调整的方法来建堆。如果我们将这组数据看成完全二叉树，除了叶子结点，其余的结点都有孩子，也就是说，有几个有孩子结点的结点，这组数据中就有几棵树，我们可以从最后一个有孩子结点的结点开始使用向下调整算法，当走到这棵树的根节点时，就将堆建好了：

    例如这棵树，从9这个结点开始，往前都可以组成一棵树，而如何得到呢，这个也很简单，我们只需要反转计算孩子结点的公式，得到计算双亲结点的公式为（孩子-1）÷ 2 ，假设这棵树有n个结点，这棵树的尾结点为n-1，所以假设我们要得到9这个结点，公式为：（n-1-1）÷2。

得到代码：

for (int i = (size - 1 - 1) / 2; i >= 0; i--)
{AdjustDown(a, size, i);
}

2.1 3 排序 

      建好堆之后，我们就可以排序了，按前面讲的排，得到代码：

//定义一个end方便交换，每次交换完往前走一步
int end = size - 1;
//size为数组大小
while (end > 0)
{Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;
}

 堆排序完整代码：

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void AdjustDown(int* a, size_t n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] > a[child]){child++;}if (a[parent] < a[child]){Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}}

 我们定义一个数组，给一些数测数一下：

int a[] = { 454,24,34,43543,676,67,676,23,1,0 };
size_t size = sizeof(a) / sizeof(int);
HeapSort(a, size);
for (int i = 0; i < size; i++)
{printf("%d ", a[i]);
}

可以看到，一个有序的数组就完成了。

2.2 插入排序 

  2.1.1基本思想：

直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

实际中我们玩扑克牌时，就用了插入排序的思想

2.1.2直接插入排序： 

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移：

直接插入排序的特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

2.1.3 插入排序实现 

     我们定义一个end，在end下标及end之前下标的数都是有序的数，依次从end之后取数据来插入end之前，如果我们要排升序，我们从end+1开始取数据存起来，只要这个数小于end，就让end覆盖end+1，然后让end向前走一位，直到这个数比end下标的数大或者等于这个数，我们让end往前走一位，然后将这个数插入到end+1的位置。以上是一轮插入，要实现插入排序需要让end走遍整个数组，而每次插入都只插入一个数，假设某个数据为n，那么当执行完end=n-2时，这个数组也就有序了，代码展示：

void InsertSort(int* a, size_t n)
{int end;int tmp;for (int i = 0; i < n - 1; i++){end = i;tmp = a[end + 1];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}}

我们准备一个无序数组，调用插入排序：

int a[] = { 9,8,7,6,5,4,3,2,4,5,98,43,67,879,4543,687686,676,1,0 };
size_t size = sizeof(a) / sizeof(a[0]);
InsertSort(a, size);

来看结果：

调用插入排序后，这个数组就被排成了升序。

2.3 希尔排序 

     希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。本质上，希尔排序是对插入排序的优化。

 

     先对一组数进行预排序，再对这组数据进行插入排序，这就是希尔排序。而上面的操作就是对这组数据进行预排序，预排序可以让一个很大或者很小的数更快走到它排序之后的位置，假如gap=5，我们需要排升序，整个数组中最大的数只需要走两次就可以走到最后一个位置。事实上，插入排序就是希尔排序当gap为1时，一个数一次只能走1步。因此，我们得出：gap越大，大数越快走到后面，小数越快走到后面，越不接近有序。为什么呢？因为当gap=1时，执行这个程序，该组数据就有序了，所以：gap越小，大数越满走到后面，小数越慢走到前面，数组却越接近有序。

希尔排序的特性总结：
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定：

                                                                      数据结构-用面相对象方法与C++描述》--- 殷人昆 

4.稳定性：不稳定

2.4 选择排序

  2.4.1基本思想：

     每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

2.4.2 直接选择排序:

（1）在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素
（2）若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
（3）在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

2 .4.3 选择排序实现

   在我们的介绍中，选择排序就是我们多次遍历一个数组，如果要排升序，那么第一次遍历出来最小的数放到第一位，第二次遍历出来最小的数放到第二位，依次遍历完整个数组就完成了排序。我们可以对其优化一下，定义一个max和min，也就是每一次遍历都选出最小的数和最大的数，最小的数放在最前面，最大的数放在最后面，依次执行，像这样优化的速度是普通选择排序的2倍。

    定义一个起始位置的下标begin和末尾位置的下标end，接着是max和min，从begin+1的位置开始往前走，让max，min下标的数与整个数组的其他数比较，只要有比max大的数就让那个数成为max，只要有比min小的数就让这个数成为min，遍历完一遍后，让begin下标的数和min下标的数交换，接着让end下标的数和max下标的数交换，这样最大的数和最小的数都排好了，让begin往前走一步，end往后走一步，做完这些后，让max和min重新从begin们开始走，代码实现：

void SecletSort(int* a, size_t n)
{int begin = 0, end = n - 1;int maxi = begin;int mini = begin;while (begin < end){mini = begin;maxi = begin;for (int i = begin + 1; i <= end; i++){if (a[i] > a[maxi]){maxi = i;}if (a[i] < a[mini]){mini = i;}}Swap(&a[mini], &a[begin]);if (begin == maxi)maxi = mini;Swap(&a[maxi], &a[end]);begin++;end--;}}

 依旧是一组无序的数，调用选择排序：

int a[] = { 9,8,7,6,5,4,3,2,4,5,98,43,67,879,4543,687686,676,1,0 };
size_t size = sizeof(a) / sizeof(a[0]);
SecletSort(a, size);

来看结果：

选择排序也没有任何问题，将一组无序数排成升序。

未完待续。。。。。。