【Algo】排序算法

你的名字 2022-06-06 06:20 75阅读 0赞

## 1、冒泡 ##

简介——  
冒泡排序，可以想象成从水中冒出的气泡，从水中到水面气泡逐渐变大，近似有序排列。冒泡排序就是这个思想，对于给定的一组N个数据，从前往后或者从后往前，依次比较两个相邻数据的大小，不满足排序要求（从小到大或者从大到小）的就交换它们的位置，每轮比较可以冒出一个最大数或者最小数。因为是两个数据作比较，所以每轮最多只需比较N-1次，而且对于已经冒出的数据即排序好的数据没有必要再进行比较，所以每轮比较的次数递减。N个数据也最多需要比较N-1轮，如果在第一轮比较时没有任何数据进行交换，则说明原始数据已经有序，或者在某轮比较时没有任何数据进行交换，说明数据已经有序，不用再进行剩下的比较。可以看出，冒泡排序的时间复杂度最好的为N-1，最坏的为(N-1)\*(N-1)。

例子——  
下面是从小到大、从前往后冒泡的排序算法实现，关键点为两个for循环的结束判断语句以及判断一轮比较下来有无数据交换的变量swapped，变量step可以理解为时间复杂度，并且打印出了每次比较后的结果。

#include <iostream>
    
    #include "sort.h"
    
    using namespace std;
    
    int BubbleSort(int *data, int size)
    {
        int step = 0;
        bool swapped = false;
    
        cout << "step:" << step << " data:";
        for (int i = 0; i < size; ++i) {
            cout << data[i] << " ";
        }
        cout << endl;
    
        for (int i = 0; i < size - 1; ++i) {
            swapped = false;
            int temp = 0;
            for (int j = 0; j < size - 1 - i; ++j) {
                ++step;
                if (data[j] > data[j + 1]) {
                    swapped = true;
                    temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                }
    
                cout << "step:" << step << " data:";
                for (int i = 0; i < size; ++i) {
                    cout << data[i] << " ";
                }
                cout << endl;
            }
            if (!swapped) {
                return step;
            }
        }
    
        return step;
    }

## 2、选择 ##

简介——  
选择排序，顾名思义，就是从一组数据中选择目标数据，可以从前往后或者从后往前进行选择，每轮循环选择一个最小数或者最大数，然后把这个数放到目标位置，再进行剩下的选择。比如说从小到大排序N个数，从前往后进行选择，首先是第一个数，依次与其后的所有数进行比较，每次比较时把较小的数放到第一个数的位置，这样一轮下来，第一个数就是最小的数，然后选择第二个数，依次类推，N个数需要循环N-1次，且每次循环的数据比较次数递减，可以看出，即使是一个完全排序好的数列，也需要相当多的时间复杂度。

例子——  
如下例子中，每轮循环选择最小数时只是记下了最小数的索引，最后才进行数据交换，从而避免了频繁数据交换的不良影响。

#include <iostream>
    
    #include "sort.h"
    
    using namespace std;
    
    int SelectionSort(int *data, int size)
    {
        int step = 0;
        int min = 0;
    
        cout << "step:" << step << " data:";
        for (int i = 0; i < size; ++i) {
            cout << data[i] << " ";
        }
        cout << endl;
    
        for (int i = 0; i < size - 1; ++i) {
            min = i;
            for (int j = i + 1; j < size; ++j) {
                ++step;
                if (data[min] > data[j]) {
                    min = j;
                }
            }
            if (min != i) {
                int temp = data[i];
                data[i] = data[min];
                data[min] = temp;
            }
    
            cout << "step:" << step << " data:";
            for (int i = 0; i < size; ++i) {
                cout << data[i] << " ";
            }
            cout << endl;
        }
    
        return step;
    }

上面的选择排序有个优化空间，那就是在每轮循环选择最小数的同时选择一个最大数，并将最大数放到对应位置，这样循环轮数减半，每轮循环深度递减，转化为一个最大数的比较过程，例子如下，关键点为两个for循环语句以及最小数、最大数的交换过程。

int SelectionSort2(int *data, int size)
    {
        int step = 0;
        int min = 0;
        int max = 0;
    
        cout << "step:" << step << " data:";
        for (int i = 0; i < size; ++i) {
            cout << data[i] << " ";
        }
        cout << endl;
    
        for (int i = 0; i < size / 2; ++i) {
            min = i;
            max = i;
            for (int j = i + 1; j < size - i; ++j) {
                ++step;
                if (data[min] > data[j]) {
                    min = j;
                }
                if (data[max] < data[j]) {
                    max = j;
                }
            }
            if (min != i) {
                int temp = data[i];
                data[i] = data[min];
                data[min] = temp;
            }
            if (max != size - i - 1) {
                if (max == i) {
                    max = min;
                }
                int temp = data[size - i - 1];
                data[size - i - 1] = data[max];
                data[max] = temp;
            }
    
            cout << "step:" << step << " data:";
            for (int i = 0; i < size; ++i) {
                cout << data[i] << " ";
            }
            cout << endl;
        }
    
        return step;
    }

