数据结构与算法之基础排序算法

c/c++

浏览数:225

2019-3-28

简介

一般所谓的基础排序算法指的是时间复杂度为O(n^2)的算法。常用的有选择排序、插入排序、冒泡排序等。在这里,我们主要来分析前面两个算法。

选择排序(Selection Sort)

1. 原理
如下图所示有8个数据:

首先遍历第二个数字开始的所有数字,找到最小的那个,然后和第一个数字进行比较,如果比他小,就和他进行交换,否则不交换。如下图所示:

以此类推,从第N个数字开始继续寻找最小的数字,和第N个数字进行交换(N是指循环的次数,第一次和第一个数,第二次和第二个数…),如下图所示:

这样下去就可以把整个数组进行排序了。

2. 代码实现
使用c++对其实现

template<typename T>
void selectionSort(T arr[], int n){

    for(int i = 0 ; i < n ; i ++){

        int minIndex = i;
        for( int j = i + 1 ; j < n ; j ++ )
            if( arr[j] < arr[minIndex] )
                minIndex = j;

        swap( arr[i] , arr[minIndex] ); //需要使用头文件#include <algorithm>
    }
}

从上面的代码可以看出,对于任何一个数组,选择排序排序的两层循环都要完全执行完的,因此其效率是非常低下的。

插入排序(Insortion Sort)

1. 原理
插入排序的原理类似于在玩扑克牌时,对牌进行排序的操作。例如有下面8个数据:

首先选取第二个元素,让它和第一个元素进行比较,如果比第一个元素小,就将两者进行调换,如下图所示:

这样前面两个数字就排好序了,接着讲第三个元素与第二个进行比较,比第二个小就进行交换,交换完了再和第一个进行比较,比第一个小就继续进行交换,以此类推,如下图所示:

以此类推,后面的数字也是这样以此和前面的数据进行比较、交换,这样就可以把整个数组给拍好了。

2. 代码实现

template<typename T>
void insertionSort(T arr[], int n){
    
    for (int i = 1; i < n; i ++){ //注意这里i的小标是从1开始的,因为第0个数是固定不动的
        //寻找元素arr[i]合适的插入位置
        for (int j = i; j > 0; j --) //交换到最后是第二个数与第二个数进行交换,所以这里是j>0不是j>=0
            if (arr[j] < arr[j-1])
                swap(arr[j],arr[j-1]);
            else //如果已经比前面的数字小了,就不进行交换
                break;
    }
}

从上面的插入排序的原理和代码可以看出,插入排序和选择排序的最大区别在于:插入排序的第二重循环是可以提前结束的。因此理论上插入排序比选择排序应该更快一些。但是经过实际的测试之后,发现上面的插入排序比选择排序运行的更慢,这是什么原因呢?我们查看插入排序的第二重循环里面,每进行一次比较之后都要进行一次交换操作,而交换操作的运行速度比选择排序的赋值操作慢得多,也就是说插入排序速度慢的问题就出在了这里,接下来我们就对插入排序进行改进。

插入排序的改进

1. 原理
要将时间效率提高,就要牺牲空间!如下图所示,还是8个数字,固定第一个数字不变,,如下图所示:

接下里分三步进行操作,如下图所示:

这样就将前面两个数排序完成了。接下里的数再进行如下操作:

这样就将前面三个数排序完成了。以此类推可以将所有的数排序完成。这里我们都是使用赋值操作,所以速度会比之前的交换操作来的快。

2. 程序实现
只需要修改内循环中的代码即可。代码如下:

void insertionSort(T arr[], int n){
    
    for (int i = 1; i < n; i ++){
        //第一步,将第i个位置的元素赋值给临时变量e
        T e = arr[i]; 
        //第二步,将依次比较元素第i个位置之前的数是否比临时变量中的数要大,要大则往后移动
        int j; // j保存元素e应该插入的位置
        for (j = i; j > 0; j--)
            if (arr[j-1] > e) 
                arr[j] = arr[j-1];
            else 
                break;
        //第三步,将临时变量中的值放到最后一个比它大的位置处
        arr[j] = e;
    }
}

当一个数组本身就有近乎有序的时候,插入排序的速度将会非常的快!甚至会超过有些O(n*log n)的算法!!
当一个数组本身即是有序时,插入排序会变成一个O(n)级别的算法。所以,插入排序经常作为一个子过程对复杂的排序算法进行优化。