排序算法总结

0.概述

0.1算法分类

十种常见的排序算法可以分为两大类：

非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度bune能够突破O(nlogn),因此称为非线性时间比较类排序

线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。


0.2相关概念

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。

不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。

时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。

空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

0.3简单比较

image

1.冒泡排序(Bubble Sort)

冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

1.1算法描述

  1. 比较相邻的元素，如果第一个比第二个大，就交换它们两个；
  2. 对每一对相邻元素做同同样的工作，从开始第一对到结尾的最后一对；每次走到最后，遍历过的最大的数就会排到最后
  3. 针对所有的元素重复以上的步骤，除了已经放到最后的
  4. 对之前的元素重复以上的步骤，直到没有任何一对数字需要比较

1.2动图演示

1.3代码实现

#include <iostream>
#include <algorithm>

using namespace std;

template<typename T> void bubble_sort(T arr[],int len) {

    for(int i = 0; i < len - 1; i++) {
        for(int j = 0; j < len - 1 - i; j++) {
            if(arr[j] > arr[j + 1])
                swap(arr[j],arr[j+1]);
        }
    }
}

int main(){

    int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
    int len = (int)sizeof(arr)/sizeof(*arr);
    bubble_sort(arr,len);
    for(int i = 0;i < len;i++)
        cout << arr[i] << " ";
    cout << endl;
    float arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 };
    len = (int)sizeof(arrf)/sizeof(*arrf);
    bubble_sort(arrf,len);
    for(int i = 0;i < len;i++)
        cout << arrf[i] << " ";
    cout << endl;

    return 0;
}

2.选择排序(Selection Sort)

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

2.1算法描述

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

  1. 初始状态：无序区为R[1…n],有序区为空
  2. 第i趟排序(i=1,2,3,…,n-1)开始时，当前有序区和无序区元素分别是R[1,2,..,i-1]和R[i,…,n],该趟排序从当前的无序区中选出关键字最小的记录，将它与无序区的第一个记录交换，使R[1,2,…,i]和R[i+1,…,n]分别变成记录个数增加1的新有序区和记录个数减少1的新无序区
  3. n-1趟结束，数组有序化

2.2动图演示

2.3代码实现

