数组排序与折半查找

声明一个数组

int arr[] = {12, 33, 8, 24, 10, 22, 40, 18, 37};
int count = sizeof(arr) / sizeof(arr[0]);
printArray(arr, count);

再声明用来打印数组和交换两个变量的值的function

void printArray(int arr[], int length) {
    printf("%s\n", __func__);
    
    for (int i = 0; i < length; i++) {
        printf("%i   ", arr[i]);
    }
    printf("\n");
}

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

选择排序

拿其中一个值和其他值依次比较，完全比较一轮后，最值出现在第0位。

//选择排序
void sortArray1(int arr[], int count) {
    for (int i = 0; i < count - 1; i++) {
        for (int j = i + 1; j < count; j++) {
            if (arr[i] > arr[j]) {
                swap(arr, i, j);
            }
        }
    }
}

冒泡排序

用相邻的两个元素进行比较，每比较完一轮，最值出现在末尾。

//冒泡排序
void sortArray2(int arr[], int count) {
    for (int i = 0; i < count - 1; i++) {
        for (int j = 0; j < count - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
            }
        }
    }
}

输出结果

printArray
12   33   8   24   10   22   40   18   37   
printArray
8   10   12   18   22   24   33   37   40  

折半查找

• 原理：

1. 数组必须是有序的
2. 必须已知min和max
3. 动态计算mid的值，取出mid对应的值进行比较
4. 如果mid对应的值大于了需要查找的值，那么max要变小为mid-1
5. 如果mid对应的值小于了需要查找的值，那么min要变大为mid+1

//折半查找法
int findKey1(int arr[], int count, int key) {
    int min = 0;
    int max = count - 1;
    int mid = (max + min) / 2;
    while (key != arr[mid]) {
        if (key > arr[mid]) {
            min = mid + 1;
        } else if (key < arr[mid]) {
            max = mid - 1;
        }
        //超出范围，返回-1，说明没有在数组中找到。
        if (min > max) {
            return -1;
        }
        mid = (max + min) / 2;
    }
    return mid;
}