排序算法系列1——选择/插入/冒泡/希尔

这一系列总结写于看liuyubobobo老师视频的时候，算是重新复习了一遍数据结构与算法，感觉还是很清晰的。如今面临春招秋招，重新拿出来复习一下。

部分图片来源于网上其他人的博客，详见水印。

本文主要包括选择/插入/冒泡/希尔四种排序方法的总结。

排序基础

2-1 选择排序 Selection Sort

工作原理：

将序列分为已排序部分和待排序部分，初始时在序列中找到最小（大）元素，放到序列的起始位置作为已排序序列；然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

每一次内层循环，都寻找待排序部分的最小值，插入已排序部分的末尾

选择排序的两层循环在任何情况下都需要全部执行完，时间复杂度为O(n^2)

选择排序是不稳定排序。

选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个 元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么 交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。

main.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
选择排序
#include <iostream>
#include <algorithm>

using namespace std;

void selectionSort(int arr[], int n){

    for(int i = 0 ; i < n ; i ++){
        // 寻找[i, n)区间里的最小值
        int minIndex = i;
        for( int j = i + 1 ; j < n ; j ++ )
            if( arr[j] < arr[minIndex] )
                minIndex = j;

        swap( arr[i] , arr[minIndex] );
    }
}

int main() {

    int a[10] = {10,9,8,7,6,5,4,3,2,1};
    selectionSort(a,10);
    for( int i = 0 ; i < 10 ; i ++ )
        cout<<a[i]<<" ";
    cout<<endl;

    return 0;
}

2-2使用模板（泛型）编写算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
template<typename T>
void selectionSort(T arr[], int n){

    for(int i = 0 ; i < n ; i ++){
        // 寻找[i, n)区间里的最小值
        int minIndex = i;
        for( int j = i + 1 ; j < n ; j ++ )
            if( arr[j] < arr[minIndex] )
                minIndex = j;

        swap( arr[i] , arr[minIndex] );
    }
}

int main() {
    // 测试模板函数，传入字符串数组
    string c[4] = {"D","C","B","A"};
    selectionSort(c,4);
    for( int i = 0 ; i < 4 ; i ++ )
        cout<<c[i]<<" ";
    cout<<endl;

    // 测试模板函数，传入自定义结构体Student数组
    Student d[4] = { {"D",90} , {"C",100} , {"B",95} , {"A",95} };
    selectionSort(d,4);
    for( int i = 0 ; i < 4 ; i ++ )
        cout<<d[i];
    cout<<endl;

    return 0;
}

自定义结构体Student

Student.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<string>

using namespace std;

struct Student{
    
    string name;
    int score;
    
    // 重载小于运算法,定义Student之间的比较方式
    // 如果分数相等，则按照名字的字母序排序
    // 如果分数不等，则分数高的靠前
    bool operator<(const Student& otherStudent){
        return score != otherStudent.score ?
               score > otherStudent.score : name < otherStudent.name;
    }
    
    //重载输出运算符
    friend ostream& operator<<(ostream& os, const Student& student){
        
        os<"Student:"<<student.name<<" "<<student.score<<endl;
        return os;
    }
}

2-3 随机生成算法测试用例

SortTestHelper.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<ctime>
#include<cassert>

using namespace std;

namespace SortTestHelper{

    //生成有n个元素的随机数组，每个元素的随机范围为[rangeL,rangeR]
    int* generateRandomArray(int n, int rangeL, int rangeR){
    
        assert(rangeL<=rangeR);
        
        int *arr = new int[n];
        srand(time(NULL));
        for(int i = 0; i < n; i++)
            arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;
        return arr;
    }
    
    //打印函数
    template<typename T>
    void printArray(T arr[], int n){
        
        for(int i = 0; i < n; i++)
            cout<<arr[i]<<" ";
        cout<< endl;
        
        return;
    }
}

main.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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] );
    }
}

int main() {

    // 测试排序算法辅助函数
    int N = 20000;
    int *arr = SortTestHelper::generateRandomArray(N,0,100000);
    selectionSort(arr,N);
    SortTestHelper::printArray(arr,N);
    delete[] arr;

    return 0;
}

2-4测试算法的性能

SortTestHelper.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
namespace SortTestHelper{
    ..........
    //判断是否已经排序
    template<typename T>
    bool isSorted(T arr[], int n){
        
        for(int i = 0; i < n-1; i++)
            if(arr[i] > arr[i + 1])
                return false;
                
        return true;
    }
    