template<typename T>
void selection_sort(T arr[],int len) {
    for(int i = 0;i < len - 1;i++){
        int min = i;
        for(int j = i + 1;j < len;j++)
            if(arr[j] < arr[min])
                min = j;

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

3.插入排序(Insertion Sort)

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

3.1算法描述

  1. 从第一个元素开始，该元素可以认为已经被排序
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
  3. 如果该元素(已排序)大于新元素，将该元素移到下一位置
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置的后方
  6. 重复步骤2-5

3.2动图演示

3.3代码实现

template<typename T>
void insertion_sort(T arr[],int len) {
   for(int i = 1;i < len;i++){

    T key = arr[i];
    int j = i - 1;
    while(j >= 0 && key < arr[j]){
        arr[j+1] = arr[j];
        j--;
    }

    arr[j+1] = key;
   }
}

4.希尔排序(Shell Sort)

希尔排序按其设计者希尔（Donald Shell）的名字命名，该算法由1959年公布。一些老版本教科书和参考手册把该算法命名为Shell-Metzner，即包含Marlene Metzner Norton的名字，但是根据Metzner本人的说法，“我没有为这种算法做任何事，我的名字不应该出现在算法的名字中。”

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

  • 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
  • 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

4.1算法描述

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，然后逐步缩小步长，步长为1的操作完成时，序列变得有序，具体算法描述如下：

  1. 选择一个增量序列t1,t2,…,tk,其中tk=1
  2. 按增量个数k，对序列进行k趟排序
  3. 每趟排序，根据对应的增量ti,将待排序序列分割成若干长度为m的子序列，分别对各子序列进行直接插入排序。当增量因子(步长)为1的时候，真个序列作为一个表处理，表长度即为整个序列的长度

4.2动图演示

4.4代码实现

template<typename T>
void shell_sort(T arr[],int len) {
     int h = 1;
     while(h < len / 3)
         h = 3 * h + 1;

    while(h >= 1){
         for(int i = h;i < len;i++){
             for(int j = i;j >= h ;j -= h)
                 if(arr[j] < arr[j-h])
                     swap(arr[j],arr[j-h]);
         }
         h /= 3;
     }
}

5.归并排序(Merge Sort)

归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为O(nlogn)（大O符号）。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

5.1算法描述

  • 递归法
  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
  2. 设定两个指针，最初位置分别为两个已排序序列的起始位置
  3. 比较两个指针所指向的元素，选择相对较小的元素放入到合并空间，并移动指针到下一位置
  4. 重复步骤3直到某一指针到达序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾
  • 迭代法
  1. 把长度为n的输入序列分成两个长度为n/2的子序列
  2. 对这两个子序列分别采用归并排序
  3. 将两个排序好的子序列合并成一个最终的排序序列

5.2动图演示

5.3代码实现

迭代版

template<typename T>
void merge_sort(T arr[],int len) {
    T* a = arr;
    T* b = new T[len];

    for(int seg = 1; seg < len; seg += seg) {

        for(int start = 0; start < len; start += seg + seg) {
            int low = start,mid = min(start + seg,len),high = min(start + seg + seg,len);
            int k = low;
            int start1 = low,end1 = mid;
            int start2 = mid,end2 = high;
            while(start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while(start1 < end1)
                b[k++] = a[start1++];
            while(start2 < end2)
                b[k++] = a[start2++];
        }
        T* temp = a;
        a = b;
        b = temp;
    }

    if(a != arr) {

        for(int i = 0; i < len; i++)
            b[i] = a[i];
        b = a;

    }
    delete[] b;

}

递归版

void Merge(vector<int> &arr,int front,int mid,int end){
    vector<int> LeftSubArray(arr.begin()+front,arr.begin()+mid+1);
    vector<int> RightSubArray(arr.begin()+mid+1,arr.begin()+end+1);
    
    int idxLeft = 0,idxRight = 0;
    
    // Copy Array[front ... mid] to LeftSubArray
    // Copy Array[mid+1 ... end] to RightSubArray
    LeftSubArray.insert(LeftSubArray.end(),numeric_limits<int>::max());
    RightSubArray.insert(RightSubArray.end(),numeric_limits<int>::max);
    
    // Pick min of LeftSubArray[idxLeft] and RightSubArray[idxRight], and put into Array[i] 
    for(int i = front;i <= end;i++){
        if(LeftSubArray[idxLeft] < RightSubArray[idxRight]){
            arr[i] = LeftSubArray[idxLeft];
            idxLeft++;
        }
        else{
            arr[i] = RightSubArray[idxRight];
            idxRight++;
        }
        
    }

}
void MergeSort(vector<int> & arr,int front,int end){

    if(front >= end)
        return;
    int mid = (front+end)/2;
    MergeSort(arr,front,mid);
    MergeSort(arr,mid+1,end);
    Merge(arr,front,mid,end);
}

6.快速排序(Quick Sort)

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。时间复杂度为O(nlogn)。

6.1算法描述

快速排序使用分治法策略把一个序列分为连个子序列，步骤为：

  1. 从数列中挑出一个元素，成为“基准”
  2. 重新排序数列，所有比基准值小的数字放在基准前面，所有比基准大的数字放在基准后面(相同的数可以到任意一边)。在这个分割结束之后，该基准就处于该序列的中间位置。这个操作称为分割操作
  3. 递归的把小于基准值元素的子数列和大于基准值的子数列排序

递归到最底部的时候，数列的大小是0或1，也就是已经排序好了。这个算法一定会结束，因为在每次迭代中，它至少会把一个元素放到它最后的位置去。

6.2动图演示

6.3代码实现

迭代法

struct Range{
    int start,end;
    Range(int s = 0,int e = 0){
        start = s;
        end = e;
    }
};

template<typename T>
void quick_sort(T arr[],int len){
    if(arr == nullptr || len <= 0)
        return;

    Range r[len];
    int p = 0;
    r[p++] = Range(0,len-1);
    while(p){
        Range range = r[--p];
        if(range.start >= range.end)
            continue;
        T mid = arr[range.end];
        int left = range.start;
        int right = range.end - 1;
        while(left < right){
            while(arr[left] < mid && left < right)
                left++;
            while(arr[right] >= mid && left < right)
                rught--
            swap(arr[left],arr[right]);
        }
        if(arr[left] > arr[range.end])
            swap(arr[left],arr[range.end]);
        else
            left++;
        r[p++] = Range(range.start,left - 1);
        r[p++] = Range(left + 1,range.end);
    }
}

递归法

template<typename T>
void quick_sort_recursive(T arr[],int start,int end){
    if(start >= end)
        return;
    T mid = arr[end];
    int left = start;
    int right = end;

    while(left < right){
        while(left < right && arr[left] < arr[end])
            left++;
        while(left < right && arr[right] >= arr[end])
            right--;
        swap(arr[left],arr[right]);
    }
    if(arr[left] > arr[end])
        swap(arr[left],arr[end]);
    else
        left++;
    quick_sort_recursive(arr,start,left-1);
    quick_sort_recursive(arr,left+1,end);
}

template<typename T>
void quick_sort(T arr[],int len){
    quick_sort_recursive(arr,0,len-1);
}

7.堆排序(Heap Sort)

堆排序是指利用堆这种数据结构所涉及的一种排序算法，堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于(或者大于)它的父节点。

为了方便介绍算法，堆中定义以下几种操作：

  • 最大堆调整：将堆的末端节点做调整，使得子节点永远小于父节点
  • 创建最大堆：将堆中的所有数据重新排序
  • 堆排序：移除位在根节点的数据，并作最大堆调整的递归运算

7.1算法描述

  1. 将初始待排序关键字序列(R1,R2,…,Rn)构建成大顶堆，此堆为初始的无序区
  2. 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,…,Rn-1)和新的有序区(Rn),且满足(R1,R2,…,Rn-1)<=(Rn)
  3. 由于上述交换可能破坏大顶堆的性质，因此需要对无序区(R1,R2,…,Rn-1)调整为堆，然后再次重复步骤2，直到有序区元素个数为n-1，排序完成

7.2动图演示

7.3代码实现

template<typename T>
void max_heapify(T arr[],int start,int end){
    int dad = start;
    int son = 2*start+1;

    while(son <= end){
        if(son + 1 <= end && arr[son] < arr[son + 1])
            son++;
        if(arr[son] < arr[dad])
            return;
        else{
            swap(arr[dad],arr[son]);
            dad = son;
            son = 2*dad+1;
        }

    }
}

template<typename T>
void heap_sort(T arr[],int len){
    for(int i = len/2-1;i >= 0;i--)
        max_heapify(arr,i,len-1);
    for(int i = len - 1;i > 0;i--){
        swap(arr[0],arr[i]);
        max_heapify(arr,0,i-1);
    }
}

8.计数排序(Counting Sort)

计数排序（Counting sort）是一种稳定的线性时间排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。

8.1算法描述

通俗地理解，例如有10个年龄不同的人，统计出有8个人的年龄比A小，那A的年龄就排在第9位，用这个方法可以得到其他每个人的位置，也就排好了序。当然，年龄有重复时需要特殊处理（保证稳定性），这就是为什么最后要反向填充目标数组，以及将每个数字的统计减去1的原因。算法的步骤如下：

  1. 找出待排序的数组中最大和最小的元素
  2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
  3. 对所有的技术累加(从C中的第一个元素开始，每一项和前一项相加)
  4. 反向填充目标数组：将每个元素i放在新数组的第C[i]项，每放一个元素就将C[i]减去1

8.2动图演示

8.3代码实现

template<typename T>
T* counting_sort(T arr[]){
    int len = (int)sizeof(arr)/sizeof(*arr);
    T* sorted = new int[len];

    int max = arr[0];
    for(int i = 1;i < len;i++)
        if(arr[i] > max)
            max = arr[i];

    countitng_sort_sub(arr,sorted,max);
    return sorted;
}

template<typename T>
void counting_sort_sub(T arr[],T sorted[],int len){
    T* count = new T[len];

    //计数
    int lenA = (int)sizeof(arr)/sizeof(*arr);
    for(int i = 0;i < lenA;i++)
        count[arr[i]]++;

    //求计数和
    for(int i = 1;i <= len;i++)
        count[i] += count[i-1];

    //整理
    for(int j = lenA-1;j >= 0;j--){
        sorted[count[arr[j]] - 1] = arr[j];
        --count[arr[j]];
    }
}

9.桶排序(Bucket Sort)

桶排序（Bucket sort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间O(n)（大O符号））。但桶排序并不是比较排序，它不受到O(nlogn)下限的影响。

9.1 算法描述

  1. 设置一个定量的数组当作空桶
  2. 遍历输入数据，并且把数据一个一个放到对应的桶里面去
  3. 对每个不是空的桶进行排序
  4. 从不是空的桶里面把排好序的数据拼接起来

9.2 图片演示

9.3代码实现

假设数据分布在[0，100)之间，每个桶内部用链表表示，在数据入桶的同时插入排序。然后把各个桶中的数据合并。

#include<iterator>
#include<iostream>
#include<vector>
using namespace std;
const int BUCKET_NUM = 10;

struct ListNode{
    explicit ListNode(int i=0):mData(i),mNext(NULL){}
    ListNode* mNext;
    int mData;
};

ListNode* insert(ListNode* head,int val){
    ListNode dummyNode;
    ListNode *newNode = new ListNode(val);
    ListNode *pre,*curr;
    dummyNode.mNext = head;
    pre = &dummyNode;
    curr = head;
    while(NULL!=curr && curr->mData<=val){
        pre = curr;
        curr = curr->mNext;
    }
    newNode->mNext = curr;
    pre->mNext = newNode;
    return dummyNode.mNext;
}


ListNode* Merge(ListNode *head1,ListNode *head2){
    ListNode dummyNode;
    ListNode *dummy = &dummyNode;
    while(NULL!=head1 && NULL!=head2){
        if(head1->mData <= head2->mData){
            dummy->mNext = head1;
            head1 = head1->mNext;
        }else{
            dummy->mNext = head2;
            head2 = head2->mNext;
        }
        dummy = dummy->mNext;
    }
    if(NULL!=head1) dummy->mNext = head1;
    if(NULL!=head2) dummy->mNext = head2;
    
    return dummyNode.mNext;
}

void BucketSort(int n,int arr[]){
    vector<ListNode*> buckets(BUCKET_NUM,(ListNode*)(0));
    for(int i=0;i<n;++i){
        int index = arr[i]/BUCKET_NUM;
        ListNode *head = buckets.at(index);
        buckets.at(index) = insert(head,arr[i]);
    }
    ListNode *head = buckets.at(0);
    for(int i=1;i<BUCKET_NUM;++i){
        head = Merge(head,buckets.at(i));
    }
    for(int i=0;i<n;++i){
        arr[i] = head->mData;
        head = head->mNext;
    }
}

10.基数排序(Radix Sort)

基数排序（英语：Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机（Tabulation Machine）上的贡献。

它是这样实现的：将所有待比较数值（正整数）统一为同样的数字长度，数字较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

10.1算法描述

  1. 取得数组中的最大数，并取得位数
  2. arr为原始数组，从最低位开始去每个数组成radix数组
  3. 对radix进行技术排序(利用计数排序适用于小范围数的特点)

10.2动图演示

10.3代码实现

int maxbit(int data[], int n) //辅助函数，求数据的最大位数
{
    int maxData = data[0];        ///< 最大数
    /// 先求出最大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。
    for (int i = 1; i < n; ++i)
    {
        if (maxData < data[i])
            maxData = data[i];
    }
    int d = 1;
    int p = 10;
    while (maxData >= p)
    {
        //p *= 10; // Maybe overflow
        maxData /= 10;
        ++d;
    }
    return d;
/*    int d = 1; //保存最大的位数
    int p = 10;
    for(int i = 0; i < n; ++i)
    {
        while(data[i] >= p)

        {
            p *= 10;
            ++d;
        }
    }
    return d;*/
}
void radixsort(int data[], int n) //基数排序
{
    int d = maxbit(data, n);
    int *tmp = new int[n];
    int *count = new int[10]; //计数器
    int i, j, k;
    int radix = 1;
    for(i = 1; i <= d; i++) //进行d次排序
    {
        for(j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空计数器
        for(j = 0; j < n; j++)
        {
            k = (data[j] / radix) % 10; //统计每个桶中的记录数
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
        for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
        {
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for(j = 0; j < n; j++) //将临时数组的内容复制到data中
            data[j] = tmp[j];
        radix = radix * 10;
    }
    delete []tmp;
    delete []count;
}



参考文献

https://www.cnblogs.com/onepixel/p/7674659.html [本文动图来自该博客]

https://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/ovs98/p/9916672.html