快速排序

1.什么是快速排序

我们知道排序有很多种，常见的如希尔排序，插入排序，选择排序，堆排序等等，而快速排序也是排序家族中的一员。因为其在大多数情况下有着优秀的综合性能，快速排序的快速也算是实至名归，接下来就为大家讲解快速排序的思想与实现。

2.快速排序的核心思想

快速排序通过多次比较与交换来完成排序。而这个过程又被分为了多次重复单趟排序，接下来我们先从每一趟的排序讲起。

快速排序的单趟排序思想是：

在一个无序数组中取一个数key，每一趟排序的最终目的是：让key的左边的所有数小于key，key的右边都大于key（假设排升序）。

先不考虑这一步怎么实现，我们接着往下看。

以下面的数组为例，可以观察到的是，在完成单趟排序后，无论key的左边和右边是否有序，key都来到了它在整个数组有序时应该来到的位置，也就是这个数组的第四个位置。所以对于key来说，它已经被排好序了。

 接下来，我们对key的左右区间进行单趟排序，可以预见的是，每次排序都固定好了一个数。而当我们对细分的左右区间进行单趟排序，最终整个数组都会化为有序。

下面是快速排序的整体框架：

void QuickSort(int* a, int left, int right)
{if (left >= right)//如果区间只剩一个数或没有数就不进行操作return;int key = PartSort(a, left, right);//调用单趟排序函数，取key的位置QuickSort(a, left, key - 1);//递归调用，对左区间进行排序QuickSort(a, key + 1, right);//递归调用，对右区间进行排序
}

算法思想：

1. 选取第一个数为基准

2. 将比基准小的数交换到前面，比基准大的数交换到后面

3. 对左右区间重复第二步，直到各区间只有一个数

快速排序动图演示

代码：

void QuickSort(vector& v, int low, int high) {if (low >= high)		// 结束标志return;int first = low;		// 低位下标int last = high;		// 高位下标int key = v[first];		// 设第一个为基准while (first < last){// 将比第一个小的移到前面while (first < last && v[last] >= key)last--;if (first < last)v[first++] = v[last];// 将比第一个大的移到后面while (first < last && v[first] <= key)first++;if (first < last)v[last--] = v[first];}//v[first] = key;// 前半递归QuickSort(v, low, first - 1);// 后半递归QuickSort(v, first + 1, high);
}

希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序.

算法思想：

1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；

2. 按增量序列个数k，对序列进行k 趟排序；

3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

希尔排序动图演示

代码：

void shell_sort(T array[], int length) {int h = 1;while (h < length / 3) {h = 3 * h + 1;}while (h >= 1) {for (int i = h; i < length; i++) {for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {std::swap(array[j], array[j - h]);}}h = h / 3;}
}