排序(下)—快排、归并
快速排序
采用分治的思想：每次选区一个数作为基准，让整个数据中凡是大于此数的放在此数的右边，小于此数的放在此数的左边，然后进行对此数的两边进行选基准，如上方式的分法，递归下去，直到分出来的数据只有一个元素，或者无元素，停止分支，因为每次分支都会进行调整，所以当分到每个分支中只剩一个数的时候，整组数据就有序了。
- 首先得定义一个选选基准，并进行一次的分支的方法。
- 每分一次将最后的基准数的下标返回，以此为界限，把两边分别看作两个数组，并分别进行分治
- 直到所分后的数组元素个数为1或者0，就停止分治，此时，整个数组就已经有序。
流程图：
排序(下)---快排、归并排序(下)—快排、归并
- 快排的时间复杂度平均和最好情况都为O(n*logn),但是最坏情况是O(n^2),主要看key值的选取规则
选基准的进行单次调整的方法由很多种：
左右下标寻找法：
- 定一个左下标，定一个右下标，分别指向当前数组的最左和最右。
- 将key的值定位在边上（这里定位在最右边）
- 左下标先向右走，如果发现所指的值大于key，说明需要被交换到右边去，这时在让右下标向左走，在和左下标重合之前如果发现所指的值小于key的值，那就将两个下标所指的值进行交换，然后继续向对方的方向走，直到两个下标重合。
- 两个下标重合的时候将key值（数组的最右值与重合的地方进行交换）一次调整完成。
- 视图：
排序(下)---快排、归并排序(下)—快排、归并 - 代码：
int PartSort(int left, int right, int arr[]) { int key = arr[right]; int start = left; int end = right; //反例：1, 2, 3, 4, 5, 6, 7, 8, 9,如果是end= right-1,end会一直指向8,而start会向后移动到8停止，然后进行交换8和9会发现是错的。 while (start < end) { while (start < end && arr[start] <= key) //反例：5, 5, 5, 5, 5, 5, 5,自己可以推一下 { start++; } while (start < end && arr[end] >= key) { end--; } //此时start有可能和end是相等的 if (start < end)//此时说明start指向了一个比key大的数，end指向了一个比key小的数，应该将这两个数进行交换 { int tmp = arr[start]; arr[start] = arr[end]; arr[end] = tmp; } } //说明整个数组已经交换完毕，就差将最后一个与当前的数进行交换 int tmp = arr[right]; arr[right] = arr[end]; arr[end] = tmp; return end; } - 在编写的时候遇到好多坑需要注意
挖坑法
挖坑发其实还是由左右向中间遍历的方法，不过与左右指针寻找法稍有不同。
- 首先key值我们先选最右边的值
- 首先是start向右走，碰到比key值大的数的时候，直接将此值赋给end所指的值（第一次的时候end指向的是数组最右边的值，因为变量key的值就是此值，所以不用怕赋值过后将此值丢了）
- 赋值完成之后，start停止，让end向左移动，当碰到比key值小的值的时候，将此值赋给start所指的值（此时原来的值已经在刚在赋给了上一个end下标，所以原来的值是丢不掉的）
- 一次循环，直到start与end重合，此时start和end指向的位置的左边的数全都小于等于key值，end指向的数全都大于此值，并且此值在上一次赋值后已经有了一个备份，所以直接将key的值赋给此处的值，一次调整就完成了。
- 图示：
- 代码：
//挖坑法 int PartSort(int left, int right, int arr[]) { int start = left; int end = right; int key = arr[right]; while (start < end) { while (start < end && arr[start] <= key) { start++; } //此时start所指的数大于key值，需要将其赋给end所指的空间 arr[end] = arr[start]; while (start < end && arr[end] >= key) { end--; } //此时end所指的值小于key值，需要将其赋给start所指的空间 arr[start] = arr[end]; } arr[start] = key; return start; }
前后下标法：
一个下标用来遍历数组，一个下标用来标记当前已经走过的比较大的数，刚开是都指向数组中第一个数。
- 两个变量：cur用来遍历数组，firstBig用来指向第一个比较大的数，开始都为数组最左边的数，key的数还取数组最有变的数
- 首先让cur所指的内容和key值进行比较，如果大于key值，就继续向前移动。
- 如果cur所指的值小于key值，那就让firstBig所指的值与cur所指的值进行交换，并且让firstBig向后走动一步。
- 直到cur移动到数组的最后一个元素的时候停止移动，让cur指向的值和firstBig所指的值进行交换，一次调整完成。
- 图示：
- 代码：
//前后下标法 int PartSort(int left, int right, int arr[]) { int cur = left; int firstBig = left; int key = arr[right]; while (cur < right) { if (arr[cur] <= key) { int tmp = arr[firstBig]; arr[firstBig] = arr[cur]; arr[cur] = tmp; firstBig++; } cur++; } int tmp = arr[firstBig]; arr[firstBig] = arr[cur]; arr[cur] = tmp; return firstBig; }
快排主函数
以上我们只是介绍了一次的调整方法，而再我们的快速排序中，要频繁的使用这些调整的方法，因为快排的思想是分治，也就是每分治一次，都要使用一次调整：
- 首先将整体的数组使用我们刚才的方法进行一次调整，这样就会分治一次，我们每次调整都会返回最后放在中间的key，也就是说我们只是把比key小的放在了key的左边，比key大的放在了key的右边
- 然后我们将key的左边（不包含key）左右看成一个数组，进行调整，将key的右边（不包含key）看成一个数组进行调整，然后照样会返回一个key，然后再继续这样递归下去。
- 当最后分出来的数组中元素只有一个或者0个的时候，我们已经将整个数组的工作完成了，到此结束。
代码：
//递归
void QuickSortRecursion(int arr[], int left, int right)
{
if (left >= right)//取间内就剩最多一个元素
{
return;
}
int div = PartSort(left, right, arr);
QuickSortRecursion(arr, left, div-1);
QuickSortRecursion(arr, div + 1, right);
}
void QuickSort(int arr[], int size)
{
QuickSortRecursion(arr, 0, size-1);
}
这里我使用的是递归的方式，当然也可以使用非递归的方式，但是得用到栈。
//快速排序循环版
void QuickSortLoop(int arr[], int size)
{
int stack[100];
int top = 0;
stack[top++] = 0;
stack[top++] = size - 1;
while (top > 0)
{
int right = stack[--top];
int left = stack[--top];
int div = PartSort(left, right, arr);
if (right-left > 1)
{
stack[top++] = left;
stack[top++] = div - 1;
stack[top++] = div + 1;
stack[top++] = right;
}
}
}
注意每次都是先入左边数组，再入右边数组，但是每次都是先调整右边数组，再调整左边数组的。
关于key的选取
以上的介绍中我们默认选的key为最右边的数，但是这样是有缺点的：
假如我们的数组（假设右9个元素）本来就有序，不管是升序还是降序，假设是升序可以想象一下，当我们选最右边的数作为key的时候：
- 第一次切分的后，左边还有8个元素，右边没有元素，第二次切分之后左边还有7个元素，右边还没有元素……
- 这样下去就得切分8次，每次切分都要遍历一遍，时间复杂度已经达到了O(n^2)
- 如果是降序的话还是一样的。
再次我们右两种方法进行选择key的值:
- 随机选：生成随机数选取数组的一个下标
- 三选一：选出最左边、中间和最右边，三者进行比较，选出值处于三者中间的，然后将其与最右的进行交换，然后就可以使用我们的方法，当成选作最右的方法使用了。
代码：略（哈哈，其实不是很难）
归并排序
将对一个无序数组的排序转化为对两个有序数组的排序
使用一以上的思想将一个数组分为两个数组，对于这两个数组也分别使用此方法，这样切分下去就最后结果就是，一个数组就只有一个元素或者没有0个元素了
然后从切分到极致的情况开始排序，每次排序就是将两个数组合并为一个数组，最后将原来的数组又重新组合回来
- 首先将一个数组切分成两个数组，然后再随两个数组进行切分，直到最后切分出来的数组元素个数为1或者0
- 因为一个数可以认为式天生有序，所以可以从最后切分后的数组开始进行合并
- 合并的算法就是将两个有序的数组合并为一个有序数组
- 由最后一步开始合并，直到最后合并后只剩一个数组，说明排序已经完成。
流程图：
代码：
//首先是合并两个有序数组
void Merge(int arr[], int mid, int left, int right, int extra[])
{
int indexLeft = left, indexRight = mid+1;//indexLeft用来遍历左半个数组，indexRight用来遍历右半个数组，把中间的值归为左半边
int indexExtra = left;//用来遍历extra合并后的数组，为了保持下标相等，所以也从left开始
while (indexLeft <= mid && indexRight <= right)
{
if (arr[indexLeft] <= arr[indexRight])
{
extra[indexExtra++] = arr[indexLeft++];
}
else
{
extra[indexExtra++] = arr[indexRight++];
}
}
//最后出来的时候可能是左边走完了，右边没有走完，
//也可能是右边走完了，左边没走完
while (indexLeft <= mid)
{
extra[indexExtra++] = arr[indexLeft++];
}
while (indexRight <= right)
{
extra[indexExtra++] = arr[indexRight++];
}
//最后将extra放回到原来的数组中，并且是原来的区间
int i = 0;
for (i=left; i<=right; i++)
{
arr[i] = extra[i];
}
}
//然后是归并排序的递归版
void MergeSortRecursion(int arr[], int left, int right,int extra[])
{
if (left >= right)
{
return;
}
int mid = left + (right - left) / 2;
MergeSortRecursion(arr, left, mid, extra);
MergeSortRecursion(arr, mid+1, right, extra);
Merge(arr, mid, left, right, extra);
}
//归并排序的入口
void MergeSort(int arr[], int size)
{
int *p = (int*)malloc(sizeof(int) * size);
MergeSortLoop(arr, 0, size-1, p);
free(p);
}
//当然也有循环版（非递归）
void MergeSortLoop(int arr[], int left, int right, int extra[])
{
int i = 0;
int gap = 1;
for (gap = 1; gap <= right; gap *= 2)
{
for (i=left; i<=right; i+=(2*gap))
{
int indexLeft = i;
int mid = i + gap;
int indexRight = i+2*gap-1;
if (mid > right)
{
break;
}
if (indexRight > right)
{
indexRight = right;
}
Merge(arr, i + gap - 1, i, i + gap, extra);
}
}
}
- 归并排序是非常稳定的，它的任何情况下的时间复复杂度都是O(n*logn)