## 3、插入 ##

简介——  
插入排序，就是一个把未排序数据逐步构建为有序序列的过程，可以把一组数据分为前后两部分，前面的部分表示有序序列，后面的部分表示未排序数据，首先第一个数据是有序的，从第二个数据开始，与它前面的有序序列中的数据逐个比较，找到自己的位置，依次类推，直到最后一个数据，这样需要循环插入N-1次，即使对于一个有序序列来说，在每轮的循环插入中也需要与前面的数据比较一次。

例子——

#include <iostream>
    
    #include "sort.h"
    
    using namespace std;
    
    int InsertSort(int *data, int size)
    {
        int step = 0;
    
        cout << "step:" << step << " data:";
        for (int i = 0; i < size; ++i) {
            cout << data[i] << " ";
        }
        cout << endl;
    
        for (int i = 1; i < size; ++i) {
            int temp = data[i];
            int index = i - 1;
            while (index >= 0) {
                ++step;
                if (temp >= data[index]) {
                    break;
                }
                data[index + 1] = data[index];
                --index;
    
                cout << "step:" << step << " data:";
                for (int i = 0; i < size; ++i) {
                    cout << data[i] << " ";
                }
                cout << endl;
            }
            data[index + 1] = temp;
    
            cout << "step:" << step << " data:";
            for (int i = 0; i < size; ++i) {
                cout << data[i] << " ";
            }
            cout << endl;
        }
    
        return step;
    }

上面的例子中有个优化空间，在每轮的循环插入中，因为是在前面的已经排序好的有序序列中查找当前数据的位置，这样就没有必要按顺序查找插入点，可以使用二分法。

## 4、快排 ##

简介——  
快速排序，就是从一组数据中选择一个基准值，将比基准值小的数据放到基准值的一边，比基准值大的数据放到基准值的另一边，等于基准值的数据可放到任意一边，然后再以同样的方法分别递归排序基准值两边的数据，直到完全有序。

例子——  
下面的例子中有两种快速排序算法实现，相同的是都选取第一个数据为基准值，从小到大排序，不同的是查找比基准值大、小的数据然后放到合适位置的方法。

#include <iostream>
    
    #include "sort.h"
    
    using namespace std;
    
    int QuickSort(int *data, int left, int right)
    {
        int index = left;
        int pivot = data[index];
    
        for (int i = left + 1; i <= right; ++i) {
            if (data[i] < pivot) {
                ++index;
                if (index != i) {
                    int temp = data[index];
                    data[index] = data[i];
                    data[i] = temp;
                }
            }
        }
        if (index != left) {
            data[left] = data[index];
            data[index] = pivot;
        }
    
        if (index -1 > left) {
            QuickSort(data, left, index -1);
        }
        if (index + 1 < right) {
            QuickSort(data, index + 1, right);
        }
    
        static int step = 0;
        ++step;
        cout << "step:" << step << " data:";
        for (int i = left; i <= right; ++i) {
            cout << data[i] << " ";
        }
        cout << endl;
    
        return 0;
    }
    
    int QuickSort2(int *data, int left, int right)
    {
        int begin = left;
        int end = right;
        int pivot = data[begin];
    
        while (begin < end) {
            while (begin < end && data[end] >= pivot) {
                --end;
            }
            data[begin] = data[end];
            while (begin < end && data[begin] <= pivot) {
                ++begin;
            }
            data[end] = data[begin];
        }
        data[begin] = pivot;
    
        if (begin - 1 > left) {
            QuickSort2(data, left, begin - 1);
        }
        if (begin + 1 < right) {
            QuickSort2(data, begin + 1, right);
        }
    
        static int step = 0;
        ++step;
        cout << "step:" << step << " data:";
        for (int i = left; i <= right; ++i) {
            cout << data[i] << " ";
        }
        cout << endl;
    
        return 0;
    }

## 5、堆 ##

简介——  
堆排序，利用了堆的性质，堆是一个完全二叉树，分为大根堆和小根堆，即堆顶数据为最大值或最小值，且父节点比子节点大或小。以从小到大升序排列为例，可以把数据分为两部分，前面的部分表示堆，是个无序大顶堆，只需要保证第一个数据为堆中的最大值即可，后面的部分为从小到大排序好的数据，首先是建堆，从最后一个非叶子节点到根节点逐步调整堆，使得第一个数据即堆顶数据或根节点为最大值，然后是排序和调整堆，排序即交换堆顶数据与堆中的最后一个数据，这样堆后面部分的数据为从小到大排序好的数据，而此时的堆已经不是大顶堆，所以需要再次进行调整，把堆中的最大值调整到堆顶，然后再进行同样的排序和调整堆的过程，直到最后一个数据。

例子——

