即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

排序算法归纳深度总结

编程语言 RandomXM 18℃ 0评论
本文目录
[隐藏]

对几种内部排序算法进行归纳总结,其中包括:直接插入排序,希尔排序,冒泡排序,简单选择排序,堆排序,快速排序,归并排序

排序方式 平均情况 最好情况 最坏情况 辅助空间 稳定性
直接插入排序 O(n2) O(n) O(n^2) O(1) 稳定
希尔排序 O(n1.3) O(n) O(n2) O(1) 不稳定
冒泡排序 O(n2) O(n) O(n2) O(1) 稳定
简单选择排序 O(n2) O(n2) O(n2) O(1) 不稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
快速排序 O(nlogn) O(nlogn) O(n2) O(logn)~O(n) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定

P.S.排序算法稳定性的简单形式化定义为:如果Ai = Aj,排序前Ai在Aj之前,排序后Ai还在Aj之前,则称这种排序算法是稳定的



1.插入排序


1.1.直接插入排序

1.1.1.基本思想

直接插入排序是一种简单直观的排序算法,它是将一个元素直接插入到已排序好的有序序列中。

1.1.2.算法运作

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

1.1.3.效果图

直接插入排序

1.1.4.算法实现

// 直接插入排序
// 最差时间复杂度  O(n^2)
// 最优时间复杂度  O(n)
// 平均时间复杂度  O(n^2)
// 所需辅助空间    O(1)
// 稳定性          稳定
#include 
void InsertSort(int a[], int n)
{
    int i, j, temp;
    for (i = 1; i < n; ++i) //认为第一个元素已被排序
    {
        temp = a[i]; //待插入元素保存到辅助空间中
        j = i - 1;//从后向前扫描
        while (j >= 0 && a[j] > temp)
        {
            a[j + 1] = a[j];//扫描到的元素比待插入元素大则向后移一位
            --j;
        }
        a[j + 1] = temp;//扫描到的元素小于或等于待插入元素,将元素插入到其后一位
    }
}

