概述
挖坑填数 分治法
对挖坑填数进行总结
- i =L; j = R; 将基准数挖出形成第一个坑a[i]，例如第一次的基准数就是0索引的
- j–由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
- i 由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
- 再重复执行2，3二步，直到i==j，将基准数填入a[i]中，相遇时再按照基准更新左半边索引，和右半边索引
- quick_sort(s, l, i - 1);quick_sort(s, i 1, r);递归调用，直到每个递归的l 与 r相等，结束递归
void quick_sort(int s[], int l, int r)
{
if (l < r){
int i = l, j = r, x = s[l];
while (i < j){
while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
--j;
if(i < j)
s[i ] = s[j];
while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
i;
if(i < j)
s[j--] = s[i];
}
s[i] = x;
quick_sort(s, l, i - 1); // 递归调用
quick_sort(s, i 1, r);
}
}快速排序如果有相同数字的时候是怎样的过程
有相同的数字会忽略，然后继续先前的寻找方向去找下一个满足要求的数字进行替换
测试
int[] array = new int[8] { 5 ,2, 2, 1, 7 ,3, 4, 4 };
时间复杂度
O (nlogn)
O(log n)解析 再比如O(log n)，当数据增大n倍时，耗时增大log n倍（这里的log是以2为底的，比如，当数据增大256倍时，耗时只增大8倍，是比线性还要低的时间复杂度）。二分查找就是O(log n)的算法，每找一次排除一半的可能，256个数据中查找只要找8次就可以找到目标。
通俗易懂的例子
这个就像是有一百把钥匙，你突然觉得，我从头找是不是太慢了，我从中间找，比如我要找到23号的房间钥匙，我从中间切开，找到50编号的位置，然后23在150里面，我再把从中间切开变成25，然后23在125之间，我再切开变成12.5，然后23在12.5~25之间，依次找下去，直到找到钥匙。这种查找钥匙的方法的复杂度就是O(log^n)
O(n log n)解析 O(n log n)同理，就是n乘以log n，当数据增大256倍时，耗时增大256*8=2048倍。这个复杂度高于线性低于平方。归并排序就是O(n log n)的时间复杂度。
源码
https://github.com/luoyikun/UnityForTest SortScene场景
