排序是数据结构最重要的算法之一，在这里整理一下七大排序算法的思路及代码。

排序分为以下四类共七种排序方法：

插入排序：1) 直接插入排序     2) 希尔排序

选择排序：3) 直接选择排序     4) 堆排序

交换排序：5) 冒泡排序            6) 快速排序

合并排序：7) 合并排序

（注：本文中讲解均以升序为例）

---

1、直接插入排序

       直接插入排序是最为直接也是最简单的排序，对于一个无序的序列 a1,a2,a3,…，我们将它分为两个序列 a1 和 a2,a3,...,因为 a1序列中只有一个元素，我们可以将它看做一个有序序列，剩下的所有元素组成的序列为无序序列，我们只需要从无序序列中一次拿出每个元素，与有序序列中的元素作比较，找到合适的位置并将它插入，直到无序序列为空，此时排序完毕。

具体来说，首先，我们将一个无序数组分看做两个子序列，如下图。在第一个子序列中只有一个元素，因此可以将它看做有序，并且用一个指针 i 指向有序序列的最后一个，即 a1，再用一个指针 j 指向无序序列的第一个元素，即 a2，准备下次一排序。

       接下来我们来看第二个元素 a2，假设 a2 < a1，那么我们交换 a2 和 a1，并且让 i 指针左移一个，j 指针左移一个，此时 i 指针已超出数组范围，说明 a2 已到了正确的位置，此趟排序结束，得到一个新的有序序列，再将 i 指针指向有序序列的最后一个元素，将 j 指针指向无需数组的第一个元素，准备下一趟排序，如下图。

       接下来我们再来看第三个元素 a3，比较 i 指针所指向的 a1 与 j 指针指向的 a3，假设 a3 < a1，交换 a1 与 a3，将 i、j 指针分别左移一个，接着比较 i 指针指向的 a2 元素与 j 指针指向的 a3 元素，假设 a2 < a3，则说明 a3 已到了正确的位置，此趟排序结束，得到一个新的有序序列，再将 i 指针指向有序序列的最后一个元素，将 j 指针指向无需数组的第一个元素，准备下一趟排序，如下图。

依次类推，直到 i = size-1 时，表明所有的元素都在有序序列中，即该序列排序完成。

实例排序效果如下图：

代码如下：

void InsertSort(int arr[], size_t size)
{
	size_t i = 0;
	size_t j = 1;
	int key;
	size_t right;
	while(i < size-1){
		right = j;
		while(i >= 0 && arr[j] < arr[i]){
				key = arr[i];
				arr[i] = arr[j];
				arr[j] = key;
				j--;
				i--;
		}
		j = right+1;
		i = right;
	}
}

2、希尔排序

希尔排序是在1958年由希尔提出的，是基于直接插入排序的一个优化版本。

首先我们要明确希尔排序出现的原因：

1）当数据项数量不多的时候，插入排序可以很好的完成工作。

2）当数据项基本有序的时候，插入排序具有很高的效率。

基于这两个原因我们来了解一下希尔排序的步骤：

1）因为对于插入排序，若一个数列天生有序，则其排序效率最高。因此我们对一个序列进行预排序，使其尽量有序。

2）对一个序列进行预排序时，我们采用分组排序的方法，分组的间隔，我们记为 gap。

3）当 gap 越大时，排序的速度越快；而当 gap 越小，排序的效果越好，即预排序后的序列越接近与有序。

因此 gap 是动态变化的，在这里，我们让 gap 从 size 开始，每次 gap = gap / 3 + 1，直到 gap == 1 时预排序结束。

4）分组进行排序时，每组组内我们都采用插排的方式来排序。

以下面这个逆序的序列为例，在这个序列中，size = 9，因此第一次分组时 gap = 4，即每组的间隔为4，在图中表示为颜色相同的为一组：

我们将每组在组内进行插入排列，得到一个新的序列，在对其进行分组，此时 gap = gap / 3 + 1 ，即 gap = 2，如下图：

接着我们继续对得到的新序列进行排序，排序后发现 gap = gap / 3 + 1，即 gap = 1，则此时我们对序列进行最后一次排序后排序完成。

代码如下：