    //计算所需时间
    //参数为排序算法的名称，排序算法函数指针，测试用例
    template<typename T>
    void testSort( string sortName, void(*sort)(T[],int), T arr[], int n){
        
        clock_t startTime = clock();
        sort(arr,n);
        clock_t endTime = clock();
        
        assert(isSorted(arr,n));
        cout << sortName << " : " << double(endTime - startTime) / CLOCKS_PER_SEC << " s" << endl;
        
        return;
    }
}

main.cpp

1
2
3
4
5
6
7
8
9
int main() {

    int n = 20000;
    int *arr = SortTestHelper::generateRandomArray(n,0,n);
    SortTestHelper::testSort("Selection Sort", selectionSort, arr, n);
    delete[] arr;

    return 0;
}

2-5插入排序法 Insertion Sort

插入排序原理：
插入排序同样将序列分为已排序部分和待排序部分，每次去除待排序部分的第一个元素，将其插入以排序部分的合适的位置，直到所有元素排序完成。

内层循环每次在已排序的部分中寻找合适的位置插入元素

插入排序是稳定排序算法

插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开 始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相 等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳 定的。

image

main.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
template<typename T>
void insertionSort(T arr[], int n){
    
    for(int i = 1; i < n; i++){
        
        //寻找元素arr[i]合适的插入位置
        for( int j = i ; j > 0 && arr[j] < arr[j-1] ; j -- )
            swap( arr[j] , arr[j-1] );
        }
    }
}

// 比较SelectionSort和InsertionSort两种排序算法的性能效率
// 此时， 插入排序比选择排序性能略低
int main() {

    int n = 20000;

    cout<<"Test for random array, size = "<<n<<", random range [0, "<<n<<"]"<<endl;
    int *arr1 = SortTestHelper::generateRandomArray(n,0,n);
    int *arr2 = SortTestHelper::copyIntArray(arr1, n);

    SortTestHelper::testSort("Insertion Sort", insertionSort,arr1,n);
    SortTestHelper::testSort("Selection Sort", selectionSort,arr2,n);

    delete[] arr1;
    delete[] arr2;

    cout<<endl;

    return 0;
}

SortTestHelper.h

1
2
3
4
5
6
7
//复制数组
int *copyIntArray(int a[], int n)
{
    int* arr = new int[n];
    copy(a,a+n,arr);
    return arr;
}

插入排序的第二重循环可以提前结束，相比选择排序更有效, 但上面的实验结果却相反。

因为插入排序在不断的进行交换操作，比比较操作更为耗时。

2-6插入排序法的改进

将数据的交换改成数据的赋值，直至找到正确的位置

对于一个近乎排序的数组，插入排序的效率要远远高于选择排序

对已排序的数组，插入排序的复杂度为O(n)

main.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<typename T>
void insertionSort(T arr[], int n){
    
    for(int i = 1; i < n; i++){
        
        //寻找元素arr[i]合适的插入位置
        T e = arr[i];
        int j; //j保存元素e应该插入的位置
        for( j = i ; j > 0 && arr[j-1] > e ; j -- )
            arr[j] = arr[j-1];
        }
        arr[j] = e;
    }
}

SortTestHelper.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//生成一个接近有序的数组
// 生成一个近乎有序的数组
// 首先生成一个含有[0...n-1]的完全有序数组, 之后随机交换swapTimes对数据
// swapTimes定义了数组的无序程度:
// swapTimes == 0 时, 数组完全有序
// swapTimes 越大, 数组越趋向于无序
int *generateNearlyOrderedArray(int n, int swapTimes){

    int *arr = new int[n];
    for(int i = 0 ; i < n ; i ++ )
        arr[i] = i;

    srand(time(NULL));
    for( int i = 0 ; i < swapTimes ; i ++ ){
        int posx = rand()%n;
        int posy = rand()%n;
        swap( arr[posx] , arr[posy] );
    }

    return arr;
}

Optional - 01 - 选择排序的改进

