后端研发面试题目总结

最近一段时间面试n多公司，总结算法题目如下。

一

1 将数组中奇数置前偶数置后

void classify(int arr[],int n){
    int left = 0;
    int right = n-1;
    while (left < right){
        while(left < right && arr[right]%2==0){
            right--;
        }

        while(left < right && arr[left]%2==1){
            left++;
        }

        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
    }
}

2快速排序

void swap(int arr[],int left,int right){
    int tmp = arr[left];
    arr[left] = arr[right];
    arr[right] = tmp;
}

void Qsort(int arr[],int left,int right){
    if (left < right){
        int tmp = arr[left];
        int i = left;
        int j = right;
        while (i<j){
            while (arr[j]>tmp && i<j){
                j--;
            }

            while (arr[i]<tmp && i<j){
                i++;
            }

            if (i<j){
                swap(arr[i],i,j);
            }
            arr[left]=arr[i];
            arr[i]=tmp;

            Qsort(arr,left,i-1);
            Qsort(arr,i+1,right);
    }
}

堆排序

#include <stdio.h>

void swap(int arr[],int i,int j){
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] =t;
}


void maxHeapAdjust(int arr[],int p,int n){
    int left = 2*p+1;
    int right = 2*p+2;
    int max = p;
    if (left < n && arr[left]>arr[p]){
        max = left;
    }
    if (right < n && arr[right]>arr[max]){
        max = right;
    }
    if (max!=p){
        swap(arr,p,max);
        maxHeapAdjust(arr,max,n);
    }
}



//初始化最大堆
void buildMaxHeap(int arr[],int n){
    for(int i=(n-1)/2;i>=0;i--){
        maxHeapAdjust(arr,i,n);
    }
}



/**
 * 堆排序
 * @param arr
 * @param size
 */
void heapSort(int arr[],int size){
    buildMaxHeap(arr,size);

//    for (int i = 0; i < size ; ++i) {
//        printf("%d---\n",arr[i]);
//    }

    for (int i = size-1; i >=0 ; i--) {
        int tmp = arr[0];
        arr[0] = arr[i];
        arr[i]=tmp;
        maxHeapAdjust(arr,0,i-1);
    }

}
int main(){
    int arr[] = {3,5,8,9,1,4,7,6,2,12,3};
    heapSort(arr, sizeof(arr)/ sizeof(int));
    for (int i = 0; i < sizeof(arr)/ sizeof(int) ; ++i) {
        printf("%d---\n",arr[i]);
    }
    return 0;
}

image.png