【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)

简介: 【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)

一、排序基本概念

排序是处理数据的一种最常见的操作,所谓排序就是将数据按某字段规律排列,所谓的字段就是数据节点的其中一个属性。比如一个班级的学生,其字段就有学号、姓名、班级、分数等等,我们既可以针对学号排序,也可以针对分数排序。

1、稳定性

在一组无序数据中,若两个待排序字段一致的数据,在排序前后相对位置不变,则称排序算法是稳定的,否则是不稳定的。

2、内排序与外排序

如果待排序数据量不大,可以一次性全部装进内存进行处理,则称为内排序,若数据量大到无法一次性全部装进内存,而需要将数据暂存外存,分批次读入内存进行处理,则称为外排序。

3、性能分析

不同的排序算法性能不同,详细性能数据如下表所示:

从表中可以得到一些简单的指导思路:

  • 选择排序、插入排序和冒泡排序思路简单,但时间效率较差,只适用于数据样本较小的场合,这几种算法的好处是不需要额外开辟空间,空间复杂度是常量。
  • 希尔排序是插入排序的改进版,在平均情况下时间效率要比直接插入法好很多,也不需要额外开辟空间,要注意的是希尔排序是不稳定排序。
  • 快速排序是所有排序算法中时间效率最高的,但由于快排是一种递归运算,对内存空间要求较高,当数据量较大时,会消耗较多的内存。


二、插入排序

1、思路

假设前面已经有i节点是有序的,那么就从第i+1个节点开始,插入到前面的i个节点的合适的位置中。由于第一个元素自身总是有序的,因此从第2个开始,不断插入前面的有序序列,直到全部排列完毕。

2、时间复杂度分析

假设总共有n个节点,那么总共需要将n−1个节点插入到有序序列中,而插入节点时需要找到合适的位置,显然这个查找的过程时间复杂度是O(n−i),因此插入排序的时间复杂度是O(n−1)(n−i),即O(n^2)

3、示例代码

#include <stdio.h>
#include <stdbool.h>

int swap_count = 0;
int comp_count = 0;

void show(int data[], int len)
{
    int i;
    for(i=0; i<len; ++i)
    {
        printf("%d\t", data[i]);
    }
    printf("\n");
}


//小到大排序
void insertionSort(int data[], int len)
{
    if(len <= 1)
        return;

    int i, j;
    for(i=1; i<len; i++)
    {
        int tmp = data[i];

        for(j=i-1; j>=0; j--)
        {
            comp_count++;
            if(data[j] < tmp)
            {
                break;
            }
            else
            {
                swap_count++;
                data[j+1] = data[j];
            }
        }
        swap_count++;
        data[j+1] = tmp;
    }
}

int main(int argc, char **argv)
{
    srand(time(NULL));

    int i, data[100];
    for(i=0; i<100; ++i)
    {
        data[i] = rand() % 1000;
    }
    printf("随机序列: ");
    show(data, 100);

    printf("插入排序: ");
    insertionSort(data, 100);
    show(data, 100);

    printf("总共比较次数: %d\n", comp_count);
    printf("总共移动次数: %d\n", swap_count);

    return 0;
}

4、代码分析

三、冒泡排序

1、概念

冒泡排序基于这样一种简单的思路:从头到尾让每两个相邻的元素进行比较,顺序就保持位置不变,逆序就交换位置。可以预料,经过一轮比较,序列中具有“极值”的数据,将被挪至序列的末端。


2、时间复杂度

假如序列中有n个数据,那么在最极端的情况下,只需要经过n−1轮的比较,则一定可以将所有的数据排序完毕。冒泡法排序的时间复杂度是O(n2)

最好:12345678

最坏(完全逆序): 87654321

3、思路

总思路先把最大的往右边挤,把第二大往最右边第二位置挤…

逐对比较,并交换

4、示例代码

#include <stdio.h>

int comp_count = 0; // 数据比较次数
int swap_count = 0; // 数据交换次数

