数据结构——排序算法（C语言）

本篇将详细讲一下以下排序算法：

1. 直接插入排序
2. 希尔排序
3. 选择排序
4. 快速排序
5. 归并排序
6. 计数排序

排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某写关键字的大小，按照递增或递减0排列起来的操作。

稳定性的概念

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变。如一下例子，

5 2 3 4 5 9 8

 经过排序，如果红5和蓝5的相对顺序不对，这就叫稳定，反之则不稳定。

 直接插入排序

直接插入排序的思想：将待排序的记录按其关键码值的大小逐个插入到一个已经排好序的序列中，直到所有的序列为有序序列。

实际中，我们玩扑克牌时，就用到了这样的一个排序算法。

时间复杂度： 

直接插入排序时一个稳定的排序，如果有相同的元素，它们的相对位置不会发生变化。它时间复杂度最好的情况下是O（N）,当一个数插入到已经排好序的序列中，只需要比较一次就好了。

最坏情况：O（N^2） ，在完全逆序的情况下，要排升序。

希尔排序 

 希尔排序其实和插入排序很像，只不过希尔排序的思想是：先预排序，最后插入排序。

预排序的意义在哪里？？

• 大的数更快到后面去，小的数更快到前面去。gap越大跳的越快，越不有序，当gap =1 时就是插入排序。
• 

   

   

  

   时间复杂度

   

  希尔排序的时间复杂度：大约为O（N^1.3） 

  ---

  选择排序

  选择排序的思想：选择排序可以在一次查找中找到最大的数和最小的数，然后把最大的数放到最后，最小的数放到最前面。

   

  时间复杂度

  时间复杂度是O（N^2）

  稳定性：差 

  

  ---

   快速排序

  快排思想：说到排序，或多或少都听过快速排序，快速排序是Hoare于1962年提出的一种二叉树结构的交换方法，其基本思想为：任取待排序元素序列中的某个元素作为基准值，按照该排序吗将待排序集合分割成2个子序列，左序列小于keyi值，右序列大于keyi值，然后重复此方法，最后拍完序。

  快速排序一次可以确定一个值在正确的位置上。（这个值就是key值）

  	if (begin >= end)
  	{
  		return;
  	}
  	int left = begin, right = end;
  	int keyi = left;
  	while (left