查找和排序算法大杂烩

很多算法都一知半解，就是现在，一个个击破它们吧！

链表算法

反转单链

//单链表的转置,循环方法
Node* reverseByLoop(Node *head)
{
    if(head == NULL || head->next == NULL)
        return head;
    Node *pre = NULL;
    Node *next = NULL;
    while(head != NULL)   //总体来说就是进来一个，指向新链表一次，后面的链表由next保存
    {
        next = head->next;//保存之后的链表
        head->next = pre; //使当前的点指向之前生成的新链表
        pre = head;       //新链表指向当前点形成更新的链表
        head = next;      //当前元素变成之前的next的第一个元素
    }
    return pre;
}

链表倒数第k个节点

设置两个指针 p1、p2，首先 p1 和 p2 都指向 head，然后 p2 向前走 k 步，这样 p1 和 p2 之间就间隔 k 个节点，最后 p1 和 p2 同时向前移动，直至 p2 走到链表末尾

public class ListNode {
  int val;
  ListNode next = null;

  ListNode(int val) {
    this.val = val;
  }
}


public class Solution {
  public ListNode FindKthToTail(ListNode head,int k) {
    if(head==null||k<=0){
      return null;
    }

    ListNode pre=head;
    ListNode last=head;       

    for(int i=1;i<k;i++){
      if(pre.next!=null){
        pre=pre.next;
      }else{
        return null;
      }
    }

    while(pre.next!=null){
      pre = pre.next;
      last=last.next;
    }
  
    return last;
  }
}

速学路径

Java反转单链表实战

逆序、求倒数第K个节点，判断是否有环

栈

数组方式

public class StackArray{
    private int[] array;//用数组实现
    private int top; //栈顶指针
    private final static int size = 100;
    public StackArray(){
        array = new int[size];
        top = -1; //栈空的时候 
    }
    //压栈
    public void push(int element){
        if(top == size-1){
            throw new StackOverflowError();
        }
        else 
            array[++top] = element;
    }
    //弹栈
    public int pop(){
        if(top == -1){
            throw new EmptyStackException();
        }
        return array[top--];
    }
    //判断是否为空
    public boolean isEmpty(){
        return top == -1;
    }
    //返回栈顶元素
    public Integer peek(){
        if(top == -1){
            throw new EmptyStackException();
        }
        return array[top];
    }
}

链表方式

public class LinkedStack<T> implements Stack<T>{
    //不用容器或者数组等数据结构存储节点
    //Node定义一个节点类
    private static class Node<U>{
        private U item; //存储的data
        private Node<U> next; //类似指针
        Node(){
            this.item = null;
            this.next = null;
        }
        Node(U item, Node<U> next){
            this.item = item;
            this.next = next;
        }
        boolean end(){
            return item == null && next == null;
        }
    } 

    private Node<T> top ; //栈顶指针
    LinkedStack(){
        top = new Node<T>();
    }


    //弹栈
    public T pop(){
        if(this.isEmpty() == true){
            throw new EmptyStackException();
        }
        T result = top.item;
        if(!top.end())
        {
            top = top.next;
        }
        return result;
    }
    //压栈
    public void push(T element){
        top = new Node<T>(element, top);
    }
    //判断是否为空
    public boolean isEmpty(){
        return  top.end();
    }
    //返回栈顶元素
    public T peek(){
        if(this.isEmpty() == true){
            throw new EmptyStackException();
        }
        T result = top.item;
        return result;
    }   
}

参考路径

Stack的三种实现（数组，容器，链表）

串

字符串逆转

数组方式

public static String strReverseWithArray2(String string){
       if(string==null||string.length()==0)return string;
       int length = string.length();
       char [] array = string.toCharArray();
       for(int i = 0;i<length/2;i++){
           array[i] = string.charAt(length-1-i);
           array[length-1-i] = string.charAt(i);
       }
       return new String(array);
   }

栈方式

