快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
static void qsort(int[] a, int l,int r){
    if(l>=r)return;
    int i=l-1,j=r+1,x=a[l+r>>1];
    while(i<j){
        do i++; while(a[i]<x);
        do j--;while(x<a[j]);
        if(i<j){
            swap(a,i,j);
        }
    }
    qsort(a,l,j);
    qsort(a,j+1,r);
}

它的思想很简单，但是它的边界处理真的很傻x，稍不留神就会无限递归或无线循环。

我曾如是写道:

1
2
3
4
5
6
7
8
9
10
11
12
13
static void qsort(int[] arr, int begin, int end){
    if(begin>=end) return;
    int i=begin,j=end,x=arr[begin+end>>1];
    while(i<j){
        while(arr[i]<x) i++;
        while(x<arr[j]) j--;
        if(i<j) {
            swap(arr,i,j);
        }
    }
    qsort(arr,begin, i-1);
    qsort(arr, i+1,end);
}

当它在以下测试用例会无限循环

1
2
2
1 1

它会进入无限循环，i,j指针连动都不带动的！！！

而do while则会一言不合先动指针，然后再判断，这样指针就不会停滞下来。

我曾如是写道:：

1
2
3
4
5
6
7
8
9
10
11
12
13
static void qsort(int[] a, int l,int r){
    if(l>=r)return;
    int i=l-1,j=r+1,x=a[l+r>>1];
    while(i<j){
        do i++; while(a[i]<x);
        do j--;while(x<a[j]);
        if(i<j){
            swap(a,i,j);
        }
    }
    qsort(a,l,i-1);
    qsort(a,i+1,r);
}

这种情况会造成无限递归的问题，实际上x=a[l+r>>1]和qsort(a,l,j); qsort(a,j+1,r);是相关联的，你也许会对分界点j的处理感到困扰。

且看证明：

1.进行边界分析是为了避免分治时出现被分为0和n的情况，造成无限分治内存超限问题。
2.若以j为分界点，对于quick_sort(q, l, j), quick_sort(q, j + 1, r)，j有可能取l~r的任何一个值，若j取l，则quick_sort(q, l + 1, r)执行时会产生分割，不会出现0和n的情况；若j取r，则quick_sort(q, l, r)执行时会分割为n，会导致无限分治。本条结论：若在递归分治前保持j = r，那么就会出现无限分治的情况
3.所以只要在进入分治前不要让j取到r就可以了。那什么时候会取到r呢？初始化完毕时，j的值为r + 1，当执行过一次do j--; while(q[j] > x)后，j变为r，并且恰好在此之后j都不会发生改变，即do j--; while(q[j] > x)只会执行一次，如果保持j = r不变的话，那么i会在此之前一直自增到i = r，此时j = r; i = r不满足i < j循环结束，此时，整个while(i < j) {}循环只进行了1轮，分治，从而导致分治出了0和n两个情况。本条结论：若要在递归分治前保持j = r，那么while(i < j) {}只能执行一次
4.现在把焦点转移到x的取值上，第3点说到，若出现无限分治问题，i会一直自增到i = r，若出现这种情况，那么x的取值一定是q[r]，因为如果x的值不为q[r]，那么一定会在x处存在q[i] == x，而q[i] == x会导致i自增暂时停止，那么就会往下执行，执行do j--;，判断后进入第二轮while(i < j) {}循环，进入第二轮循环会使j自减至少两次，而他的初值为r + 1，也就是说，j的值不会一直保持在j = r上，也就不会导致无限分治。本条结论：若x的取值不为q[r]，那么while(i < j) {}会至少执行两次，因此在进行递归分治前，j的值是一定小于r的。
5.l + r >> 1的值一定是小于r的，不会取到r，而l + r + 1 >> 1的值一定是大于l的，不会取到l
所以综合2、3、4、5的结论就得出了若以j为分界点，x取q[l + r >> 1]，此时不会出现无限分治的情况；若以i为分界点，x取q[l + r + 1 >> 1]，此时不会出现无限分治的情况

坑是真的多

归并排序

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {

    public int binary_search(int low, int high, int[] nums, int target){  
        if(low>high) return -1;
        else{
            int mid = (low+high)/2;
            if(nums[mid]<target){
                return binary_search(mid+1, high, nums, target);
            }
            else if(nums[mid]>target){
                return binary_search(low, mid-1, nums, target);
            }
            else
                return mid;
        }
        
    }
    public int search(int[] nums, int target) {
        return binary_search(0, nums.length-1, nums, target);
    }
}