int main()
{
    int a[8] = { 6, 5, 3, 1, 8, 7, 2, 4 };
    int size = sizeof(a) / sizeof(int); //待排序序列长度

    InsertSort(a, size);

    printf("插入排序结果:");
    for (int i = 0; i < size; ++i)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

插入排序不适合对数据量比较大的序列进行排序,适合的对少量元素进行排序。稳定排序算法。


1.2.希尔排序

1.2.1.基本思想

先将整个待排序元素序列分割成为若干子序列分别进行直接插入排序,待整个序列中的元素“基本有序”时,再对全体元素进行依次直接插入排序。

1.2.2.算法运作

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

1.2.3.效果图

此处输入图片的描述

1.2.4.算法实现

在这里简单处理增量序列:增量序列d={n/2, n/4, n/8…… 1},n为待排序列元素个数。

// 希尔排序——直接插入排序改进
// 最差时间复杂度  根据步长序列的不同而不同
// 最优时间复杂度  O(n)
// 平均时间复杂度  根据步长序列的不同而不同
// 所需辅助空间    O(1)
// 稳定性          不稳定
// 增量序列d = {n/2 ,n/4, n/8 .....1}
#include 
void ShellInsertSort(int a[], int n, int gap)
{
    for (int i = gap; i < n; ++i)
    {
        //在该子序列中进行插入排序
        int j = i - gap;
        int temp = a[i];
        while (j >= 0 && a[j] > temp)
        {
            a[j + gap] = a[j];//先将第i-gap元素在此子序列中后移一个单位
            j -= gap;
        }
        a[j + gap] = temp;//扫描到的元素小于或等于待插入元素,将元素插入到其后一位
    }
}

void ShellSort(int a[], int n)
{
    int gap = n / 2;//初始增量
    while (gap >= 1)
    {
        ShellInsertSort(a, n, gap);
        gap /= 2;//每进行一次排序增量变为上一次的1/2
    }
}
int main()
{
    int a[8] = { 4, 7, 2, 6, 5, 1, 8, 3 };
    int size = sizeof(a) / sizeof(int); //待排序序列长度

    ShellSort(a, size);//希尔排序

    printf("希尔排序结果:");
    for (int i = 0; i < size; ++i)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

希尔排序时效分析与增量因子序列的选取有关,本文只是采用了最简单的一种增量因子序列。另外希尔排序是不稳定的排序算法,虽然一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱。


比如序列:{ 3, 5, 10, 8, 7, 2, 8, 1, 20, 6 },h=2时分成两个子序列 { 3, 10, 7, 8, 20 } 和 { 5, 8, 2, 1, 6},未排序之前第二个子序列中的8在前面,现在对两个子序列进行插入排序,得到 { 3, 7, 8, 10, 20 } 和 { 1, 2, 5, 6, 8 } ,即 { 3, 1, 7, 2, 8, 5, 10, 6, 20, 8 } ,两个8的相对次序发生了改变。


2.冒泡排序


2.1.普通冒泡排序

2.1.1.基本思想

冒泡排序是一种极其简单的排序算法,它重复地走访要排序的元素,一次比较相邻两个元素,如果他们的


顺序错误就把他们调换过来,直到没有元素再需要交换,排序完成。

2.1.2.算法运作

  1. 比较相邻的元素,如果前一个比后一个大,就把它们两个调换位置
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

2.1.3.效果图

冒泡排序算法


冒泡排序算法

2.1.4.算法实现

// 冒泡排序
// 最差时间复杂度  O(n^2)
// 最优时间复杂度  O(n)
// 平均时间复杂度  O(n^2)
// 所需辅助空间    O(1)
// 稳定性          稳定
#include 
#include
void BubbleSort(int a[], int n)
{
    for (int i = 0; i < n - 1; ++i)
    {
        for (int j = 0; j < n - 1 - i; ++j)//最后面的几个无需在进行排序
        {
            if (a[j] > a[j + 1])//若条件改成>=,则变为不稳定算法
            {
                std::swap(a[j], a[j + 1]);//依次比较相邻的两个元素,使较大的那个向后移
            }
        }
    }
}
int main()
{
    int a[8] = { 4, 7, 2, 6, 5, 1, 8, 3 };
    int size = sizeof(a) / sizeof(int); //待排序序列长度

    BubbleSort(a, size);//冒泡排序

    printf("冒泡排序结果:");
    for (int i = 0; i < size; ++i)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

尽管冒泡排序是最容易了解和实现的排序算法之一,但它对于少数元素之外的数列排序是很没有效率的。稳定排序算法。


2.2.鸡尾酒排序

2.2.1.基本思想

鸡尾酒排序,也叫定向冒泡排序,是冒泡排序的一种改进。此算法与冒泡排序的不同处在于从低到高然后从高到低,而冒泡排序则仅从低到高去比较序列里的每个元素。它可以得到比冒泡排序稍微好一点的效能。

2.2.2.效果图

鸡尾酒排序

2.2.3.算法实现

// 鸡尾酒排序
// 最差时间复杂度  O(n^2)
// 最优时间复杂度  O(n)
// 平均时间复杂度  O(n^2)
// 所需辅助空间    O(1)
// 稳定性          稳定
#include 
#include
void BubbleSort(int a[], int left, int right)
{
    while (left < right)
    {
        for (int i = left; i < right; ++i)//前半轮,将最大元素放到后面
        {
            if (a[i] > a[i + 1])
                std::swap(a[i], a[i+1]);
        }
        right--;//此时最后面的数已为最大数,无需再参加排序
        for(int i = right; i>left; --i)
            if (a[i - 1] > a[i])
            {
                std::swap(a[i - 1], a[i]);
            }
        left++;//此时最前面的数已为最小数,无需再参加排序
    }
}
int main()
{
    int a[8] = { 4, 7, 2, 6, 5, 1, 8, 3 };
    int size = sizeof(a) / sizeof(int); //待排序序列长度

    BubbleSort(a, 0, size-1);//鸡尾酒排序

    printf("鸡尾酒排序结果:");
    for (int i = 0; i < size; ++i)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

以序列(2,3,4,5,1)为例,鸡尾酒排序只需要访问一次序列就可以完成排序,但如果使用冒泡排序则需要四次。但是在乱数序列的状态下,鸡尾酒排序与冒泡排序的效率都很差劲。稳定排序算法


3.选择排序


3.1.简单选择排序

3.1.1.基本思想

在要排序的一组数中,选出最小(或者最大)的一个数与第1个位置的数交换;然后在剩下的数当中再找最小(或者最大)的与第2个位置的数交换,依次类推,直到第n-1个元素(倒数第二个数)和第n个元素(最后一个数)比较为止。

3.1.2.效果图

简单选择排序

3.1.3.算法实现

// 简单选择排序
// 最差时间复杂度  O(n^2)
// 最优时间复杂度  O(n^2)
// 平均时间复杂度  O(n^2)
// 所需辅助空间    O(1)
// 稳定性          不稳定
#include 
#include
int SelectMinKey(int a[], int n, int i)//寻找i~n-1中值最小的数,并返回其下标
{
    int k = i;
    for (int j = k + 1; j < n; ++j)
        if (a[k] > a[j])
            k = j;
    return k;
}

void SelectSort(int a[], int n)
{
    int key;
    for (int i = 0; i < n; ++i)
    {
        key = SelectMinKey(a, n, i);//得到最小值元素的小标
        if (key != i)
            std::swap(a[i], a[key]);
    }
}

int main()
{
    int a[8] = { 4, 7, 2, 6, 5, 1, 8, 3 };
    int size = sizeof(a) / sizeof(int); //待排序序列长度

    SelectSort(a, size);//简单选择排序

    printf("简单选择排序结果:");
    for (int i = 0; i < size; ++i)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

选择排序是不稳定的排序算法,不稳定发生在最小元素与[i]交换的时刻


比如序列:{ 5, 8, 5, 2, 9},一次选择的最小元素是2,然后把2和第一个5进行交换,从而改变了两个元素5的相对次序。


3.2.堆排序

3.2.1.基本思想

堆的定义如下:具有n个元素的序列(k1,k2,…,kn),当且仅当满足

{kik_2ikik2i+1{kik2ikik2i+1(i=1,2,...,n/2)

时称之为。由堆的定义可看出,堆顶元素(即第一个元素的值)必须为最小项(小顶堆)或最大项(大顶堆)。堆是一个近似完全二叉树的结构(通常堆是通过一维数组来实现的),并同时满足堆的性质:即子结点的键值总是小于(或者大于)它的父节点

3.2.2.算法运作

  1. 创建一个堆
  2. 把堆顶元素(最大值)和堆尾元素互换
  3. 把堆的尺寸缩小1,并调用heapify(A, 0)从新的堆顶元素开始进行堆调整
  4. 重复步骤2,直到堆的尺寸为1

3.2.3.效果图

最小堆最大堆


堆调整


堆排序

3.2.4.算法实现

// 堆排序
// 最差时间复杂度  O(nlogn)
// 最优时间复杂度  O(nlogn)
// 平均时间复杂度  O(nlogn)
// 所需辅助空间    O(1)
// 稳定性          稳定
#include 
#include
int heapsize; //堆大小
void Heapify(int a[], int i) //堆调整函数(最大堆)
{
    int leftchild = 2 * i + 1; //左孩子索引
    int rightchild = 2 * i + 2;//右孩子索引
    int largest;  //选出当前节点与左右孩子之中的最大值
    if (leftchild < heapsize && a[leftchild] > a[i])
        largest = leftchild;
    else
        largest = i;
    if (rightchild < heapsize && a[rightchild] > a[largest])
        largest = rightchild;
    if (largest != i)
    {
        std::swap(a[i], a[largest]);   // 把当前结点和它的最大(直接)子节点进行交换
        Heapify(a, largest);           // 递归调用,继续从当前结点向下进行堆调整
    }
}

void BuildHeap(int a[], int n) //建堆函数
{
    heapsize = n;
    for (int i = heapsize / 2 - 1; i >= 0; --i) // 对每一个非叶结点
        Heapify(a, i);  // 不断的堆调整
}

void HeapSort(int a[], int n)   
{
    BuildHeap(a, n);
    for (int i = n - 1; i >= 1; --i)
    {
        std::swap(a[0], a[i]);   // 将堆顶元素(当前最大值)与堆的最后一个元素互换(该操作很有可能把后面元素的稳定性打乱,所以堆排序是不稳定的排序算法)
        heapsize--;              // 从堆中去掉最后一个元素
        Heapify(a, 0);           // 从新的堆顶元素开始进行堆调整
    }
}

int main()
{
    int a[8] = { 4, 7, 2, 6, 5, 1, 8, 3 };
    int size = sizeof(a) / sizeof(int); //待排序序列长度

    HeapSort(a, size);  //堆排序

    printf("堆排序结果:");
    for (int i = 0; i < size; ++i)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

堆排序是不稳定的排序算法,不稳定发生在堆顶元素与A[i]交换的时刻。


比如序列:{ 9, 5, 7, 5 },堆顶元素是9,堆排序下一步将9和第二个5进行交换,得到序列 { 5, 5, 7, 9 },再进行堆调整得到{ 7, 5, 5, 9 },重复之前的操作最后得到{ 5, 5, 7, 9 }从而改变了两个5的相对次序。


4.快速排序

4.1.基本思想

  1. 选择一个基准元素,通常选择第一个元素或者最后一个元素。
  2. 通过一趟排序将待排序的序列分割成独立的两部分,其中一部分序列的元素值均比基准元素值小。另一部分序列的元素值比基准值大。
  3. 此时基准元素在其排好序后的正确位置.
  4. 然后分别对这两部分序列用同样的方法继续进行排序,直到整个序列有序。

4.2.效果图

快速排序

4.3.算法实现

// 快速排序
// 最差时间复杂度  每次选取的基准都是最大(小)的元素,导致每次只划分出了一个子序列,需要进行n-1次划分才能结束递归,时间复杂度为O(n^2)
// 最优时间复杂度  每次选取的基准都能使划分均匀,只需要logn次划分就能结束递归,时间复杂度为O(nlogn)
// 平均时间复杂度  O(nlogn)
// 所需辅助空间    O(logn)~O(n),主要是递归造成的栈空间的使用(保存left和right等局部变量),取决于递归树的深度一般为O(logn),最差为O(n)
// 稳定性          不稳定
#include 
#include
int Partition(int a[], int left, int right)//划分函数
{
    int pivot = a[right]; //选择最后一个元素作为基准
    int tail = left - 1; //tail用来存储小于基准的子数组最后一个元素的索引
    for (int i = left; i < right; ++i)
    {
        if (a[i] <= pivot) //把小于等于基准的元素放到左子数组中
        {
            ++tail;//左子数组数目加1,tail向右移动一位
            if(tail != i )
                std::swap(a[tail], a[i]);//将小于基准的和大于基准的数进行交换
        }
    }
    std::swap(a[tail + 1], a[right]); // 最后把基准放到前一个子数组的后边,基准的左子数组大于基准的子数组
    return tail + 1; // 返回基准的索引
}
void QuickSort(int a[], int left, int right)
{
    if (left < right)
    {
        int pivot_index;                        // 基准的索引
        pivot_index = Partition(a, left, right);
        QuickSort(a, left, pivot_index - 1); //遍历左子数组
        QuickSort(a, pivot_index + 1, right);//遍历右子数组
    }
}

int main()
{
    int a[8] = { 4, 7, 2, 6, 5, 1, 8, 3 };
    int size = sizeof(a) / sizeof(int); //待排序序列长度

    QuickSort(a, 0, size-1);//快速排序

    printf("快速排序结果:");
    for (int i = 0; i < size; ++i)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

快速排序是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;


快速排序是不稳定的排序算法,不稳定发生在基准元素与A[tail+1]交换的时刻。


比如序列:{ 1, 3, 4, 2, 8, 9, 8, 7, 5}, 基准元素是5,一次划分操作后5要和第一个8进行交换, 从而改变了两个元素8的相对次序。


5.归并排序

5.1.基本思想

归并(Merge)排序是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。


归并排序的实现分为递归实现非递归(迭代)实现。递归实现的归并排序将一个大问题分割成小问题分别解决,然后用所有小问题的答案来解决整个大问题。非递归(迭代)实现的归并排序首先进行是两两归并,然后四四归并,然后是八八归并,一直下去直到归并了整个数组。

5.2.效果图

归并排序

5.3.算法实现

// 归并排序
// 最差时间复杂度  O(nlogn)
// 最优时间复杂度  O(nlogn)
// 平均时间复杂度  O(nlogn)
// 所需辅助空间    O(n)
// 稳定性          稳定
#include 
#include

int L[10];    // 两个子数组定义成全局变量(辅助存储空间,大小正比于元素的个数)
int R[10];

void Merge(int A[], int left, int middle, int right)// 合并两个已排好序的数组A[left...middle]和A[middle+1...right]
{
    int n1 = middle - left + 1;     // 两个数组的大小
    int n2 = right - middle;
    for (int i = 0; i < n1; i++)    // 把两部分分别拷贝到两个数组中
        L[i] = A[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = A[middle + j + 1];
    L[n1] = INT_MAX;                // 使用无穷大作为哨兵值放在子数组的末尾
    R[n2] = INT_MAX;                // 这样可以免去检查某个子数组是否已读完的步骤
    int i = 0;
    int j = 0;
    for (int k = left; k <= right; k++) // 依次比较两个子数组中的值,每次取出更小的那一个放入原数组
    {
        if (L[i] <= R[j])
        {
            A[k] = L[i];
            i++; //若不把L[n1]设置成INT_MAX,这里应判断是否已走完L[]数组
        }
        else
        {
            A[k] = R[j];
            j++;
        }
    }

}

void Mergesort_recursion(int A[], int left, int right) // 递归实现的归并排序(自顶向下)
{
    int middle = (left + right) / 2;
    if (left < right)          // 当待排序的序列长度为1时(left == right),递归“开始回升”
    {
        Mergesort_recursion(A, left, middle);
        Mergesort_recursion(A, middle + 1, right);
        Merge(A, left, middle, right);
    }
}

void Mergesort_iteration(int A[], int left, int right)  // 非递归(迭代)实现的归并排序(自底向上)
{
    int low, middle, high;    // 子数组索引,前一个为A[low...middle],后一个子数组为A[middle+1...high]
    for (int size = 1; size <= right - left; size *= 2) // 子数组的大小初始为1,每轮翻倍
    {
        low = left;
        while (low + size - 1 <= right - 1) //后一个子数组存在(需要归并)
        {
            middle = low + size - 1;
            high = middle + size;
            if (high > right)               //后一个子数组大小不足size
                high = right;
            Merge(A, low, middle, high);
            low = high + 1;                 //前一个子数组索引向后移动
        }
    }
}

int main()
{
    int a1[8] = { 4, 7, 2, 6, 5, 1, 8, 3 };
    int a2[8] = { 4, 7, 2, 6, 5, 1, 8, 3 };
    int size1 = sizeof(a1) / sizeof(int); //待排序序列长度
    int size2 = sizeof(a2) / sizeof(int); //待排序序列长度

    Mergesort_recursion(a1, 0, size1 - 1); // 递归归并排序
    Mergesort_iteration(a2, 0, size2 - 1); // 非递归(迭代)归并排序

    printf("递归归并排序结果:");
    for (int i = 0; i < size1; ++i)
    {
        printf("%d ", a1[i]);
    }
    printf("\n");

    printf("非递归归并排序结果:");
    for (int i = 0; i < size2; ++i)
    {
        printf("%d ", a2[i]);
    }
    printf("\n");
    return 0;
}

归并排序的效率是比较高的,设数列长为N,将数列分开成小数列一共要logN步,每步都是一个合并有序数列的过程,时间复杂度可以记为O(N),故一共为O(N*logN)。稳定排序算法


6.总结

设待排序元素的个数为n

  1. 当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序。
  2. 当n较大,内存空间允许,且要求稳定性 -> 归并排序
  3. 当n较小,可采用直接插入或直接选择排序。

转载请注明:CodingBlog » 排序算法归纳深度总结

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情