必备知识点（四）

数据结构

排序

插入类排序

直接插入排序

void InsertSort(int R[], int n){
    for(int i = 1 ; i < n ; ++i){
        int j = i - 1;
        int temp = R[i];
        // 不断往前替换
        while(j > 0 && temp < R[j]){
            R[j+1] = R[j];
            --j;
        }
        R[j+1] = temp;
    }
}

折半插入排序

void BinaryInsertSortup(int R[], int n){
    for(int i = 1 ; i < n ; ++i){
        int right = i - 1;
        int temp = R[i];
        int left = 0;
        while(right <= left){
            int mid = (left + right) / 2;
            if(temp >= R[mid])
                left = mid + 1;
            else if(temp < R[mid])
                right = mid - 1;
        }
        int k = i - 1;
        for(; k > right ; --k)
            R[k+1] = R[k];
        R[j+1] = temp;
    }
}

交换类排序

起泡排序

void BubbleSort(int R[], int n){
    for(int i = n - 1 ; i > 1 ; --i){
        int flag = 0;  //是否交换标志
        for(int j = 1 ; j <= i ; ++j){
            if(R[j-1] > R[j]){
                flag = 1；
                int temp = R[j];
                R[j] = R[j+1];
                R[j+1] = temp；
            }
        }
        if(flag == 0)
            break;
    }
}

快速排序

void QuickSort(int R[], int low, int high){
    int i = low, j = high;
    if(low < high){
        int temp = R[low];
        while(i < j){
            while(i < j && temp <= R[j])
                --j;
            // 此时R[j]<temp，所以放到左边
            if(i < j){
                R[i] = R[j];
                ++i;
            }
            while(i < j && temp > R[i])
                ++i;
            // 此时R[i]>temp，所以放到右边
            if(i < j){
                R[j] = R[i];
                --j;
            }
            R[i] = temp;  // 将最开始的R[i]放到合适位置
        }
        // 两边递归
        QuickSort(int R[], int low, int i-1)；
        QuickSort(int R[], int i+1, int high)；
    }
}

选择类排序

简单选择排序

void SelectSort(int R[], int n){
    for(int i = 0 ; i < n ; ++i){
        int k = i;
        for(int j = i+1 ; j < n ; ++j){
            if(R[j] < R[k])
                k = j;
        }
        temp = R[i];
        R[i] = R[k];
        R[k] = temp;
    }
}

多路归并排序

直接拿letcode题目来做例子吧~（letcode 23）
算是暴力归并吧（两两比较合成一个）

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0) return null;
        int left = 0; int right = lists.length - 1;
        while(right > 0) {
            while(left < right) {
                lists[left] = merge(lists[left], lists[right]);
                left++;
                right--;
            }
            left = 0;
        }
        return lists[0];
    }
    private ListNode merge(ListNode node1, ListNode node2) {
        ListNode head = new ListNode(0);
        ListNode pre = head;
        while(node1 != null && node2 != null) {
            if(node1.val < node2.val){
                pre.next = node1;
                node1 = node1.next;
                pre = pre.next;
            } else {
                pre.next = node2;
                node2 = node2.next;
                pre = pre.next;
            }
        }
        pre.next = node1 == null ? node2 : node1;
        return head.next;
    }
}