在每一轮中, 可以同时找到当前未处理元素的最大值和最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
template<typename T>
void selectionSort( T arr[], int n){
    int left = 0, right = n - 1;
    while(left<right){
        int minIndex = left;
        int maxIndex = right;
        
        //在每一轮查找时，保证arr[minIndex] <= arr[maxIndex]
        if(arr[minIndex) > arr[maxIndex])
            swap(arr[minIndex], arr[maxIndex])；
        
        for(int i = left + 1; i < right; i++)
            if(arr[i] < arr[minIndex])
                minIndex = i;
            else if(arr[i] > arr[maxIndex)
                maxIndex = i;
        
        swap(arr[left], arr[minIndex]);
        swap(arr[right], arr[maxIndex]);
        
        left++;
        right--;
    }
    return;
}

Optional - 02 - 冒泡排序探究

冒泡排序

基本思路

冒泡排序的基本思想是，对相邻的元素进行两两比较，顺序相反则进行交换，这样，每一趟会将最小或最大的元素“浮”到顶端，最终达到完全有序

稳定算法

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改 变，所以冒泡排序是一种稳定排序算法。

image

代码实现

1
2
3
4
5
6
7
8
9
10
template<typename T>
void bubbleSort(T arr[], int n){
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n - i - 1; j++){
            if(arr[j] > arr[j + 1])
                swap(arr[j], arr[j+1]);
        }
    }
}

改进：当发现某一次循环没有交换数据时，说明已经有序，直接break

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<typename T>
void bubbleSort(T arr[], int n){
    
    for(int i = 0; i < n; i++){
        bool flag  = true;
        for(int j = 0; j < n - i - 1; j++){
            if(arr[j] > arr[j + 1]){
                swap(arr[j], arr[j+1]);
                flag = false;
            }
        }
        if(flag)
            break;
    }
}

改进：记录最后一次的交换位置,在此之后的元素在下一轮扫描中均不考虑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<typename T>
void bubbleSort_Improve2(T arr[], int n){
	int lastIndex = n - 1;
	for (int i = 0; i < n; i++){
		int recordIndex = 0;
		for (int j = 0; j < lastIndex; j++){
			if (arr[j] > arr[j + 1]){
				swap(arr[j], arr[j + 1]);
				recordIndex = j+1;
			}
		}
		lastIndex = recordIndex;
	}
}

根据上面这种冒泡实现，若原数组本身就是有序的（这是最好情况），仅需n-1次比较就可完成；若是倒序，比较次数为 n-1+n-2+…+1=n(n-1)/2，交换次数和比较次数等值。所以，其时间复杂度依然为O(n2）。综合来看，冒泡排序性能还还是稍差于上面那种选择排序的。

Optional - 03 - 希尔排序探究

基本思想

希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。换句话说，一个h有序数组就是h个互相独立的有序数组编织在一起组成的一个数组（见下图）。在进行排序时，如果h很大，我们就能将元素移动到很远的地方，为实现更小的h有序创造方便。用这种方式，对于任意以1结尾的h序列，我们都能够将数组排序。这就是希尔排序。

image

希尔排序更高效的原因是它权衡了子数组的规模和有序性。排序之初，各个子数组都很短，排序之后子数组都是部分有序的，这两种情况都很适合插入排序。子数组部分有序的程度取决于递增序列的选择。透彻理解希尔排序的性能至今仍然是一项挑战。实际上，它是我们唯一无法准确描述其对于乱序的数组的性能特征的排序方法。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template<typename T>
void shellSort(T arr[], int n){
    
    //计算increment squence: 1,4 13,121,364
    int h = 1;
    while(h < n/3)
        h = 3*h + 1;
        
    while(h >= 1){
    
        //h-sort the array
        for(int i = h; i < n; i++){
            //对//arr[i],arr[i-h],arr[i-2*h],arr[i-3*h]...
            T e = arr[i];
            int j;
            for(j = i; j >= h && e < arr[j-h]; j -= h)
                arr[j] = arr[j-h];
            arr[j] = e;
        }
        h/=3;
    }
}

总结

有经验的程序员有时会选择希尔排序，因为对于中等大小的数组它的运行时间是可以接受的。它的代码量很小，且不需要使用额外的内存空间。在后面的学习中我们会看到更加高效的算法，但除了对于很大的N，它们可能只会比希尔排序快两倍（可能还达不到），而且更复杂。如果你需要解决一个排序问题而又没有系统排序函数可用（例如直接接触硬件或是运行于嵌入式系统中的代码），可以先用希尔排序，然后再考虑是否值得将它替换为更加复杂的排序算法。

希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小， 插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元 素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

希尔排序

算法排序的稳定性

赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

SJTU在读<br><br>机器学习/深度学习<br><br>走在路上的猪肝君