void _InsertSort(int arr[], size_t size, size_t gap)
{
	size_t i = 0;
	size_t j;
	size_t k;
	int key;

	while(i < gap)
	{
		j = i;
		k = j+gap;
		while(k < size)
		{
			key = arr[j];
			if(arr[j] > arr[k])
			{
				arr[j] = arr[k];
				arr[k] = key;
			}
			j += gap;                    //间隔为gap
			k += gap;
		}
		i++;
	}

}

void ShellSort(int arr[], size_t size)
{
	size_t gap = size;

	while(1)
	{
		gap = gap/3 + 1;
		_InsertSort(arr, size, gap);

		if(gap == 1)                   //排序完成后若gap=1则排序完成
		{
			break;
		}
	}
}

3、直接选择排序

       直接选择排序的思路很简单，就是每次从未排序的序列中选出最小的一个放在已排序的序列末尾，直到未排序序列为空，则排序结束。

       就上图的例子来说，我们定义一个 i 指针记录未排序序列的第一个元素，再定义一个 j 指针寻找当前序列中的最小元素，当 j 指针找到最小的元素后，交换 i 指针与 j 指针的元素，然后让 i 指针后移一位，指向当前未排序序列中的第一个元素，j 指针从 i 指针指向的位置开始遍历，寻找下一个最小的元素，以此类推，当 i 指针走到序列末尾时，排序结束。

       显然，这样一个一个寻找最小元素然后放到队尾的效率实在是太低了，那么我们可以将它优化一下，用两个指针同时指向序列的头和尾，此时当一次遍历时就可以同时寻找当前序列中的最大元素和最小元素，然后分别放到序列的开头结尾，当指向头和尾的指针相遇时，排序结束。这样虽然效率会高一些，但时间复杂度其实和上面的方法是一样的。

代码如下：

