几种排序算法

public class MergeSort {


    private static void merge(int a[], int first, int mid, int last) {
        int i = first;
        int j = mid + 1;
        int m = mid;
        int n = last;
        int k = 0;
        // 临时数组保存
        int[] temp = new int[last + 1];
        // 两个数组的左边小于左边 右边小于右边的情况下
        while (i <= m && j <= n) {
            if (a[i] <= a[j]) {
                temp[k++] = a[i++];
            } else {
                temp[k++] = a[j++];
            }
        }
        // 把左边数组或者右边的数组剩下的元素直接添加到临时数组中
        while (i <= m) {
            temp[k++] = a[i++];
        }
        while (j <= n) {
            temp[k++] = a[j++];
        }
        // 赋值给原始数组
        for (i = 0; i < k; i++) {
            a[first + i] = temp[i];
        }
    }


    /**
     * 递归 排序
     *
     * @param a
     * @param first
     * @param last
     */
    private static void mergeSort(int a[], int first, int last) {
        if (first < last && a.length > 1) {
            // 求中位数
            int mid = (first + last) / 2;
            // 左边有序
            mergeSort(a, first, mid);
            // 右边有序
            mergeSort(a, mid + 1, last);
            merge(a, first, mid, last);
        }
    }


    public static void main(String[] args) {
        int[] a = {1, 3, 5, 2, 4, 6, 7, 8};
        mergeSort(a, 0, 7);
        System.out.println(Arrays.toString(a));
    }
}

def max_head(mylist, headsize, root_index):
    # 计算左右子节点索引
    left = root_index*2+1
    right = root_index*2+2
    large_index = root_index
    # 判断左节点的值是否大于父节点
    if left < headsize and mylist[left] > mylist[large_index]:
        large_index = left
    # 判断右节点的值是否大于父节点
    if right < headsize and mylist[right] > mylist[large_index]:
        large_index = right
    #如果做了堆调整则larger的值等于左节点或者右节点的，这个时候做对调值操作
    if large_index != root_index:
        mylist[large_index], mylist[root_index] = mylist[root_index], mylist[large_index]
        max_head(mylist, headsize, large_index)


def create_head(mylist):
    length = len(mylist)
    max_child_index = (length - 2)//2
    #从后往前出数
    for i in range(max_child_index, -1, -1):
        max_head(mylist, length, i)


def sort_head(mylist):
    """
    将根节点取出与最后一位做对调，对前面len-1个节点继续进行对调整过程。
    """
    create_head(mylist)
    for i in range(len(mylist)-1, -1, -1):
        mylist[0], mylist[i] = mylist[i], mylist[0]
        max_head(mylist, i, 0)


if __name__ == "__main__":
    mylist = [49, 38, 65, 97, 76, 13, 27, 49]
    sort_head(mylist)
    print(mylist)

public class TopK {


    /**
     * 快速排序
     *
     * @param a
     * @param start
     * @param end
     * @return
     */
    public static int quickSort(int a[], int start, int end) {
        if (start >= end || a.length <= 1) {
            return -1;
        }
        int i = start;
        int j = end;
        int x = a[i];
        while (i < j) {
            while (i < j && a[j] >= x) {
                j--;
            }
            if (i < j) {
                a[i] = a[j];
                i++;
            }

            while (i < j && a[i] < x) {
                i++;
            }
            if (i < j) {
                a[j] = a[i];
                j--;
            }
        }
        a[i] = x;
//        quickSort(a, start, i - 1);
//        quickSort(a, i + 1, end);
        return i;
    }

    /**
     * 选取第k个数
     *
     * @param arr
     * @param start
     * @param end
     * @param k
     */
    public static int selectK(int arr[], int start, int end, int k) {
        if (start > end || k < 1) {
            return -1;
        }
        if (start == end) {
            return arr[start];
        }
        int temp = quickSort(arr, start, end);
        // 当前左边刚好有k个数(小于基准值)
        if (start + k == temp + 1) {
            return arr[temp];
            // 左边小于基准值得个数大于k
        } else if (start + k < temp + 1) {
            return selectK(arr, start, temp - 1, k);
            // 左边小于基准值得个数小于k(从右边在获取缺少的数量)
        } else {
            return selectK(arr, temp + 1, end, k - (temp - start + 1));
        }
    }


    public static void main(String[] args) {
        int k = 4;
        int a[] = {2, 0, 5, 4, 7, 3, 1};
        System.out.println("第k个数为:" + TopK.selectK(a, 0, a.length - 1, k));
//        quickSort(a, 0, a.length - 1);
        for (int i : a) {
            System.out.println(i);
        }
    }
}