常见查找、排序算法的实现

• 查找
• 排序

---

  以下是部分常见排序查找算法的实现，后期会继续补充。

查找

二分查找

static int binarySerach(int *array, int count, int key)
{
    int left = 0;
    int right = count - 1;

    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (array[mid] == key)
            return mid;
        else if (array[mid] < key)
            left = mid + 1;
        else if (array[mid] > key)
            right = mid - 1;
    }

    return -1;
}

注：
  二分查找针对的是有序递增序列，思路比较简单，但有一点需要注意的是：结束条件必须为left <= right,这里必须是闭合空间。最简单的例子，如果数组为（1，3，5），如果寻找5，那么left < right的条件就找不到，left和right最终可以相等。

排序

冒泡排序

static void BubbleSort(int *a, int len)
{
    int i, j, temp;
    for (j = 0; j < len - 1; j++)
    {
        for (i = 0; i < len - 1 - j; i++)
        {
            if (a[i] < a[i + 1])
            {
                temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp;
            }
        }
    }
}

注：
  冒泡排序的思路是：分为内外循环，第i次外循环将第i大的值放到合适位置，内循环次数每次减少1。

选择排序

void Selection_Sort(int *a, int n)
{
    int i, j, k, min;

    for (i = 0; i < n; i++)
    {
        min = a[i];
        for (j = i + 1; j < n; j++)
        {
            if (a[j] < min)
            {
                min = a[j];
                k = j;
            }
        }

        if (min != a[i])
            swap(a[i], a[k]);
    }
}

注：
  选择排序其实效率并不高，它也只适合数量较少的数据，其基本思路也很简单：每轮循环找到最小的数，然后放到正确的位置。

快速排序

int a[100];
int quicksort(int left, int right)
{
    int i, j, t, temp;

    if (left > right)
        return;

    temp = a[left];
    i = left;
    j = right;

    while (i != j)
    {
        while (a[j] >= temp && i < j)
        {
            j--;
        }

        while (a[i] <= temp && i < j)
        {
            i++;
        }
        
        if (i < j)
        {
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }

        a[left] = a[i];
        a[i] = temp;
        quicksort(left, i - 1);
        quicksort(i + 1, right);
    }
}

注：
  快速排序的思路简而言之就是：选择一个基准，定义两个指针，分别从数组两侧进行遍历，左指针的目标是找一个比基准大的值，右指针的目标是找一个比基准小的值，找到后，将二者位置交换，直到左序列都比基准数小，右侧都比基准数大，最终左指针会和右指针相遇，这个位置就是基准数应该在的位置，那么就将基准数与此交换。第一次之后，左右序列都成为了相对有序序列，但是内部还是混乱，那么使用快排递归，直到整个数组有序。
  关于这个排序算法，建议访问：链接，这篇博客里的讲解很形象。