基本排序算法的关注点分为：
1. 时间复杂度。如n的平方（冒泡，选择，插入）；插入排序的优化希尔排序，则把复杂度降低到n的3/2次方；n乘以logn(快排，归并排序，堆排序）。
2. 是否为原地排序。如，归并排序需要额外的辅助空间。
3. 算法的稳定性。稳定排序（by nature）如冒泡，插入，归并。如果把次序考虑在内，可以把其他的排序（如快排，堆排序）也实现为稳定排序。
4. 算法的实现。同为时间复杂度同为n平方的算法中，插入排序的效率更高。但是如果算法实现的不好，可能会降低算法的效率，甚至让稳定的算法变得不稳定。又如，快速排序有不同的实现方式，如三路快排可以更好的应对待排序数组中有大量重复元素的情况。堆排序可以通过自上而下的递归方式实现，也可以通过自下而上的方式实现。
5. 不同算法的特点，如对于近乎有序的数组进行排序，首选插入排序，时间复杂度近乎是n，而快速排序则退化为n平方。

二分查找，需要注意 (l+r)/2可能存在越界问题。

leetcode题，用二分查找找到x*x > n 且(x-1)的平方小于n的数，则n-1就是结果。或者 x的平方小于n且x+1的平方大于n,则返回x。

#O(n)时间复杂度时间复杂度内找到一组数据的第 n大元素
import random
import time

def Array(n):
    a = []
    for i in range(n):
        a.append(random.randint(0 , n))
    return a
def QuickSort(n):
    array = Array(100)
    if n > len(array) or n < 1:
        print("超出范围，找不到")
        return
    n = n-1
    a = qsort(0 , len(array)-1 , array , n)
    print(sorted(array))
    print("-----------------------------")
    print(a)

def qsort(start , end , array , n):
    if start == end:
        res = array[start]
    if start < end:
        key = partation(array , start , end)
        print(start , key , end)
        if key > n :
            res = qsort(start , key-1 , array , n)
        elif key < n:
            res = qsort(key+1 , end , array , n)
        else:
            res = array[key]
    return res

def swap(array , start , end):
    temp = array[start]
    array[start] = array[end]
    array[end] = temp

def partation(array , start , end):
    temp = array[start]
    while start < end :
        while start<end and array[end]<=temp:
            end-=1
        swap(array , start , end)
        while start<end and array[start]>=temp:
            start+=1
        swap(array , start , end)
    return start

/**
 * O(n)时间复杂度内求无序数组中第K大元素
 */
public class TopK {

    public int findTopK(int[] arr, int k) {
        return findTopK(arr, 0, arr.length - 1, k);
    }

    private int findTopK(int[] arr, int left, int right, int k) {
        if (arr.length < k) {
            return -1;
        }
        int pivot = partition(arr, left, right);
        if (pivot + 1 < k) {
            findTopK(arr, pivot + 1, right, k);
        } else if (pivot + 1 > k) {
            findTopK(arr, left, pivot - 1, k);
        }
        return arr[pivot];
    }


    private int partition(int[] array, int left, int right) {
        int pivotValue = array[right];
        int i = left;

        //小于分区点放在左边 大于分区点放在右边
        for (int j = left; j < right; j++) {
            if (array[j] < pivotValue) {
                int tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
                i++;
            }
        }
        //与分区点交换
        int tmp = array[i];
        array[i] = array[right];
        array[right] = tmp;
        return i;
    }
}

java实现冒泡排序
代码如下：
package sort;

public class BubbleSort {

    public int[] bubbleSort(int[] array) {
        for (int i = 0;i < array.length - 1;i++) {
            for (int j = 0;j < array.length - i - 1;j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
            }
        }
        return array;
    }

    public static void main(String[] args) {
        int[] array = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        BubbleSort bubbleSort = new BubbleSort();
        int[] result = bubbleSort.bubbleSort(array);
        for (int i = 0;i < result.length;i++) {
            System.out.print(result[i] + " ");
        }
    }

}

实现模糊二分查找算法2:

public class BinarySearch {
    // 3. 查找第一个大于等于给定值的元素
    public static int bsFistGE(int[] array, int target) {
        int lo = 0;
        int hi = array.length - 1;

        while (lo <= hi) {
            int mid = lo + ((hi - lo) >> 1);

            if (array[mid] >= target) {
                if (mid == 0 || array[mid-1] < target) {
                    return mid;
                } else {
                    hi = mid - 1;
                }
            } else {
                lo = mid + 1;
            }
        }

        return -1;
    }

    // 4. 查找最后一个小于等于给定值的元素
    public static int bsLastLE(int[] array, int target) {
        int lo = 0;
        int hi = array.length - 1;

        while (lo <= hi) {
            int mid = lo + ((hi - lo) >> 1);

            if (array[mid] <= target) {
                if (mid == hi || array[mid+1] > target) {
                    return mid;
                } else {
                    lo = mid + 1;
                }
            } else {
                hi = mid - 1;
            }
        }

        return -1;
    }
}

实现模糊二分查找算法1:

public class BinarySearch {
    
    // 1. 查找第一个值等于给定值的元素
    public static int bsFirst(int[] array, int target) {
        int lo = 0;
        int hi = array.length - 1;

        while (lo <= hi) {
            int mid = lo + ((hi - lo) >> 1);

            if (array[mid] > target) {
                hi = mid - 1;
            } else if (array[mid] < target) {
                lo = mid + 1;
            } else {
                if (mid == lo || array[mid-1] != array[mid]) {
                    return mid;
                } else {
                    hi = mid - 1;
                }
            }
        }

        return -1;
    }

    // 2. 查找最后一个值等于给定值的元素
    public static int bsLast(int[] array, int target) {
        int lo = 0;
        int hi = array.length - 1;

        while (lo <= hi) {
            int mid = lo + ((hi - lo) >> 1);

            if (array[mid] > target) {
                hi = mid - 1;
            } else if (array[mid] < target) {
                lo = mid + 1;
            } else {
                if (mid == hi || array[mid] != array[mid+1]) {
                    return mid;
                } else {
                    lo = mid + 1;
                }
            }
        }

        return -1;
    }
}

实现一个有序数组的二分查找算法:

public class BinarySearch {
    // 最简单的二分查找算法：针对有序无重复元素数组
    // 迭代
    public static int binarySearch(int[] array, int target) {
        if (array == null) return -1;

        int lo = 0;
        int hi = array.length-1; // 始终在[lo, hi]范围内查找target

        while (lo <= hi) {
            int mid = lo + ((hi - lo) >> 1); // 这里若是 (lo + hi) / 2 有可能造成整型溢出

            if (array[mid] > target) {
                hi = mid - 1;
            } else if (array[mid] < target) {
                lo = mid + 1;
            } else {
                return mid;
            }
        }

        return -1;
    }

    // 递归
    public static int binarySearchRecur(int[] array, int target) {
        if (array == null) return -1;
        return bs(array, target, 0, array.length-1);
    }

    private static int bs(int[] array, int target, int lo, int hi) {
        if (lo <= hi) {
            int mid = lo + ((hi - lo) >> 1);
            if (array[mid] > target) {
                return bs(array, target, lo, mid-1);
            } else if (array[mid] < target) {
                return bs(array, target, mid+1, hi);
            } else {
                return mid;
            }
        }

        return -1;
    }
}

王争老师初三快乐！
这是今天两道题的解题思路和代码
1. O(n)时间内找到第K大的元素：
解题思路：利用快排中分区的思想，选择数组区间A[0...n-1]的左右一个元素A[n-1]作为pivot，对数组A[0...n-1]原地分区，这样数组就分成了三部分，A[0..p-1],A[p],A[p+1...n-1],如果p+1=k,那么A[p]就是要求解的元素，如果K>p+1,则说明第K大的元素在A[p+1...n-1]这个区间，否则在A[0...p-1]这个区间，递归的查找第K大的元素
2. Sqrt(x) （x 的平方根）
解题思路：利用二分查找的思想，从1到x查找x的近似平方根
代码：
https://github.com/yyxd/leetcode/blob/master/src/leetcode/sort/Problem69_Sqrt.java

Use Binary Search

class Solution {
    public int mySqrt(int x) {
        if (x == 0 || x == 1) {
            return x;
        }
        
        int start = 0;
        int end = (x >> 1) + 1;
        
        while (start + 1 < end) {
            final int mid = start + ((end - start) >> 1);
            final int quotient = x / mid;
            if (quotient == mid) {
                return mid;
            } else if (quotient < mid) {
                end = mid;
            } else {
                start = mid;
            }
        }
        
        return start;
    }
}

#二分查找变种
import random
import time

def Array(n):
    a = []
    for i in range(n):
        a.append(random.randint(0 , n))
    return a
#查找第一个值等于给定值的元素
def find_1(n):
    array = Array(100)
    array = sorted(array)
    left = 0
    right = len(array)-1
    while left <= right:
        mid = int((left+right)/2)
        if array[mid] > n:
            right = mid - 1
        elif array[mid] < n:
            left = mid + 1
        else:
            if mid==0 or array[mid] != array[mid-1]:
                return mid
            else:
                right = mid - 1
    print("找不到")
    return -1

#查找最后一个值等于给定值的元素
def find_2(n):
    array = Array(100)
    array = sorted(array)
    left = 0
    right = len(array)-1
    while left <= right:
        mid = int((left+right)/2)
        if array[mid] > n:
            right = mid - 1
        elif array[mid] < n:
            left = mid + 1
        else:
            if mid==right or array[mid] != array[mid+1]:
                return mid
            else:
                left = mid + 1
    print("找不到")
    return -1

#查找第一个值大于等于给定值的元素
def find_3(n):
    array = Array(100)
    array = sorted(array)
    left = 0
    right = len(array)-1
    while left <= right:
        mid = int((left+right)/2)
        if array[mid] >= n:
            if mid==0 or array[mid-1]<n:
                return mid
            else:
                right = mid - 1
        else array[mid] < n:
            left = mid + 1
    print("找不到")
    return -1

#查找最后一个值小于等于给定值的元素
def find_4(n):
    array = Array(100)
    array = sorted(array)
    left = 0
    right = len(array)-1
    while left <= right:
        mid = int((left+right)/2)
        if array[mid] <= n:
            if mid==right or array[mid+1]>n:
                return mid
            else:
                left = mid + 1
        else array[mid] > n:
            right = mid - 1
    print("找不到")
    return -1

#实现一个有序数组的二分查找算法
import random
import time

def Array(n):
    a = []
    for i in range(n):
        a.append(random.randint(0 , n))
    return a

def find(n):
    array = Array(100)
    array = sorted(array)
    left = 0
    right = len(array)-1
    while left <= right:
        mid = int((left+right)/2)
        if array[mid] > n:
            right = mid - 1
        elif array[mid] < n:
            left = mid + 1
        else:
            return mid
    print("找不到")
    return -1

x 的平方根 go 语言实现
func mySqrt(x int) int{

    if x==0{
        return 0
    }
    min:=1
    max:=x

    for {
        mid:=min+(max-min)/2
        if mid*mid==x{
            return mid
        }else if mid*mid<x{
            if (mid+1)*(mid+1)>x{
                return mid
            }else{
                min=mid+1
            }
        }else{
            max=mid-1
        }

    }
}

#include<iostream>
#include<cmath>
using namespace std;
double a = 1e-6;
double sqrt(double n){
    double low = 0.0;
    double high = n;
    
int i = 1000;

    while(i--){
        double mid = low + (high - low) / 2.0;
        //cout<<"n:"<<n<<endl;
        double square = mid * mid;
        //cout<<"sq:"<<square<<endl;
        //cout<<"s:"<<abs(square - n)<<endl;
        if(abs(mid * mid - n) < a){
            return mid;
        }
        else{

            if(square > n){
                high = mid;
            }
            else{
             low = mid;
            }
        }
    }
    return -2.0;
}
int main(){
    double t;
    while(true){
        cin>>t;
        cout<<sqrt(t)<<endl;
    }
}