排序算法（1）

本此介绍十大经典排序算法的前五个：

• 冒泡排序
• 选择排序
• 插入排序
• 希尔排序
• 归并排序

冒泡排序

算法步骤

1. 比较相邻元素的大小如果第一个小于第二个就交换他们的位置
2. 循环比较每一对，最后一个元素会是最小的元素
3. 重复上面的操作，除了最后一个，因为最后一个已经确定
4. 继续重复比较直到全部比较完成，或某次比较没有任何元素交换

代码实现

void bubble_sort(int *list,int len)
{
    int i,j,temp,flag;

    for (i = 0; i < len - 1; i++)
    {
        flag = 1;

        for (j = 0; j < len - 1 - i; j++)
        {
            if (list[j] < list[j+1] )
            {
                temp = list[j+1];
                list[j+1] = list[j];
                list[j] = temp;
                flag = 0;
            }
        }

        if (flag)
        {
            break;
        }
    }
}

---

选择排序

算法步骤

1. 从未排序的数组中找到最大的元素放到起始位置
2. 从剩下的元素中找到最大的元素放到起始位置之后
3. 重复上面的操作，直到所有元素排序完成

代码实现

void sellection_sort(int *list,int len)
{
    int i,j,temp;
    for (i = 0; i < len; i++)
    {
        for (j = i+1; j < len; j++)
        {
            if (list[i] < list[j] )
            {
                temp = list[i];
                list[i] = list[j];
                list[j] = temp;
            }
        }
    }
}

---

插入排序

算法步骤

1. 将第一个元素当做有序数组
2. 将第二个元素插入到合适的位置，此时前两个元素是有序的
3. 再将第三个元素插入到前两个元素中合适的位置，此时前三个元素是有序的
4. 重复上面操作，直到排序完成
5. 在插入过程中，如果有插入操作就进行下一个元素的插入

代码实现

void instertion_sort(int *list,int len)
{
    int i,j,temp;
    for (i = 1; i < len; i++)
    {
        for (j = i; j > 0; j--)
        {
            if (list[j-1] < list[j] )
            {
                temp = list[j-1];
                list[j-1] = list[j];
                list[j] = temp;
            }
            else
            {
                break;
            }
        }
    }
}

---

希尔排序

算法步骤

1. 选择一个增量，根据增量可以得到每次排序的间隔（例如：10个元素，增量为2，则间隔为5(10/2),2(5/2),1(2/2) ）
2. 按间隔进行比较，如果满足条件就交换位置。
3. 重复上面的操作，直到间隔小于1结束

代码实现

void shell_sort(int *list,int len)
{
    int h = 1;
    int tmp = 0;
    while (h < len/2)
    {
        h =2 * h;
    }

    while (h)
    {
        for (int i = 0; i < h; i++)
        {
            for (int j = len - 1; j >= 0; j -= h)
            {
                if (list[j] > list[j-h])
                {
                    tmp = list[j-h];
                    list[j-h] = list[j];
                    list[j] = tmp;
                }
            }
        }

        h = h / 2;
    }

    return;

}

---

归并排序

算法步骤

1. 将数组从中间分为两部分
2. 将这个两部分继续从其中间分开
3. 重复上面的操作，直到两边只有一个元素
4. 从最下层开始，两部分对应元素进行比较并排序，合并到一起，如果一部分没有元素，将仍有元素的直接加到末尾

代码实现

void merge(int *list, int first, int mid, int last, int *temp)
{
    int i = first, j = mid + 1; // i为第一组的起点, j为第二组的起点
    int m = mid, n = last;      // m为第一组的终点, n为第二组的终点
    int k = 0;                  // k用于指向temp数组当前放到哪个位置
    while (i <= m && j <= n)
    {                           // 将两个有序序列循环比较, 填入数组temp
        if (list[i] <= list[j])
            temp[k++] = list[j++];
        else
            temp[k++] = list[i++];
    }
    while (i <= m)
    {                           // 如果比较完毕, 第一组还有数剩下, 则全部填入temp
        temp[k++] = list[i++];
    }
    while (j <= n)
    {                           // 如果比较完毕, 第二组还有数剩下, 则全部填入temp
        temp[k++] = list[j++];
    }
    for (i = 0; i < k; i++)
    {                           // 将排好序的数填回到数组的对应位置
        list[first + i] = temp[i];
    }
}

void merge_sort(int *list, int first, int last, int *tmp)
{
    if (first < last)
    {
        int mid = (first + last) / 2;
        merge_sort(list, first, mid, tmp); // 递归归并左边元素
        merge_sort(list, mid + 1, last, tmp); // 递归归并右边元素
        merge(list, first, mid, last, tmp); // 再将二个有序数列合并
    }

}

算法原理的学习以及算法图片来自程序员吴师兄