【算法基础——第六讲】排序

大家好，我是quicklysleep，欢迎大家光临我的博客,算法学习笔记系列持续更新中~

• 一、前言
• 二、排序算法的介绍
• 三、排序算法的运用
• • 1.快速排序模板
  • 2.冒泡排序模板
  • 3.归并排序模板
• 最后

排序算法是最基本的算法之一。

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

图片来自百度,方便大家了解各种排序算法的时间复杂度以及更好的应用.

这里主要介绍冒泡排序,快速排序,归并排序.(其实博主不会别的排序算法)
推荐看一下动图演示,百度可以搜到,可以更直观理解.
重点在排序算法的思想,常用的主要就几个.

算法步骤
1.确定分界点

2.调整区间，使x左边的区间都小于等于x（此时区间内不一定是有序的），右边则大于

3.递归处理左右两段

如下：

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

算法步骤

1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

3.针对所有的元素重复以上的步骤，除了最后一个。

4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

如下：

void bubble_sort(T arr[], int len) {
        int i, j;
        for (i = 0; i < len - 1; i++)
                for (j = 0; j < len - 1 - i; j++)
                        if (arr[j] > arr[j + 1])
                                swap(arr[j], arr[j + 1]);
}

算法步骤

1.确定分界点为首末中点

2.以中点为界，递归排序中点两侧使其有序

3.归并，合二为一

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

莫言真理无穷尽，寸进自有寸进欢·