Datawhale 系列数据结构
Task3.1 排序
3.1.1归并
//采用分治(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并，得到完全的序列
public static int [] mergeSort(int []arr){
int len =arr.length;
if(len<2){
return arr;
}
int [] left=Arrays.copyOfRange(arr,0,len/2);
int [] right=Arrays.copyOfRange(arr,len/2,len);
return merge(mergeSort(left),mergeSort(right));
}
public static int [] merge(int [] left,int [] right){
int llen=left.length;
int rlen=right.length;
int[] res=new int[llen+rlen];
int li=0,ri=0,rei=0;
while (llen-li>0 && rlen-ri>0) {
if (left[li] <= right[ri]) {
res[rei++]=left[li++];
} else {
res[rei++]=right[ri++];
}
}
while (llen-li>0) {
res[rei++]=left[li++];
}
while (rlen-ri>0) {
res[rei++]=right[ri++];
}
return res;
}
3.1.2 快速排序
/*快速排序使用分治法来把一个list分为两个子list:
*从数列中跳出一个元素，称为“基准”（pivot）
*重新排序数列，所有元素比基准小的摆放在基准前面，所有比基准大的放在基准后面。在这个分区推出后，该基准就处于数列的中间位置。这个称为分区操作。
*递归的，把小于基准值元素的子数列和大于基准值元素的子数列排序
*/
public static int partition(int []array,int lo,int hi){
//固定的切分方式
int key=array[lo];
while(lo<hi){
while(array[hi]>=key&&hi>lo){//从后半部分向前扫描
hi--;
}
array[lo]=array[hi];
while(array[lo]<=key&&hi>lo){从前半部分向后扫描
lo++;
}
array[hi]=array[lo];
}
array[hi]=key;
return hi;
}
public static void sort(int[] array,int lo ,int hi){
if(lo>=hi){
return ;
}
int index=partition(array,lo,hi);
sort(array,lo,index-1);
sort(array,index+1,hi);
}
3.1.3 插入
public static int [] insertionSort(int []arr){
for(int i=0;i<arr.length;i++){
for(int j=i;j>0;j--){
if(arr[j]<arr[j-1]){
int temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
}
}
}
return arr;
}
3.1.4 冒泡
public static int [] bubbleSort(int [] arr){
for(int i= 0;i<arr.length-1;i++){
for(int j=0;j<arr.length-1-i;j++){
if(arr[j]>arr[j+1]){
int temp =arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
return arr;
}
3.1.5 选择
public static int [] selectionSort(int [] arr){
int min = 0;
for(int i=0;i<arr.length-1;i++){
for(int j=i+1;j<arr.length-1;j++){
min = arr[i];
if(arr[j]<min){
min=arr[j];
arr[j]=arr[i];
arr[i]=min;
}
}
}
return arr;
}
3.1.6 堆排序(选做)
/*堆排序分为三个步骤：
* 创建最大堆
* 确保最大堆中父节点的值比子节点的值都大
* 将根节点与最后一个叶子节点比较，择其大者剔除出堆，再重复第2、3步。
*第二步是整个堆排序的关键。
*/
public static void maxHeapify(int[] array, int heapsize, int i){
int l = 2*i + 1;
int r = 2*i + 2;
int large = i;
if (l < heapsize && array[i] < array[l]) {
large = l;
}else {
large = i;
}
if (r < heapsize && array[large] < array[r]) {
large = r;
}
if (large != i) {
int temp = array[i];
array[i] = array[large];
array[large] = temp;
//因为将最大值和父节点交换了位置，新的子节点并不能保证一定是比它的子节点大
//所以需要递归，确定交换的子节点比它的子节点都大
//而没有动的子节点是不需要进行递归的，因为它的数值没有变，如果之前满足最大堆条件，现在就还是满足的
maxHeapify(array, heapsize, large);
}
}
//创建堆
public static void buildMaxHeap(int[] array){
int heapsize = array.length;
for (int i = heapsize/2; i >= 0; i--) {
maxHeapify(array,heapsize,i);
}
}
public static void heapSort(int[] array){
int heapsize = array.length;
for (int i = heapsize - 1; i > 0; i--) {
if (array[i] < array[0]) {
int temp = array[0];
array[0] = array[i];
array[i] = temp;
heapsize --;
maxHeapify(array, heapsize, 0);
}
}
}
3.1.8 编程实现 O(n) 时间复杂度内找到一组数据第 K 大元素
//采用堆排序的方法
//在创建最小堆，只创建K个元素
public static void maxHeapify(int[] array, int size, int i) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int small = i;
if (left < size) {
if (array[small] > array[left]) {
small = left;
}
}
if (right < size) {
if (array[small] > array[right]) {
small = right;
}
}
if (small != i) {
int temp = array[small];
array[small] = array[i];
array[i] = temp;
maxHeapify(array, size, small);
}
}
public static void buildHeap(int[] array, int size) {
for (int i = size - 1; i >= 0; i--) {
maxHeapify(array, size, i);
}
}
public static int findKByHeap(int[] array, int k) {
buildHeap(array, k);
for (int i = k + 1; i < array.length; i++) {
if (array[i] > array[0]) {
int temp = array[i];
array[i] = array[0];
array[0] = temp;
maxHeapify(array, k, 0);
}
}
return array[0];
}
TASK3.2 查找
3.2.1 实现一个有序数组的二分查找
//默认数组是有序数组
public static int biSearch(int [] arr, int target){
int r = arr.length-1;
int l = 0;
int mid=r/2;
while(l<=r){
mid=(l+r)/2;
if(arr[mid]==target)
return mid;
else if(arr[mid]>target)
r=mid;
else
l=mid;
}
return -1;
}
3.2.2 实现模糊二分查找算法（比如大于等于给定值的第一个元素）
//模糊二分查找，返回大于等于给定值的第一个值的下标
public static int blurrySearch(int [] arr, int target){
int r = arr.length-1;
int l = 0;
int mid=r/2;
while(l<=r){
mid=(l+r)/2;
if(arr[mid]==target)
return mid;
else if(arr[mid]>target)
r=mid-1;
else
l=mid+1;
}
return r+1;
}
3.2.3 Sqrt(x)（x的平方根）
class Solution {
public int mySqrt(int x) {
if(x==1) return 1;
int min=0;
int max = x;
while(max-min>1){
int m=(max+min)/2;
if(x/m<m) max=m;
else min = m;
}
return min;
}
}