public static String strReverseWithStack(String string){
       if(string==null||string.length()==0)return string;
       Stack<Character> stringStack = new Stack<>();
       char [] array = string.toCharArray();
       for(Character c:array){
           stringStack.push(c);
       }
       int length = string.length();
       for(int i= 0;i<length;i++){
           array[i] = stringStack.pop();
       }
       return new String(array);
   }

参考路径

http://www.cnblogs.com/JohnTsai/p/5606719.html

遍历

二叉树遍历

public class Node {
    public int data;
    public Node left;
    public Node right;
    public Node(int data){
        this.data = data;
    }
    public Node(){
        this(0);
    }
}
//中序递归遍历
private void inOrderRe(Node node,List<Integer> list){
    if(list==null){
        list=new ArrayList<>();
    }
    if(node==null){
        return;
    }
    if(node.left!=null){
        inOrderRe(node.left,list);
    }
    list.add(node.data);
    if(node.right!=null){
        inOrderRe(node.right,list);
    }
}
//插入算法
public void insert(Node node) {
    if (root == null) { //根节点不为空
        root = node;
        size++;
        return;
    }
    Node current = root;
    while (true) {
        if (node.data <= current.data) {
            if (current.left == null) {
                current.left = node;
                size++;
                return;
            }
            current = current.left;
        } else {
            if (current.right == null) {
                current.right = node;
                size++;
                return;
            }
            current = current.right;
        }
    }
}

查找

折半查找

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

// while循环
public int binary_search(int[] arr,int val){
	int start = 0;
	int end = arr.length - 1;
	int mid;
	while(start <= end){
		mid = (start + end) / 2;
		if (val < arr[mid]) {
			end = mid - 1;
		}else if (val > arr[mid]) {
			start = mid + 1;
		}else {
			return mid;
		}
	}
}

// 递归版本
public int binary_search(int arr[],int val,int start,int end){
	if (start > end) {
		return -1;
	}

	int mid = (start + end) / 2;
	if (val < arr[mid]) {
		binary_search(arr,val,start,mid-1);
	}else if (val > arr[mid]) {
		binary_search(arr,val,mid+1,end);
	}else {
		return mid;
	}
}

二叉查找树

1. 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2. 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3. 任意节点的左、右子树也分别为二叉查找树；
4. 没有键值相等的节点。

排序

升序是从小到大

降序是从大到小

速学路径

http://www.jianshu.com/p/bbb7c838880f

插入排序

说白了就是循环一遍，每个元素都按大小插到前面的序列里

public static void insertSort(int[] list)
    {
    int size = list.length;
    int temp = 0 ;
    int j =  0;
    
    for(int i = 0 ; i < size ; i++)
    {
        temp = list[i];
        //假如temp比前面的值小，则将前面的值后移
        for(j = i ; j > 0 && temp < list[j-1] ; j --)
        {
        	list[j] = list[j-1];
        }
        list[j] = temp;
    }
}

希尔排序

有间隔的直接插入排序

public void shellSort(int[] data)
{
    int j;
    int temp;
    //每次将步长缩短为原来的一半
    for (int increment = data.length / 2; increment > 0; increment /= 2)
    {
        for (int i = increment; i < data.length; i++)
        {
            temp = data[i];
            for (j = i; j >= increment; j -= increment)
            {
                if(temp < data[j - increment])//如想从小到大排只需修改这里
                {
                    data[j] = data[j - increment];
                }
                else
                {
                    break;
                }
            }
            data[j] = temp;
        }
    }
}

堆排序

堆是一颗完全二叉树，除了最底层之外，每一层都是满的。

它有最大堆和最小堆之分

堆中每个父节点的元素值都大于等于其孩子结点的堆就是一个最大堆

那么相反，每个父节点都小于等于其孩子结点的堆就是一个最小堆

堆排序的时间复杂度为O(n*logn)

他的排序方法就是先形成一个堆

父节点和两个子节点进行比较，把最大的那个换到父节点上，然后那两个子节点就递归这个比较和交换

然后开始排序了

把堆顶的元素拿下，并且把最小的元素换到堆顶，然后形成一个新堆，然后循环这样的操作，取出来的元素就有序了

