常用排序算法(一)插入排序、希尔排序、冒泡排序

红太狼 2022-05-18 09:26 159阅读 0赞

[常用排序算法(二)选择排序、快速排序][Link 1]  
[常用排序算法(三)归并排序、堆排序、基数排序][Link 2]

### 1. 插入排序 ###

##### 算法 #####

最简单的排序算法之一是插入排序（insertion sort）。插入排序由N-1趟（pass）排序组成。对于P=1趟到P=N-1趟，插入排序保证从位置0到位置P上的元素为已排序状态。插入排序利用了这样的事实：位置0到位置P-1上的元素是已排过序的。下图显示一个简单的数组在每一趟插入排序后的情况。  
![这里写图片描述][70]  
C语言给出算法参考程序如下，显然，插入排序算法复杂度为O(N2)  O ( N 2 ) ，输入为逆序的时候达到最坏边界。

void InsertionSort(int a[], int n)
    {
        int i, j;
        for (i = 1; i < n; i++)
        {
            int temp = a[i];
            for (j = i; j > 0 && temp < a[j - 1]; j--)      
                a[j] = a[j - 1];
            a[j] = temp;
        }
    }

##### 改进版的插入排序 #####

我们知道，插入排序利用了这样的事实：位置0到位置P-1上的元素是已排过序的。那么对于前面已排好序的序列，将数据找到合适的位置插入，一个比较不错的方法是用二分法找到插入位置，然后将该位置后直到P-1位置处的数据都往后移动一位。具体实现代码读者可自行实践。  
二分插入排序的平均时间复杂度仍然为O(n2)，空间复杂度为O(1)，挪动的次数不变，只是减少了比较的次数，时间上会比直接插入排序要快一些，但时间复杂度不变。

### 2. 希尔排序 ###

希尔排序（Shellsort）通过比较相距一定间隔的元素来工作，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序未知，由于这个原因，希尔排序有时也叫作缩小增量排序(diminishing increment sort)。  
希尔排序使用一个序列h1,h2,…,ht，叫做增量序列(increment sequence)。只要h1=1,任何增量序列都是可行的，不过，有些增量序列比另外一些增量序列更好。在使用增量hk的一趟排序之后，对于每一个i我们有A\[i\]<=A\[i+hk\]：所有相隔hk的元素都被排序。此时称文件是hk-排序（hk-sorted）的。下图显示各趟排序后数组的情况。  
![这里写图片描述][70 1]  
仔细的考查可以发现，一趟hk-排序的作用就是对hk个独立的子数组执行一次插入排序。

void ShellSort(int a[], int n)
    {
        for (int increment = n / 2; increment > 0; increment /= 2)
        {
            for (int i = increment; i < n; i++)
            {
                for (int j = i; j >= increment; j -= increment)
                {
                    if (a[j] < a[j - increment])
                    {
                        int temp = a[j];
                        a[j] = a[j - increment];
                        a[j - increment] = temp;
                    }
                    else
                        break;
                }
            }
        }
    }

希尔排序的最差时间复杂度是O(n2)，最优时间复杂度是O(n)，平均时间复杂度为O(n1.5)，需要强调的是，希尔排序的平均时间复杂度与增量的选择有关，在我的实现中使用的是折半的方法，不一定是最好的增量序列，查阅资料表明，当增量之间成倍数关系时效率其实是不高的。希尔排序的时间复杂度比快速排序要高，它的优势在于平均情况下和最差情况下的表现接近，在这点上比快排有优势，并且易于实现。因此有资料表明，任何排序工作在一开始都可以用希尔排序来做，在表现不佳的时候，再换成快速排序来做。本质上讲，希尔排序算法是直接插入排序算法的一种改进，减少了其复制的次数，速度要快很多。 原因是，当n值很大时数据项每一趟排序需要的个数很少，但数据项的距离很长。当n值减小时每一趟需要和动的数据增多，此时已经接近于它们排序后的最终位置。正是这两种情况的结合才使希尔排序效率比插入排序高很多。

### 3. 冒泡排序 ###

##### 算法 #####

