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));
}
}
通常堆是通过一维数组来实现的。在阵列起始位置为0的情况中 (1)父节点i的左子节点在位置(2i+1); (2)父节点i的右子节点在位置(2i+2); (3)子节点i的父节点在位置floor((i-1)/2);
堆可以分为大根堆和小根堆,这里用最大堆的情况来定义操作:
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)
由于快速排序的思路是找到一个基准值,然后将大于该值得放在右边,小于该值得放在左边
如果此时这个基准值刚好是第k的数,那边左边就是最小的k个数,右边则是最大的k个数
此处以最小的k个数为例
如果当前的基准值不到左边的数不到k个,那么就需要在右边大于基准值的部分选取缺少的个数
如果当前基准值左边的数量大于k个,那么就需要在左边的部分中在选取k个数
直到刚好获取到第k个数
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);
}
}
}