挖坑填数+分治法
对挖坑填数进行总结
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场景