简单的排序和查找

冒泡排序

#include <stdio.h>
/**
O(n^2)
*/
void sort(int arr[],int len);
void sort2(int arr[],int len);
void printArr(int arr[],int len);
int main(){
    int arr[]={51,61,23,65,85,01,36,45,96,47};
    printArr(arr, 10);
    sort(arr, 10);
}

void sort2(int arr[],int len){
    int i,j,t;
    for( i=len-1;i>0;i-- ){
        for( j=0;j<i;j++ ){
            if( arr[j]>arr[j+1] ){
                t=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=t;
            }
        }
        printArr(arr, len);
    }
}

void sort(int arr[],int len){
    int i,j,t;
    for( i=0;i<len-1;i++ ){//趟数
        for( j=0;j<len-i-1;j++ ){//比较次数
            if( arr[j]>arr[j+1] ){
                t=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=t;
            }
        }
        printArr(arr, len);
    }
}

void printArr(int arr[],int len){
    int i;
    for( i=0;i<len;i++ ){
        printf("%d ",arr[i]);
    }
    printf("\n");
}

选择排序

#include <stdio.h>
/**
O(^2)
*/
void printArr(int arr[], int len);
void sort(int arr[], int len) {
    int i, j, min, t;
    for (i = 0; i < len-1; i++) {//比较趟数
        min = i;
        for (j = i + 1; j < len; j++) {//比较次数
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        t = arr[min];
        arr[min] = arr[i];
        arr[i] = t;
        printArr(arr, len);
    }
}
int main(void) {
    int arr[] = {51, 61, 23, 65, 85, 01, 36, 45, 96, 47};
    printArr(arr, 10);
    sort(arr, 10);
}

void printArr(int arr[], int len) {
    int i;
    for (i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

插入排序

#include <stdio.h>
/**
O(log2n)
*/
void printArr(int arr[], int len);
void sort(int arr[], int len) {
    int i,j,t;
    for( i=1;i<len;i++ ){
        t=arr[i];
        j=i-1;
        while( j>=0&&arr[j]>t ){
            arr[j+1]=arr[j];
            j--;
        }
        arr[j+1]=t;
        printArr(arr, len);
    }
}
int main(void) {
    int arr[] = {51, 61, 23, 65, 85, 01, 36, 45, 96, 47};
    printArr(arr, 10);
    sort(arr, 10);
}

void printArr(int arr[], int len) {
    int i;
    for (i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

二分查找

#include <stdio.h>

int serach(int arr[],int len,int target){
    int left=0,right=len-1;
    int mid;
    while (left<=right) {
        mid=(left+right)/2;
        if( arr[mid]==target ){
            return mid;
        }else if( arr[mid]>target ){
            right=mid-1;
        }else{
            left=mid+1;
        }
    }
    return -1;
}

int main(void) {
    int arr[] = {1,2,3,4,5,6,7,8,9,10};
    int len=10;
    int r5=serach(arr, len, 5);
    int r8=serach(arr, len, 8);
    int r50=serach(arr, len, 50);
    printf("num:%d,position:%d\n",5,r5);
    printf("num:%d,position:%d\n",8,r8);
    printf("num:%d,position:%d",50,r50);
}