void Swap(int *a, int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

//选择排序
void SelectSrot(int arr[], size_t size)
{
	size_t minSp = 0;                   //记录头的指针
	size_t maxSp = size-1;              //记录尾的指针
	size_t minPos = minSp;              //寻找最小元素的指针
	size_t maxPos = maxSp;              //寻找最大元素的指针
	size_t i;
	while(minSp < maxSp)
	{
		for(i = minSp; i <= maxSp; i++)
		{
			if(arr[i] < arr[minPos])
			{
				minPos = i;
			}
		}
		Swap(&arr[minSp], &arr[minPos]);

		for(i = minSp; i <= maxSp; i++)
		{
			if(arr[i] > arr[maxPos])
			{
				maxPos = i;
			}
		}
		Swap(&arr[maxSp], &arr[maxPos]);

		minSp++;
		maxSp--;
	}
}

4、冒泡排序

       冒泡排序应该是我们在学习数据结构之前就很熟悉的一种排序，它的思想就如同它的名字一样，比较相邻两元素的大小，若反序，则交换，每趟将序列中最大的元素交换到最后位置，就像气泡从水里冒出一样。

       具体来说，我们定义一个指针 i 指向序列的第一个元素，再定义一个指针 j 指向 i 的下一个元素，比较两元素的大小，若 j 指针指向的元素小于 i 指针指向的元素，则交换两指针指向的元素，再将两指针分别后移一个；反之，直接将两指针后移一位，继续下一次比较。当一趟排序完成后，下一次参与排序的元素个数就要减一。

值得注意的是，若在一趟排序中没有发生任何一次交换，则说明该序列已经有序。

代码如下：

void Swap(int *a, int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
//冒泡排序
void BubbleSort(int arr[], int size)
{
	int i, j;

	for(i = 0; i < size-1; i++)
	{
		for(j = 0; j < size-1-i; j++)
		{
			if(arr[j] > arr[j+1])    //若前一个大于后一个，则交换
			{
				Swap(arr+j, arr+j+1);
			}
		}
	}
}

5、堆排序

       上面我们介绍的所有排序的时间复杂度均为O(n^2)，下面我们要介绍的排序算法均为O(nlogn)，可以说都是很优秀的排序算法，但对于不同的情况，它们有各自的优势，首先来看堆排序。堆排序的优势在于它只需要一定数量的额外空间，堆排序要比空间复杂度为O(n)的归并排序稍微慢一点。

       首先，我们来看看堆的定义：一颗二叉树，任意非叶子节点的左右子节点都同时比它大，或者同时比它小。

       堆的定义有很明显的作用，最小的或者最大的数字永远在堆顶，因此我们借助堆的这个特点，实现排序。首先我们根据给出的序列建一个大堆，此时序列中最大的元素就在堆顶，我们取出该元素将它与堆的最后一个元素进行交换，缩小区间，并做向下调整，此时第二大的元素就到了堆顶，再次交换堆顶元素与当前堆的最后一个元素，并缩小区间，以此类推，直到排序完成。

       下面我们以序列{53，17，78，9，45，65，87，23，31}为例，首先我们根据给出的序列建堆，并做向下调整，得到第一个大堆。

      交换堆顶元素与堆尾元素，同时缩小排序区间，对现在的树再次进行向下调整，此时的堆顶元素就是第二大的元素。

      此时再次交换堆顶元素与堆尾元素，缩小排序区间，再次进行向下调整。

      重复上述操作，直到需要排序的堆中只剩一个元素时，排序结束。

代码如下：

//向下调整
void AdjustDown(int array[], size_t size, size_t root)
{
	size_t left = 2 * root + 1;
	size_t right = 2 * root + 2;
	size_t max;

	while(left < size)
	{
		max = left;
		if(right < size)
		{
			if(array[right] >= array[max])
			{
				max = right;
			}
		}
		if(array[root] >= array[max])
		{
			break;
		}

		Swap(array+root, array+max);
		root = max;
		left = 2 * root + 1;
		right = 2 * root + 2;
	}
}
//堆排
void HeapSort(int array[], int size)
{
	int i, j;
	for(i = (size - 2 ) / 2; i >= 0; i--)
	{
		AdjustDown(array, size, i);
	}

	for(j = 0; j <= size; j++)
	{
		Swap(array, array + size - 1 - j);
		AdjustDown(array, size - 1 - j, 0);
	}
}

6、快速排序

        快速排序是冒泡排序的改进版，也是最好的一种内排序，在很多面试题中都会出现，也是作为程序员必须掌握的一种排序方法。

快速排序的基本思路是这样的：

1）在待排序的元素任取一个元素作为基准(通常选第一个或最后一个元素)，称为基准元素；

2）将待排序的元素进行分区，比基准元素大的元素放在它的右边，比其小的放在它的左边；

3）对左右两个分区重复以上步骤直到所有元素都是有序的。

       而对于怎样将待排序元素根据基准值分区，有三种方法，分别是：挖坑法、Hoare法和快慢指针法，在下面我们以最后一个元素作为基准值为例来讲解一下这三种方法。

挖坑法：

       挖坑法，顾名思义就是挖一个“坑”将合适的元素放进去。

       首先我们确定最后一个元素为基准元素，定义一个begin指针指向序列的第一个元素，再定义一个end指针指向序列的最后一个元素，即基准元素所在的位置，并定义一个pivot变量保存基准元素。此时就可以看做我们将基准元素从序列中拿了出来，而基准元素在序列中的位置就可以看做是一个坑。

       然后我们开始排序，因为end指针此时指向的是一个“坑”，所以我们让begin指针先开始遍历。当begin指向的元素小于或等于基准元素时，begin向后走，当begin遇到第一个大于基准元素的元素时停止遍历，并将begin所指向的元素放入end所指向的位置，此时begin所在的位置就是一个“坑”了。然后我们让end开始遍历，当end指向的元素大于基准元素时，end向前走，当end遇到第一个小于基准元素的元素时，停止遍历，并将end所指向的元素放入begin所指向的位置，此时end所指向的位置就又变成“坑”了。以此类推，当begin和end相遇时，将最开始拿出去保存在pivot中的基准值放在最后的坑里，第一趟排序就结束了。

排序中序列中元素分布：

下面我们举个例子来理解一下：

       首先我们选择序列中的最后一个元素作为基准元素，并用变量pivot保存它的值，定义一个begin指针指向序列开头，一个end指针指向序列末尾，此时end指针指向的位置就可以看作是一个“坑”。我们让begin指针从序列开头开始遍历，遇到第一个大于基准元素的元素时停止遍历，即begin在 7 处停止遍历，并将 7 放入end所指向的“坑”中，此时begin所指向的位置就变成了“坑”。再让end开始遍历，当end遇到第一个小于或等于基准元素的元素时停止遍历，即当end指向 3 时停止遍历，再将 3 放入begin指向的“坑”中，此时，end所指向的位置就又变成了“坑”，后面以此类推。

       当begin指针与end指针相遇时，如下图所示，此时“坑”左边的元素全部小于或等于基准值，而坑右边的元素全部大于基准元素，因此这个“坑”的位置就是基准元素的位置，我们将基准元素放入“坑”中。

        一趟排序完成后，原序列被分成了三部分：基准元素左边的序列、基准元素、基准元素右边的序列，我们用分而治之的思想来处理基准元素两边的序列，即对左右两边的小序列进行同样方式的排序，直到小序列已经有序（小序列中只有一个元素）或分不出小序列（小序列中有0个元素）时，我们才能得到一个完全有序的序列，排序结束。

挖坑法代码如下：

void QuickSort_1(int arr[], int left, int right)
{
	int begin = left;
	int end = right;
	int pivot = arr[right];

	if(left >= right)                       //小序列有序或小序列里没有元素时，返回
	{
		return;
	}

	while(begin < end)
	{
		while(begin < end && arr[begin] <= pivot)
		{
			begin++;
		}
		arr[end] = arr[begin];

		while(end > begin && arr[end] >= pivot)
		{
			end--;
		}
		arr[begin] = arr[end];
	}
	arr[end] = pivot;

	QuickSort_1(arr, left, end-1);            //递归完成基准元素左边序列的排序
	QuickSort_1(arr, end+1, right);           //递归完成基准元素右边序列的排序
}

Hoare法：

       Hoare法，又叫左右指针法，Hoare法也需要定义一个基准元素，和挖坑法不同的是，Hoare法是通过交换来实现排序的。

       首先我们用pivot指针标记最后一个元素作为基准元素，再定义一个begin指针指向序列的开头，一个end指针指向序列的末尾，让begin指针从序列开头开始遍历，当begin指向的元素小于或等于基准元素时，begin向后走，当begin遇到第一个大于基准元素的元素时，begin停止遍历，end从序列末尾开始遍历，当end指向的元素大于基准元素时，end向前走，当end遇到第一个小于基准值的元素时，end停止遍历，此时交换begin指向的元素和end指向的元素，继续遍历，直到begin和end相遇，交换begin指向的元素与pivot指向的元素，第一趟排序完成。

排序中序列中元素分布：

下面举例说明：

       首先我们选择序列的最后一个元素作为基准元素，并用pivot指针标记，在定义一个begin指针指向序列开头，一个end指针指向序列末尾。先让begin指针开始遍历，当begin指针遇到第一个大于基准元素的元素时停止遍历，end指针开始遍历，当end指针遇到第一个小于或等于基准元素的元素时停止遍历，交换begin指向的元素和end指向的元素，让begin指针和end指针继续遍历，进行下一次交换，直到begin指针与end指针相遇。

       当begin指针与end指针相遇时，如下图所示，此时begin指针和end指针共同指向的是序列中第一个大于基准元素的元素，那么我们只需要交换begin指针与pivot指针所指向的元素，就可以完成让基准元素左边的元素全部小于或等于基准元素，基准元素右边的元素全部大于基准元素。

        一趟排序完成后，原序列同样被分成了三部分：基准元素左边的序列、基准元素、基准元素右边的序列，我们还是采用分而治之的思想来处理基准元素两边的序列，即对左右两边的小序列进行同样方式的排序，直到小序列已经有序（小序列中只有一个元素）或分不出小序列（小序列中有0个元素）时，我们才能得到一个完全有序的序列，排序结束。

Hoare法代码如下：

void Swap(int *a, int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

//Hoare法
void QuickSort_3(int arr[], int left, int right)
{
	int begin = left;
	int end = right;

	if(left >= right)
	{
		return;
	}

	while(begin < end)
	{
		while(begin < end && arr[begin] <= arr[right])
		{
			begin++;
		}
		while(begin < end && arr[end] > arr[right])
		{
			end--;
		}

		Swap(arr + begin, arr + end);
	}
	Swap(arr + begin, arr + right);

	QuickSort_3(arr, left, begin - 1);
	QuickSort_3(arr, begin + 1, right);

}

快慢指针法：

       快慢指针法和上述两个方法略有不同，但快慢指针法的应用范围更广，在链表中也能很好的使用，使我们必须掌握的排序方法。

       首先我们还是确定序列的最后一个元素为基准元素，用指针pivot标记，再定义一个div指针和一个cur指针同时指向序列的开头。这里我们要清楚，虽然div和cur是同时从序列的开头出发，但div指针是指向序列中第一个大于基准元素的元素的，而cur指针是在序列中寻找小于或等于基准元素的元素，并与div指向的元素进行交换，使得小于基准元素的元素与大于基准元素的元素分开。一开始div指针和cur指针同时开始遍历，当遇到第一个大于基准元素的元素时div停止遍历，cur继续向后遍历，当cur指向的元素小于或等于基准元素时，交换div与cur所指向的元素，div向后走一个，继续指向序列中第一个大于基准元素的元素，cur继续向后遍历，当cur指针与pivot指针相遇时，将基准元素与div指向的元素交换，第一趟排序结束。

排序中序列中元素分布：

下面我们举个例子来理解一下：

       首先我们选择序列的最后一个元素作为基准元素，并用pivot指针基准元素的标记，再定一个div指针和一个cur指针指向序列的开头，让他们同时从序列的开头开始遍历，当遇到第一个大于基准元素的元素，即遇到元素 7 时，div停止遍历，cur继续遍历，当遇到第一个小于或等于基准元素的元素，即元素 2 时，cur停止遍历，此时div指向的是序列中第一个大于基准元素的元素，因此我们交换div指向的元素和cur指向的元素，使得比基准元素小的元素在比基准元素大的元素前面，交换之后让div元素向后走一个，即让div指针继续指向序列中第一个大于基准元素的元素，cur指针继续遍历，直到与pivot指针相遇。

       当cur指针与pivot指针相遇时，基准元素之前的序列中所有小于等于基准元素的元素全部都在大于基准元素我的元素前面，因为div指向的是第一个大于基准元素的元素，那么我们只需要交换div指向的元素与基准元素，就可以将基准元素放在比它大的元素和比它小的元素之间，第一趟排序完成。

       一趟排序完成后，原序列同样被分成了三部分：基准元素左边的序列、基准元素、基准元素右边的序列，我们继续采用分而治之的思想来处理基准元素两边的序列，即对左右两边的小序列进行同样方式的排序，直到小序列已经有序（小序列中只有一个元素）或分不出小序列（小序列中有0个元素）时，我们才能得到一个完全有序的序列，排序结束。

快慢指针法代码如下：

void Swap(int *a, int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

//快慢指针法
void QuickSort_2(int arr[], int left, int right)
{
	int div = left;
	int cur = left;

	if(left >= right || left < 0 || right < 0)
	{
		return;
	}

	for(; cur < right; cur++)
	{
		if(arr[cur] <= arr[right])
		{
			Swap(arr+cur, arr+div);
			div++;
		}
	}
	Swap(arr+div, arr+right);

	QuickSort_2(arr, left, div-1);
	QuickSort_2(arr, div+1, right);
}

7、归并排序

      归并排序的思想很简单，是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

归并排序的思想：

       将待排序的元素序列分成两个长度相等的子序列，对每一个子序列排序，然后将它们合并成一个序列。合并两个子序列的过程称为二路归并。

归并排序的核心步骤：

1、分组。停止条件：①分出的小区间已经有序（区间内只有一个元素）②分出的小区间内没有元素。

2、归并。

代码如下：

// 合并两个有序区间
void Merge(int array[], int left, int mid, int right, int extra[])
{
	int left_index = left;
	int right_index = mid;
	int extra_index = left;

	while (left_index < mid && right_index < right) {
		if (array[left_index] <= array[right_index]) {
			extra[extra_index++] = array[left_index++];
		}
		else {
			extra[extra_index++] = array[right_index++];
		}
	}

	while (left_index < mid) {
		extra[extra_index++] = array[left_index++];
	}

	while (right_index < right) {
		extra[extra_index++] = array[right_index++];
	}

	for (int i = left; i < right; i++) {
		array[i] = extra[i];
	}
}
//归并排序
void __MergeSort(int array[], int left, int right, int extra[])
{
	if (left + 1 == right) {
		// 里面只剩一个数了，所以已经有序了
		return;
	}

	if (left >= right) {
		// 区间内没有数了
		return;
	}

	int mid = left + (right - left) / 2;
	__MergeSort(array, left, mid, extra);
	__MergeSort(array, mid, right, extra);

	// 左右两个小区间都已经有序了
	Merge(array, left, mid, right, extra);
}

---

最后附上各排序算法的时间、空间复杂度对比：