顺序表的简单插入排序和折半查找c语言

顺序表的简单插入排序：

void InsertSort(int* a, int n)
{
    int i, j, temp;
    for(i = 1; i < n; ++i)
    {
        temp = a[i];
        for(j = i - 1; j >= 0 && a[j] > temp; --j)
            a[j + 1] = a[j];
        a[j + 1] = temp;
    }
}

折半查找：

int BinarySearch(int* a, int n, int key)
{
    int low = 0, high = n - 1, mid;
    while(low <= high)
    {
        mid = (low + high) / 2;
        if(a[mid] == key)
            return mid;
        else if(a[mid] > key)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1;
}

相关问题

用C语言在顺序表上完成以下完整的操作： 1、直接插入排序 2、折半插入排序 3、希尔排序 4、冒泡排序 5、快速排序 6、简单选择排序 7、堆排序 8、二路归并排序 9、顺序查找 10、折半查找

以下是C语言实现的各种排序和查找算法的代码示例：

1. 直接插入排序：

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

2. 折半插入排序：

void binaryInsertionSort(int arr[], int n) {
    int i, key, j, low, high, mid;
    for (i = 1; i < n; i++) {
        key = arr[i];
        low = 0;
        high = i - 1;
        while (low <= high) {
            mid = (low + high) / 2;
            if (key < arr[mid])
                high = mid - 1;
            else
                low = mid + 1;
        }
        for (j = i - 1; j >= low; j--)
            arr[j + 1] = arr[j];
        arr[low] = key;
    }
}

3. 希尔排序：

void shellSort(int arr[], int n) {
    int gap, i, j, temp;
    for (gap = n / 2; gap > 0; gap /= 2) {
        for (i = gap; i < n; i++) {
            temp = arr[i];
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
                arr[j] = arr[j - gap];
            arr[j] = temp;
        }
    }
}

4. 冒泡排序：

void bubbleSort(int arr[], int n) {
    int i, j, temp;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

5. 快速排序：

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

6. 简单选择排序：

void selectionSort(int arr[], int n) {
    int i, j, min_idx;
    for (i = 0; i < n - 1; i++) {
        min_idx = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx])
                min_idx = j;
        }
        swap(&arr[min_idx], &arr[i]);
    }
}

7. 堆排序：

void heapify(int arr[], int n, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    if (l < n && arr[l] > arr[largest])
        largest = l;
    if (r < n && arr[r] > arr[largest])
        largest = r;
    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    for (int i = n - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
}

8. 二路归并排序：

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1], R[n2];
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

9. 顺序查找：

int linearSearch(int arr[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == x)
            return i;
    }
    return -1;
}

10. 折半查找：

int binarySearch(int arr[], int l, int r, int x) {
    if (r >= l) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);
        return binarySearch(arr, mid + 1, r, x);
    }
    return -1;
}

C语言，编写具体函数实现查找表的顺序查找与折半查找等基本操作时遇到的问题和解决方法

在实现顺序查找和折半查找时，常见的问题有以下几种：

1. 顺序查找时，查找数据量大时效率低下的问题。
解决方法：可以使用哈希表等更高效的数据结构进行查找。

2. 折半查找时，数组必须是有序的，如果数组未排序，则需要先排序，这会增加时间复杂度。
解决方法：可以在数据插入时就保证数组有序，或者使用其他排序算法，如快速排序、归并排序等。

3. 折半查找时，当数组中存在重复元素时，无法保证查找到的是第一个或最后一个重复元素。
解决方法：可以通过修改查找条件，查找第一个或最后一个重复元素。

4. 折半查找时，查找元素不在数组中时，可能会一直循环下去。
解决方法：可以设置查找的上限和下限，当查找到上限或下限时，即可判断查找失败。

以下是C语言中实现顺序查找和折半查找的代码示例：

1. 顺序查找

int seq_search(int *a, int len, int key)
{
    for (int i = 0; i < len; ++i)
    {
        if (a[i] == key)
        {
            return i;
        }
    }
    return -1;  // 查找失败
}

2. 折半查找

int bin_search(int *a, int len, int key)
{
    int left = 0, right = len - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (a[mid] == key)
        {
            return mid;
        }
        else if (a[mid] < key)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    return -1;  // 查找失败
}