排序算法（Sorting algorithm）（一）一、算法分类二、算法比较三、算法实现分析

86 阅读 0 评论 57 点赞

我是靠谱客的博主淡然蜡烛，最近开发中收集的这篇文章主要介绍排序算法（Sorting algorithm）（一）一、算法分类二、算法比较三、算法实现分析，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

写在前面：
本文章旨在总结备份、方便以后查询，由于是个人总结，如有不对，欢迎指正；另外，内容大部分来自网络、书籍、和各类手册，如若侵权请告知，马上删帖致歉。

参考来源：

https://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95

https://github.com/hustcc/JS-Sorting-Algorithm

https://www.cnblogs.com/sunshineliulu/category/1139260.html

https://www.smslit.top/2018/11/07/algorithm-sort/

https://zoharyip.club/posts/Sort-Algorithms.html

https://www.cnblogs.com/chengxiao/p/6129630.html

https://www.cnblogs.com/dyg0826/p/11369450.html

模型建立：

https://visualgo.net/zh

https://github.com/algorithm-visualizer/algorithm-visualizer

一、算法分类

二、算法比较

三、算法实现分析

1、冒泡排序（Bubble Sort）

2、直接选择排序（Straight Selection sort）

3、直接插入排序（Straight Insertion Sort）

4、希尔排序（Shell Sort）

5、二路归并排序（Two-way Merge Sort）

一、算法分类

比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

二、算法比较

稳定排序算法：会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的，当有两个相等键值的纪录 R和 S，且在原本的列表中 R出现在 S之前，在排序过的列表中 R也将会是在 S之前。

三、算法实现分析

1、冒泡排序（Bubble Sort）

冒泡排序（英语：Bubble Sort）又称为泡式排序，是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

1.1 执行流程：

比较相邻的元素。如果第一个比第二个大，就交换他们两个；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数；
针对所有的元素重复以上的步骤，除了最后一个；
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

1.2 动图演示：

1.3 代码实现：

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

2、直接选择排序（Straight Selection sort）

下称选择排序

选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

2.1 执行流程：

初始状态：无序区为 R[1..n]，有序区为空；
第一趟：在无序区 R[1..n]中选出最小元素，将他 R[1]交换，R[1]为有效区；
第二趟：在无序区 R[2..n]中选出最小元素，将他 R[1]交换，R[1..2]为有效区；
第 n-1趟：在无序区 R[n-1..n]中选出最小元素，将他 R[n-1]交换，R[1..n-1]为有效区；
n-1趟结束，区间 R[1..n]中记录按递增有序排列。

2.2 动图演示：

2.3 代码实现：

void Selection_Sort(int *arr, int len)
{
    int i, j, k, temp;
    for (i = 0; i < len - 1; i++) {
        k = i;
        for (j = i + 1; j < len; j++)
            if (arr[j] < arr[k])
                k = j;
        if(k != i){
            temp = arr[k];
            arr[k] = arr[i];
            arr[i] = temp;	
        }
    }
}

3、直接插入排序（Straight Insertion Sort）

下称插入排序

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place排序（即只需用到 {O(1)} 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

3.1 执行流程：

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤 2~5

3.2 动图演示：

3.3 代码实现：

void Insertion_Sort(int *arr, int len)    
{    
    int i, j, temp;    
    for (i = 1; i < len; i++)
        if (arr[i] < arr[i-1]) {    
            temp = arr[i];    
            for (j = i - 1; j >= 0 && arr[j] > temp; j--)
                arr[j+1] = arr[j];
            arr[j+1] = temp;    
        }
}

4、希尔排序（Shell Sort）

希尔排序（Shell Sort），也称递减增量排序算法，是直接插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于直接插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
但直接插入排序一般来说是低效的，因为直接插入排序每次只能将数据移动一位

4.1 执行流程：

取增量，一般取数组长度 / 2；
按增量取得子序列，对子序列进行插入排序；
将增量递减，重复 1、2步骤；
直至增量均为 0，数列已经排好序。

4.2 动图演示：

4.3 代码实现：

void Shell_Sort(int *arr, int len) {
    int gap, i, j;
    int temp;
    for (gap = len >> 1; gap > 0; gap >>= 1)
        for (i = gap; i < len; i++) {
            temp = arr[i];
            for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                arr[j + gap] = arr[j];
            arr[j + gap] = temp;
        }
}

5、二路归并排序（Two-way Merge Sort）

下称归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
自下而上的迭代。

5.1 执行流程（以递归过程为例）：

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
设定两个指针，最初位置分别为两个已经排序序列的起始位置；
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
重复步骤 3 直到某一指针达到序列尾；
将另一序列剩下的所有元素直接复制到合并序列尾。

总执行分解图：

合并过程如下（以第 2趟归并为例）：

5.2 动图演示：

5.3 代码实现：

#define MIN(x,y)     ((x) < (y) ? (x) : (y))

void Merge_Sort(int *arr, int len) {
    int *a = arr;
    int *b = (int *) malloc(len * sizeof(int));
    int seg, start;
    
    for (seg = 1; seg < len; seg += seg) {
        for (start = 0; start < len; start += seg * 2) {
            int low = start, mid = MIN(start + seg, len), high = MIN(start + seg * 2, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        int *temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        int i;
        for (i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    free(b);
}