void show(int data[], int len)
{
    int i;
    for(i=0; i<len; ++i)
    {
        printf("%d\t", data[i]);
    }
    printf("\n");
}

void swap(int *a, int *b)
{
    swap_count++;

    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

void bubbleSort(int data[], int len)
{
    int k=0;
    while(1)
    {
        bool done = true;

        int i;
        for(i=0; i<len-1-k; i++)
        {
            comp_count++;

            if(data[i] <= data[i+1])
            {
                continue;
            }
        
            swap(&data[i], &data[i+1]);
            done = false;
        }

        if(done)
            break;
        k++;
    }
}

int main(int argc, char **argv)
{
    srand(time(NULL));

    int i, data[100];
    for(i=0; i<100; ++i)
    {
        data[i] = rand() % 1000;
    }
    printf("随机序列: ");
    show(data, 100);

    bubbleSort(data, 100);  // 按升序排列
    printf("冒泡排序: ");
    show(data, 100);

    printf("总共比较次数: %d\n", comp_count);
    printf("总共交换次数: %d\n", swap_count);
    return 0;
}

5、代码分析

注意:

上述冒泡排序中,对算法做了优化,主要有两点:

  • 由于每一趟比较后,都至少有1个“极值”被移至末端,因此第i趟比较只需n−i次 对比次数优化
  • 当发现某一趟比较中全部为顺序时,则意味着序列已经有序,则可以提前退出 轮次优化


四、快速排序

1、概念

快排是一种递归思想的排序算法,先比较其他的排序算法,它需要更多内存空间,但快排的语句频度是最低的,理论上时间效率是最高的。

2、思路

在待排序序列中随便选取一个数据,作为所谓“支点”,然后所有其他的数据与之比较,以从小到大排序为例,那么比支点小的统统放在其左边,比支点大的统统放在其右边,全部比完之后,支点将位与两个序列的中间,这叫做一次划分。

一次划分之后,序列内部也许是无序的,但是序列与支点三者之间,形成了一种基本的有序状态,接下去使用相同的思路,递归地对左右两边的子序列进行排序,直到子序列的长度小于等于1为止。

3、示例代码

#include <stdio.h>

int comp_count = 0;
int swap_count = 0;

void show(int data[], int len)
{
    int i;
    for(i=0; i<len; ++i)
    {
        printf("%d\t", data[i]);
    }
    printf("\n");
}

void swap(int *a, int *b)
{
    swap_count++;

    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

int partition(int data[], int len)
{
    if(len <= 1)
        return 0;

    int i = 0;
    int j = len-1;
    while(i < j)
    {
        // 从右向左比较,顺序j--,逆序交换
        comp_count++;
        while(data[i]<=data[j] && i<j)
            j--;
        swap(&data[i], &data[j]);

        // 从左向右比较,顺序i++,逆序交换
        comp_count++;
        while(data[i]<=data[j] && i<j)
            i++;
        swap(&data[i], &data[j]);
    }

    return i;
}

void quickSort(int data[], int len)
{
    if(len <= 1)
        return;

    int pivot = partition(data, len);

    quickSort(data, pivot);
    quickSort(data+pivot+1, len-pivot-1);
}

int main(int argc, char **argv)
{
    srand(time(NULL));

    int i, data[100];
    for(i=0; i<100; ++i)
    {
        data[i] = rand() % 1000;
    }
    printf("随机序列: ");
    show(data, 100);

    printf("快速排序: ");
    quickSort(data, 100);
    show(data, 100);

    printf("总共比较次数: %d\n", comp_count);
    printf("总共交换次数: %d\n", swap_count);

    return 0;
}


五、希尔排序

1、比较插入排序和希尔排序

插入排序:

逐步的局部有序到全局有序

希尔排序:

从整体宏观上有序逐步细节到局部的有序

2、概念

希尔排序是一种改进版的插入排序,普通的插入排序算法中,是从第2个节点开始,依次插入到有序序列中,这种做法虽然“一次成形”,但研究发现时间效率上这么做并不划算,更“划算”的做法是这样的:不严格一个个插入使之有序,而是拉开插入节点的距离,让它们逐步有序

3、示例代码

#include <stdio.h>
#include <math.h>

int comp_count = 0;
int swap_count = 0;

void show(int data[], int len)
{
    int i;
    for(i=0; i<len; ++i)
    {
        printf("%d\t", data[i]);
    }

    printf("\n");
    return;
}

//                    起点    节点个数    间距
void insert_sort(int data[], int len, int delta)
{
    if(len <= 1)
        return;

    for(int i=delta; i<len*delta; i+=delta)
    {
        int j, tmp = data[i];
        for(j=i-delta; j>=0; j-=delta)
        {
            comp_count++;
            if(data[j] < tmp)
                break;

            swap_count++;
            data[j+delta] = data[j];
        }

        data[j+delta] = tmp;
    }
}

void shell_sort(int data[], int len)
{
    if(len <= 1)
        return;

    for(int delta=len/2; delta>0; delta/=2)
    {
        for(int i=0; i<delta; ++i)
        {
            //           起点     节点个数    间距
            insert_sort(data+i, len/delta, delta);
        }
    }
}

int main(void)
{
    // 准备产生一些随机数
    srand(time(NULL));

    int i, data[100];
    for(i=0; i<100; i++)
    {
        int exp = (int)pow(10, rand()%3+3);
        data[i] = rand()%exp;
    }
    printf("随机序列: ");
    show(data, 100);

    printf("希尔排序: ");
    shell_sort(data, 100);
    show(data, 100);

    printf("总共比较次数: %d\n", comp_count);
    printf("总共移动次数: %d\n", swap_count);

    return 0;
}


相关文章
|
8天前
|
机器学习/深度学习 存储 算法
【数据结构】算法的复杂度
算法的时间复杂度和空间复杂度
15 1
【数据结构】算法的复杂度
|
3天前
|
存储 算法 搜索推荐
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
【7月更文挑战第12天】归并排序是高效稳定的排序算法,采用分治策略。Python 实现包括递归地分割数组及合并已排序部分。示例代码展示了如何将 `[12, 11, 13, 5, 6]` 分割并归并成有序数组 `[5, 6, 11, 12, 13]`。虽然 $O(n log n)$ 时间复杂度优秀,但需额外空间,适合大规模数据排序。对于小规模数据,可考虑其他算法。**
13 4
|
2天前
|
存储 算法 Python
“解锁Python高级数据结构新姿势:图的表示与遍历,让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系,通过节点和边连接。常见的表示方法是邻接矩阵(适合稠密图)和邻接表(适合稀疏图)。图遍历包括DFS(深度优先搜索)和BFS(广度优先搜索):DFS深入探索分支,BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
9 1
|
7天前
|
算法 安全 调度
逆天改命!Python高级数据结构堆(Heap)与优先队列,让你的算法效率飙升至宇宙级!
【7月更文挑战第8天】Python的heapq模块和queue.PriorityQueue实现了堆和优先队列,提供高效算法解决方案。堆用于Dijkstra算法求解最短路径,例如在图论问题中;PriorityQueue则在多线程下载管理中确保高优先级任务优先执行。这两个数据结构提升效率,简化代码,是编程中的强大工具。
10 0
|
7天前
|
算法 搜索推荐 Java
在Java中实现高效的算法与数据结构
在Java中实现高效的算法与数据结构
|
16天前
|
存储 算法 调度
算法与数据结构-栈篇
算法与数据结构-栈篇
14 0
|
19天前
|
算法 C语言
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
|
14天前
|
存储 缓存 算法
堆和栈的区别及应用场景
堆和栈的区别及应用场景
|
20天前
|
存储 测试技术
【数据结构】操作受限的线性表,栈的具体实现
【数据结构】操作受限的线性表,栈的具体实现
27 5
|
19天前
|
算法 C语言
【数据结构与算法 经典例题】使用队列实现栈(图文详解)
【数据结构与算法 经典例题】使用队列实现栈(图文详解)