满二叉树：除了叶结点外每一个结点都有左右子叶且叶结点都处在最底层的二叉树；

完全二叉树：只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树；

堆是一种完全二叉树或者近似完全二叉树

public static void sort(int[] a){
    int arrayLength=a.length;
    //循环建堆
    for(int i=0;i<arrayLength-1;i++){
        //建堆
        buildMaxHeap(a,arrayLength-1-i);
        //交换堆顶和最后一个元素
        swap(a,0,arrayLength-1-i);
    }
}
//对data数组从0到lastIndex建大顶堆
public static void buildMaxHeap(int[] data, int lastIndex){
    //从lastIndex处节点（最后一个节点）的父节点开始
    for(int i=(lastIndex-1)/2;i>=0;i--){
        //k保存正在判断的节点
        int k=i;
        //如果当前k节点的子节点存在
        while(k*2+1<=lastIndex){
            //k节点的左子节点的索引
            int biggerIndex=2*k+1;
            //如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在
            if(biggerIndex<lastIndex){
                //若果右子节点的值较大
                if(data[biggerIndex]<data[biggerIndex+1]){
                    //biggerIndex总是记录较大子节点的索引
                    biggerIndex++;
                }
            }
            //如果k节点的值小于其较大的子节点的值
            if(data[k]<data[biggerIndex]){
                //交换他们
                swap(data,k,biggerIndex);
                //将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值
                k=biggerIndex;
            }else{
                break;
            }
        }
    }
}
//交换
private static void swap(int[] data, int i, int j) {
    int tmp=data[i];
    data[i]=data[j];
    data[j]=tmp;
}

归并排序

将两个已经排序的序列合并成一个序列的操作

public int[] gb_sort(int[] nums, int low, int high) {
    int mid = (low + high) / 2;
    if (low < high) {
        // 左边
        gb_sort(nums, low, mid);
        // 右边
        gb_sort(nums, mid + 1, high);
        // 左右归并
        merge(nums, low, mid, high);
    }
    return nums;
}
public void merge(int[] nums, int low, int mid, int high) {
    int[] temp = new int[high - low + 1];
    int i = low;// 左指针
    int j = mid + 1;// 右指针
    int k = 0;
    // 把较小的数先移到新数组中
    while (i <= mid && j <= high) {
        if (nums[i] < nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
        }
    }
    // 把左边剩余的数移入数组
    while (i <= mid) {
        temp[k++] = nums[i++];
    }
    // 把右边边剩余的数移入数组
    while (j <= high) {
        temp[k++] = nums[j++];
    }
    // 把新数组中的数覆盖nums数组
    for (int k2 = 0; k2 < temp.length; k2++) {
        nums[k2 + low] = temp[k2];
    }
}

空间复杂度

平均时间复杂度是logn，所以根据遍历次数，推出空间复杂度也是logn

快速排序

从需要排序的数里面随便找出一个，然后，把比这个数小的放在这个数左边，比这个数大的放在这个数右边，一样大的和这个数放在一起，最后，左右两边各自重复上述过程，直到左边或右边只剩下一个数（或零个数）无法继续为止。

取出第一个元素为基准，然后有两个指针，一个指向第二个元素，一个指向最后一个元素，先从最后一个进行比较，如果比基准大的话，就向前移向下一个，如果元素比基准小的话，就把那个元素替换到前面那个空位，然后前面的指针开始比较，如果比基准小，就移向向后下一个，如果比基准大，就替换到后面的那个空位。然后又变成后指针开始移动比较。这样的比较替换后，除去基准的那个元素，再分成前后两组，然后进行这个过程，直到前后两个指针重合，排序也就结束了。

快速排序不稳定，它的时间复杂度最好时为O(nlogn)，最差情况是O(n\n)

public int partition(int[] arr, int start, int end){
    int key = arr[start];
    while(start<end){
        while(start < end && key <= arr[end]){
            end--;
        }
        arr[start] = arr[end];
        while(start < end && key >= arr[start]){
            start++;
        }
        arr[end] = arr[start];
    }
    arr[start] = key;
    return start;
}

