算法与数据结构(二)：排序篇-O(n^2)算法：选择 &

作者: 天涯明月笙 | 来源:发表于2017-09-13 11:53 被阅读114次

排序基础

O(n^2)的算法虽然简单，但也实用！让我们从最简单的基础排序算法开始，打开我们的算法大门！

排序算法

O(n^2)的排序算法

最优的时间复杂度为O(nlogn)的算法。

为什么要学习O(n^2)的排序算法。

基础解法。先通过简单解法找思路

编码简单，易于实现，是一些简单场景的首选
在特殊情况下，简单排序算法更有效
简单的排序算法思想能衍生出复杂的排序算法（希尔排序：插入排序的优化）
作为子过程，改进更复杂的排序算法

选择排序（selection sort)

在整个数组中找到应该第一名的数和目前位于第一名的数互换。

互换前

互换后

再找到应该第二名的数和目前位于第二名的互换。

2互换后

再找到应该第几名的数和目前位于第几名的互换
七和七，八和八。自身换。

互换

具体代码

#include <iostream>
#include <algorithm>
//老的标准里swap.新的c++11就在std中。

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;
}

运行结果：

运行结果

使用模板函数增加更多类型支持

main.cpp:

#include <iostream>
#include <algorithm>
#include <string>
#include "Student.h"

using namespace std;

template<typename T>//声明函数为模板函数。类型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 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;

    // 测试模板函数，传入浮点数数组
    // float b[4] = {4.4,3.3,2.2,1.1};
    //double到float会被截断。
//    double b[4] = {4.4,3.3,2.2,1.1};
//    selectionSort(b,4);
//    for (int j = 0; j < 4 ; ++j) {
//        cout << b[j] <<" ";
//    }
//    cout<<endl;

    // 测试模板函数，传入字符串数组
    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.h:

#ifndef INC_02_SELECTION_SORT_USING_TEMPLATE_STUDENT_H
#define INC_02_SELECTION_SORT_USING_TEMPLATE_STUDENT_H

#include <iostream>
#include <string>

using namespace std;

struct Student{

    string name;
    int score;

    bool operator<(const Student& otherStudent){
        return score != otherStudent.score ?
               score > otherStudent.score : name < otherStudent.name;
        //小和大自己来定义。
        // 成绩是否等于传入的成绩。如果不等于那么将返回是否大于传入成绩的bool值
        //如果等于，那么将返回名字是否小于的bool值
    }

    friend ostream& operator<<(ostream &os, const Student &student){

        os<<"Student: "<<student.name<<" "<<student.score<<endl;
        return os;
    }
};

#endif //INC_02_SELECTION_SORT_USING_TEMPLATE_STUDENT_H

运行结果：

运行结果

使用辅助函数生成测试用例

#include <iostream>
#include "SortTestHelper.h"

using namespace std;

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 = 10000;
    int *arr = SortTestHelper::generateRandomArray(N,0,N);
    selectionSort(arr,N);
    SortTestHelper::printArray(arr,N);
    delete[] arr;

    return 0;
}

SortTestHelper.h

#ifndef INC_03_SELECTION_SORT_GENERATE_TEST_CASES_SORTTESTHELPER_H
#define INC_03_SELECTION_SORT_GENERATE_TEST_CASES_SORTTESTHELPER_H

#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);//assert函数限制L要小于等于R.include<cassert>

        int *arr = new int[n];

        srand(time(NULL));//随机种子的设置。include <ctime>
        for (int i = 0; i < n; i++)
            arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;
            //rand()返回随机整数。随机整数求余范围长度（没有加之前是0-长度范围内值） + rangL的偏移
        return arr;
    }

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

        for (int i = 0; i < n; i++)
            cout << arr[i] << " ";
        cout << endl;

        return;
    }

};
#endif //INC_03_SELECTION_SORT_GENERATE_TEST_CASES_SORTTESTHELPER_H

排序结果

算法运行时间测试函数

main.cpp:

#include <iostream>
#include "SortTestHelper.h"

using namespace std;

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 = 10000;
    int *arr = SortTestHelper::generateRandomArray(n,0,n);
    SortTestHelper::testSort("Selection Sort", selectionSort, arr, n);
    delete[] arr;

    return 0;
}

sorthelper.h

#ifndef INC_03_SELECTION_SORT_DETECT_PERFORMANCE_SORTTESTHELPER_H
#define INC_03_SELECTION_SORT_DETECT_PERFORMANCE_SORTTESTHELPER_H

#include <iostream>
#include <ctime>
#include <cassert>
#include <string>

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;
    }


// 测试数组是否有序
    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>
    //传入参数：1.排序算法名称。2.函数指针。要写明函数的返回类型，需要传入的参数。
    //3.传入测试用例4.数组元素个数
    void testSort(const string &sortName, void (*sort)(T[], int), T arr[], int n) {

        clock_t startTime = clock();//开始时间.include<ctime>
        sort(arr, n);
        clock_t endTime = clock();

//        assert(isSorted(arr, n));//限定arr是否真的有序了。如果排序不正确会自动中断
        cout << sortName << " : " << double(endTime - startTime) / CLOCKS_PER_SEC << " s" << endl;
        //CLOCKS_PER_SEC标准库中宏定义。每秒钟所运行的时钟周期。

        return;
    }

};
#endif //INC_03_SELECTION_SORT_DETECT_PERFORMANCE_SORTTESTHELPER_H