冒泡算法的主要逻辑是，假设有N个数，游标从第一位数开始，若左边的数比右边的数大，则左边交换，游标移向下一位直到最后一位。在游标移动过程中，可以保证，右边的数一定比左边的数大，因为第一轮遍历是要找出最大的数，并且最大的数在最后一位。同理，要找出第二大的数，重复上述过程，直至找出第N大的数，排序结束。  
举例说明：要排序数组：int\[\] arr=\{34,8,64,51,32,21\};  
第一趟排序：

第一次排序：34和8比较，34大于8，交换位置： 8 34 64 51 32 21

第二次排序：34和64比较，34小于64，不交换位置：8 34 64 51 32 21

第三次排序：64和51比较，64大于51，交换位置： 8 34 51 64 32 21

第四次排序：64和32比较，64大于32，交换位置：8 34 51 32 64 21

第五次排序：64和21比较：64大于21，交换位置： 8 34 51 32 21 64

第一趟总共进行了5次比较，找到最大的数。 排序结果： 8 34 51 32 21 64

--------------------

第二趟排序：

第一次排序：8和34比较，8小于34，不交换位置：8 34 51 32 21 64

第二次排序：34和51比较，34小于51，不交换位置： 8 34 51 32 21 64

第三次排序：51和32比较，51大于32，交换位置：8 34 32 51 21 64

第四次排序：51和21比较，51大于21，交换位置： 8 34 32 21 51 64

第二趟总共进行了4次比较，找到次大的数。 排序结果： 8 34 32 21 51 64

--------------------

第三趟排序：

第一次排序：8和34比较，8小于34，不交换位置： 8 34 32 21 51 64

第二次排序：34和32比较，34大于32，交换位置：8 32 34 21 51 64

第三次排序：34和21比较，34大于21，交换位置： 8 32 21 34 51 64

第二趟总共进行了3次比较，找到第三大的数。 排序结果： 8 32 21 34 51 64

--------------------

第四趟排序：

第一次排序：8和32比较，8小于32，不交换位置：8 32 21 34 51 64

第二次排序：32和21比较，32大于21，交换位置： 8 21 32 34 51 64

第二趟总共进行了2次比较，找到第四大的数。 排序结果： 8 21 32 34 51 64

--------------------

第五趟排序：

第一次排序：8和21比较，8小于21，不交换位置： 8 21 32 34 51 64

第二趟总共进行了1次比较，找到第五大的数。 排序结果： 8 21 32 34 51 64

--------------------

最终结果：8 21 32 34 51 64

--------------------

冒泡排序算法C语言实现如下，

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

##### 改进版的冒泡排序 #####

冒泡排序可以做一点改进让它的速度稍微快一点，设想，当某一次循环中，两两比较之后，没有一次交换发生，意味着此时数组已经排好序了，这个时候在进行之后的循环是没有意义的，纯粹是浪费时间，所以在这个时候应该结束循环，排序结束。C语言实现如下

void BubbleSort(int a[], int n)
    {
        bool swapFlag = false;
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = 0; j < n - 1 - i; j++)
            {
                if (a[j] > a[j + 1])
                {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    swapFlag = true;
                }
            }
            if (!swapFlag)
                break;
        }
    }

基本版的冒泡排序的时间复杂度最好和最差情况下都是O(n²)，改进版的冒泡排序最好情况下时间复杂度可以达到O(n)，最差情况下时间复杂度仍为O(n²)。两个版本的冒泡排序平均时间复杂度都为O(n²)，空间复杂度为O(1)，因为冒泡排序不占用多余的空间。  
冒泡排序是一种原地排序（In-place sort）并且稳定（stable sort）的排序算法，优点是实现简单，占用空间小，缺点是效率低，时间复杂度高，对于大规模的数据耗时长。

[Link 1]: https://blog.csdn.net/u010183728/article/details/81625010
[Link 2]: https://blog.csdn.net/u010183728/article/details/81711194
[70]: /images/20220518/f280f9f58c3949879a31261fb098454c.png
[70 1]: /images/20220518/7073e4ce962449c1a34d2ff484bfdd29.png