public void sort(int[] arr,int start,int end){
    if (start < end){
        int middle = partition(arr,start,end);
        sort(arr,0,middle-1);
        sort(arr,middle+1,end);
    }
}

优化

三值取中法： 待排序序列的前(第一个位置)、中(中间位置)、后(最后一个位置)三个记录中的中间值(按大小排序)作为枢轴

空间复杂度

就空间复杂度来说，主要是递归造成的栈空间的使用，最好情况，递归的深度为log2n，其空间复杂度也就为O(logn)，最坏情况，需要进行n‐1递归调用，其空间复杂度为O(n)，平均情况，空间复杂度也为O(logn)。

冒泡排序

1. 比较相邻的元素。 如果第一个比第二个大，就交换他们两个。
2. 从开始第一对到结尾的最后一对，每对相邻元素都作同样的工作，。 这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

public void sort(int[] arr){
    boolean swaped;
    int temp;
    for(int i = 0;i<arr.length-1;i++){
        swaped = false;
        for (int f = 0;f<arr.length-i-1;f++){
            if (arr[f] > arr[f+1]){
                temp = arr[f];
                arr[f] = arr[f+1];
                arr[f+1] = temp;
                swaped = true;
            }
        }
        if (!swaped){
            return;
        }
    }
}

选择排序

首先在序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

public void sort(int[] arr){
    int max_index;
    int temp;
    for(int i = 0;i<arr.length;i++){
        max_index = 0;
        for (int f = 0;f<arr.length-i;f++){
            if (arr[f] > arr[max_index]){
                max_index = f;
            }
        }
        temp = arr[arr.length-i-1];
        arr[arr.length-i-1] = arr[max_index];
        arr[max_index] = temp;
    }
}

基数排序

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。

public void radix_sort(int[] array){
    int max = array[0];
    for (int i = 0;i<array.length;i++){
        if (array[i] > max){
            max = array[i];
        }
    }
    int time = 0;
    while (max>0){
        max /= 10;
        time++;
    }
    int k = 0;
    int m = 0;
    int n = 1;
    int max_sd = 0;
    int[][] tempArr = new int[10][array.length];
    int[] order = new int[10];
    while (m<time){
        for (int i = 0;i<array.length;i++){
            int sd = (array[i] / n) % 10;
            tempArr[sd][order[sd]] = array[i];
            order[sd]++;
            if (sd>max_sd){
                max_sd = sd;
            }
        }
        for (int i = 0;i<10;i++){
            for (int j = 0;order[i] != 0 && j<order[i];j++){
                array[k++] = tempArr[i][j];
            }
            order[i]=0;
        }
        n *= 10;
        k = 0;
        m++;
    }
}

总结

Algorithm	Average	Best	Worst	extra space	stable
冒泡排序	O(N^2)	O(N)	O(N^2)	O(1)	稳定
直接插入排序	O(N^2)	O(N)	O(N^2)	O(1)	稳定
希尔排序	O(N^1.3)	O(N)	O(N^2)	O(1)	不稳定
简单选择排序	O(N^2)	O(N^2)	O(N^2)	O(1)	不稳定
快速排序	O(NlogN)	O(NlogN)	O(N^2)	O(logN)~O(N^2)	不稳定
归并排序	O(NlogN)	O(NlogN)	O(NlogN)	O(N)	稳定
堆排序	O(NlogN)	O(NlogN)	O(NlogN)	O(1)	不稳定
计数排序	O(d*(N+K))	O(d*(N+K))	O(d*(N+K))	O(N+K)	稳定

排序方法的选择

1. 若n较小(如n≤50)，可采用直接插入或直接选择排序。

　当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。

2. 若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；
3. 若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。

快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的;
若要求排序稳定，则可选用归并排序。

但本章介绍的从单个记录起进行两两归并的排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定 的，所以改进后的归并排序仍是稳定的。

参考资料：

排序总结

常用排序算法总结(性能+代码)

Java常用的八种排序算法与代码实现精解