插入排序

类似于生活中整理扑克牌。

插入排序

看后面的牌，把它插入合适的位置。直到最后一张牌放在合适位置。手里的牌就完成了。

原数组

对于8来说不用动。对于6来说应该放到8前面去。
2和8比应该放到8前面。

2的第一次互换

2和6相比应该放到6前面：

2的第二次互换

3要和8,6依次换位置，直到前面遇到2停止。

SortTestHelper.h:

#ifndef INC_04_INSERTION_SORT_SORTTESTHELPER_H
#define INC_04_INSERTION_SORT_SORTTESTHELPER_H

#include <iostream>
#include <algorithm>
#include <string>
#include <ctime>
#include <cassert>

using namespace std;


namespace SortTestHelper {

    int *generateRandomArray(int n, int range_l, int range_r) {

        int *arr = new int[n];

        srand(time(NULL));
        for (int i = 0; i < n; i++)
            arr[i] = rand() % (range_r - range_l + 1) + range_l;
        return arr;
    }

    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;
    }

    int *copyIntArray(int a[], int n){

        int *arr = new int[n];
        copy(a, a+n, arr);//std中的copy函数（1.原数组头指针2.原数组尾指针3.要拷贝到目的地址的头指针）
        return arr;
    }

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

        for (int i = 0; i < n; i++)
            cout << arr[i] << " ";
        cout << endl;

        return;
    }

    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(const string &sortName, void (*sort)(T[], int), T arr[], int n) {

        clock_t startTime = clock();
        sort(arr, n);
        clock_t endTime = clock();
        cout << sortName << " : " << double(endTime - startTime) / CLOCKS_PER_SEC << " s"<<endl;

        assert(isSorted(arr, n));

        return;
    }

};

#endif //INC_04_INSERTION_SORT_SORTTESTHELPER_H

main.cpp:

#include <iostream>
#include <algorithm>
#include "SortTestHelper.h"
#include "SelectionSort.h"

using namespace std;

template<typename T>
void insertionSort(T arr[], int n){
    //i从1开始是因为第0个元素可以不用考虑
    for( int i = 1 ; i < n ; i ++ ) {

        // 寻找元素arr[i]合适的插入位置
        // 写法1（向前找）
//        最多考查到j=1
//        for( int j = i ; j > 0 ; j-- )
//            if( arr[j] < arr[j-1] )
//                swap( arr[j] , arr[j-1] );
//            else
//                break;

        // 写法2
        for( int j = i ; j > 0 && arr[j] < arr[j-1] ; j -- )
            swap( arr[j] , arr[j-1] );

    }

    return;
}

int main() {

    int n = 10000;
    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;
}

selectionSort.h

#ifndef INC_04_INSERTION_SORT_SELECTIONSORT_H
#define INC_04_INSERTION_SORT_SELECTIONSORT_H

#include <iostream>
#include <algorithm>

using namespace std;


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] );
    }
}

#endif //INC_04_INSERTION_SORT_SELECTIONSORT_H

运行结果：

运行结果

根据理论推测我们认为插入排序因为会提前中止循环，不是像选择一样，每一遍都扫描全部，所以应该快一点。但是根据实际的结果发现并不是这样。选择排序更快。

优化插入排序 & 性质

   for( int j = i ; j > 0 && arr[j] < arr[j-1] ; j -- )
            swap( arr[j] , arr[j-1] );

在遍历的同时也在不停的交换。交换是要比简单的比较还要耗时的。
会有三次赋值。对于数组还有访问数组相应元素的时间。

改进让他在内层循环只交换一次。

复制副本不轻易交换

更加真实的扑克特效，复制一份6出来，不与前一个元素不停互换。而是直到找到该它存放的位置在插入。就好像扑克抽出来，直接插入该插的位置。

2的插入

把2拷贝一个副本：根前面的8比较，2比8小，则把原来2的位置赋值8.然后开始比较2与6的大小。2比6还小。原来8的位置赋值6.第0个位置了，直接赋值。

3-保存副本。然后3的位置赋值8,8的位置赋值6.6的位置发现3不再小于前面数。第一个6的位置赋值3.

第一个6位置赋值3

一次交换就是三次赋值。把交换用赋值取代

插入排序在几乎有序的情况下甚至比nlogn算法效果还好
系统日志的某几个无序日志。

如果是一个完全有序的数组。插入排序变成O(n)级别的算法。
发现就是合适位置，直接进入下一层循环。

选择排序 & 插入排序

选择排序

简单：缺点明显。两层循环。每一层循环都得完全执行完成。

插入排序

最差情况也是O(n^2).但是数组近乎有序，插入排序效率相当高。

冒泡排序（Bubble Sort）

理解过程。优化冒泡排序。适用情况。

希尔排序（shell sort）就是插入排序整体思路的延伸。

插入每次和之前一个元素进行比较。而shell排序和之前h个元素进行比较。
当h递减到1.

O(n^3/2).实现相对简单。最优O(nlogn)

优化分析理解算法。

算法与数据结构(二)：排序篇-O(n^2)算法：选择 &

排序基础

排序算法

O(n^2)的排序算法

选择排序（selection sort)

使用辅助函数生成测试用例

算法运行时间测试函数

插入排序

优化插入排序 & 性质

选择排序 & 插入排序

冒泡排序（Bubble Sort）

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

数据结构与算法

C语言

程序员

C++