#include <iostream>
    
    #include "sort.h"
    
    using namespace std;
    
    void HeapAdjust(int *data, int size, int root)
    {
        int child = root * 2 + 1;
        while (child < size) {
            if (child + 1 < size && data[child + 1] > data[child]) {
                ++child;
            }
            if (data[child] > data[root]) {
                data[root] = data[root] ^ data[child];
                data[child] = data[root] ^ data[child];
                data[root] = data[root] ^ data[child];
                root = child;
                child = root * 2 + 1;
            }
            else {
                break;
            }
        }
    }
    
    int HeapSort(int *data, int size)
    {
        for (int i = 0; i < size; ++i) {
            cout << data[i] << " ";
        }
        cout << endl;
    
        for (int i = size / 2 - 1; i >= 0; --i) {
            HeapAdjust(data, size, i);
        }
    
        for (int i = 0; i < size - 1; ++i) {
            {
                data[size -1 -i] = data[size -1 -i] ^ data[0];
                data[0] = data[size -1 -i] ^ data[0];
                data[size -1 -i] = data[size -1 -i] ^ data[0];
            }
            HeapAdjust(data, size - 1 - i, 0);
        }
    
        for (int i = 0; i < size; ++i) {
            cout << data[i] << " ";
        }
        cout << endl;
    
        return 0;
    }

## 6、希尔 ##

简介——  
希尔排序，是一种缩小增量排序算法，也是一种特殊的插入排序算法，简单来说就是简单插入排序数据索引的差为指定增量的数据，而这个增量从某个数开始，最后递减为1。也就是说，首先选取一个增量数列，如下面例子的增量从5开始，然后是2，最后是1，当增量为5时，依次简单插入排序索引5和索引0的数据、索引6和索引1、7和2、8和3、9和4，这样一轮下来，索引间隔为5的数据是有序的，然后同理排序索引间隔为2、1的情况，最后必然是间隔为1的情况。

例子——

#include <iostream>
    
    #include "sort.h"
    
    using namespace std;
    
    void ShellSortInsert(int *data, int size, int inc)
    {
        cout << inc << endl;
    
        for (int i = inc; i < size; ++i) {
            if (data[i] < data[i - inc]) {
                int j = i - inc;
                int t = data[i];
                while (j >=0 && t < data[j]) {
                    data[j + inc] = data[j];
                    j -= inc;
                }
                data[j + inc] = t;
    
                for (int i = 0; i < size; ++i) {
                    cout << data[i] << " ";
                }
                cout << endl;
            }
        }
    }
    
    int ShellSort(int *data, int size)
    {
        for (int i = 0; i < size; ++i) {
            cout << data[i] << " ";
        }
        cout << endl;
    
        int inc = size / 2;
        while (inc >= 1) {
            ShellSortInsert(data, size, inc);
            inc = inc / 2;
        }
    
        for (int i = 0; i < size; ++i) {
            cout << data[i] << " ";
        }
        cout << endl;
    
        return 0;
    }

## 7、归并 ##

简介——  
归并排序，采用了分治法Divide and Conquer的思想，首先把数据分为两部分，然后分别对这两部分数据进行排序，最后把排序好的这两部分数据合并到一起。其中，排序使用了递归策略，把当前数据再分为两部分，再进行同样的操作，直到最后一个数据；而合并的话逐个取出两个有序数列中的较小的数据，与其它排序算法不同的是，归并排序需要申请一个与待排序数据同样大小的内存空间。

例子——

#include <iostream>
    
    #include "sort.h"
    
    using namespace std;
    
    void MergeSortConquer(int *data, int first, int mid, int last, int *temp)
    {
        int lfirst = first;
        int rfirst = mid + 1;
        int llast = mid;
        int rlast = last;
        int index = 0;
    
        while (lfirst <= llast && rfirst <= rlast) {
            if (data[lfirst] < data[rfirst]) {
                temp[index++] = data[lfirst++];
            }
            else {
                temp[index++] = data[rfirst++];
            }
        }
    
        while (lfirst <= llast) {
            temp[index++] = data[lfirst++];
        }
        while (rfirst <= rlast) {
            temp[index++] = data[rfirst++];
        }
    
        for (int i = 0; i < index; ++i) {
            data[first + i] = temp[i];
        }
    }
    
    void MergeSortDivide(int *data, int first, int last, int *temp)
    {
        if (first < last) {
            int mid = (first + last) / 2;
            MergeSortDivide(data, first, mid, temp);
            MergeSortDivide(data, mid + 1, last, temp);
            MergeSortConquer(data, first, mid, last, temp);
        }
    }
    
    int MergeSort(int *data, int size)
    {
        for (int i = 0; i < size; ++i) {
            cout << data[i] << " ";
        }
        cout << endl;
    
        int *temp = new int[size];
        MergeSortDivide(data, 0, size - 1, temp);
        delete[] temp;
    
        for (int i = 0; i < size; ++i) {
            cout << data[i] << " ";
        }
        cout << endl;
    
        return 0;
    }