查找和排序

排序

选择排序

选择排序通过每次选择未排序部分中的最小（或最大）元素，将其放置到已排序部分的末尾来排序整个数组。

时间复杂度：O(n^2)

#include <stdio.h>

int main()
{
    int a[10] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};
    int i, j, t;
    for (i = 0; i < 9; i++)
    {
        int min = i;
        for (j = i + 1; j < 10; j++)
        {
            if (a[min] > a[j])
            {
                min = j;
            }
        }
    }
    for (i = 0; i < 10; i++)
    {
        printf("%d ", a[i]);
    }
    // 暂停
    getchar();
    return 0;
}

冒泡排序

冒泡排序通过反复交换相邻的元素来逐步把较大的元素“冒泡”到数组的末尾，直到数组完全有序。
在每一轮遍历中，算法从数组的开始位置出发，依次比较相邻的两个元素。如果前一个元素大于后一个元素，则交换它们的位置。
每一轮遍历结束后，最大值会被移到数组的末尾，因此下一轮遍历时，可以忽略这个已经排序的部分。

#include <stdio.h>

int main()
{
    int a[10] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};
    int i, j, t;
    for (i = 0; i < 9; i++)
    {
        for (j = 0; j < 9 - i; j++)
        {
            if (a[j] > a[j + 1])
            {
                t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
            }
        }
    }
    for (i = 0; i < 10; i++)
    {
        printf("%d ", a[i]);
    }
    // 暂停
    getchar();
    return 0;
}

插入排序

插入排序通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

#include <stdio.h>

int main()
{
    int a[10] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};
    int i, j, t;
    for (i = 1; i < 10; i++)
    {
        t = a[i];
        for (j = i - 1; j >= 0 && a[j] > t; j--)
        {
            a[j + 1] = a[j];
        }
        a[j + 1] = t;
    }
    for (i = 0; i < 10; i++)
    {
        printf("%d ", a[i]);
    }
    // 暂停
    getchar();
    return 0;
}

折半插入排序

折半插入排序是对插入排序的一种改进，它通过减少比较次数来提高排序效率。

#include <stdio.h>

int main()
{
    int a[10] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};
    int i, j, t;
    for (i = 1; i < 10; i++)
    {
        int low = 0, high = i - 1;
        t = a[i];
        while (low <= high)
        {
            int mid = (low + high) / 2;
            if (a[mid] > t)
            {
                high = mid - 1;
            }
            else
            {
                low = mid + 1;
            }
        }
        for (j = i - 1; j >= low; j--)
        {
            a[j + 1] = a[j];
        }
        a[low] = t;
    }
    for (i = 0; i < 10; i++)
    {
        printf("%d ", a[i]);
    }
    // 暂停
    getchar();
    return 0;
}

快速排序

快速排序是对冒泡排序的一种改进，它通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

#include <stdio.h>

void quickSort(int a[], int low, int high)
{
    if (low >= high)
        return;
    int i = low, j = high, t = a[low];
    while (i < j)
    {
        while (i < j && a[j] >= t)
            j--;
        while (i < j && a[i] <= t)
            i++;
        if (i < j)
        {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
    a[low] = a[i];
    a[i] = t;
    quickSort(a, low, i - 1);
    quickSort(a, i + 1, high);
}

int main()
{
    int a[10] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};
    quickSort(a, 0, 9);
    for (int i = 0; i < 10; i++)
    {
        printf("%d ", a[i]);
    }
    // 暂停
    getchar();
    return 0;
}

查找

折半查找

折半查找是对于有序数组的一种查找方法，它通过将待查找的元素与数组的中间元素进行比较，如果待查找元素小于中间元素，则在数组的前半部分继续查找，否则在数组的后半部分继续查找。

需要数组有序
中间 mid 使用low + (high - low) / 2防止溢出（mid = (low + high) / 2 有可能溢出）

#include <stdio.h>

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

int main()
{
    int a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    printf("%d\n", binarySearch(a, 10, 5));
    // 暂停
    getchar();
    return 0;
}

查找和排序 ​

排序 ​

选择排序 ​

冒泡排序 ​

插入排序 ​

折半插入排序 ​

快速排序 ​

查找 ​

折半查找 ​