八大排序算法实现与讲解

发表于 | 分类于 | 评论数：

摘要：八大排序的C和Python实现，缓慢更新中…学到哪更新到哪（脑袋瓜笨啊~）

冒泡排序

冒泡排序作为C语言for循环讲解的启蒙例子，相信大家对他都很熟悉

主要思路：

  1. 比较相邻的元素，根据规则选择是否交换这两个数
  2. 从开始第一对到结尾最后一对
  3. 针对多个元素重复以上操作（除了最后一个）
  • 时间复杂度：平均O(n^2) 最好：O(n)
  • 空间复杂度：O(1)
  • 稳定性：稳定

C：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void bubble_sort(int *arr,int len)
{
    int i,j,tmp;
    int swap = 1;
    for(i = 0; i< len-1;i++)
    {
        for(j = 0; j< len -1 -i; j++)
            if(arr[j] > arr[j+1])
            {
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
                swap = 0;
            }
        if(swap)	//如果没进行交换直接退出
            return;
    }
}

Python:

1
2
3
4
5
6
7
8
9
10
11
def bubble_sort(arr:[int])-> [int]:
    swap = True
    for i in range(0,len(arr)-1):
        for j in range(0,len(arr)-1-i):
            if arr[j] > arr[j+1]:
                arr[j],arr[j+1] = arr[j+1],arr[j]
                swap = False
        if swap:
            return arr

    return arr

简单选择排序

主要思路：每趟从待排序的记录中选出关键字最小的记录，顺序放在已排序的记录序列末尾，直到全部排序结束为止。

  • 时间复杂度：O(n^2)
  • 空间复杂度：O(1)
  • 稳定性：不稳定

C:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void select_sort(int *arr,int len)
{
    int i,j,tmp;
    int min;
    for(i = 0;i<len;i++)
    {
        min = i;
        for(j=i + 1;j<len;j++)
            if(arr[j] < arr[min])
                min = j;
        tmp = arr[i];
        arr[i]=arr[min];
        arr[min] = tmp;
    }
}

Python:

1
2
3
4
5
6
7
8
def select_sort(arr:[int])-> [int]:
    for i in range(0,len(arr)):
        min_index = i
        for j in range(i+1,len(arr)):
            if arr[min_index] > arr[j]:
                min_index = j
        arr[min_index],arr[i] = arr[i],arr[min_index]
    return arr

插入排序

主要思路：每一趟将一个待排序的记录，按照其关键字的大小插入到有序队列的合适位置里，直到全部插入完成。

  • 时间复杂度：平均:O(n^2) 最好:O(n)
  • 空间复杂度：O(1)
  • 稳定性：稳定

C:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void insert_sort(int *arr,int len)
{
    int i,j;
    int tmp = 0;
    for(i = 1;i< len;i++)
    {
        tmp  = arr[i];
        for(j = i-1;j>=0;j--)
            if(arr[j] > tmp)
                arr[j+1] = arr[j];
            else
                break;
        arr[j+1] = tmp;

    }
}

Python:

1
2
3
4
5
6
7
8
9
10
def insert_sort(arr:[int])-> [int]:
    for i in range(1,len(arr)):
        tmp = arr[i]
        for j in range(i-1,-1,-1):
            if arr[j] > tmp:
                arr[j+1] = arr[j]
            else:
                break
        arr[j+1] = tmp
    return arr

希尔排序

希尔(Shell)排序又称为缩小增量排序，它是一种插入排序。它是直接插入排序算法的一种改进版。希尔排序的比较次数和移动次数都要比直接插入排序少，当N越大时，效果越明显。

算法思想：

我们举个例子来描述算法流程（以下摘自维基百科）：

假设有这样一组数 {13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10}，如果我们以步长为 5 开始进行排序：

排序前 排序后
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10		 10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

将上述四行数字，依序接在一起时我们得到：{10, 14, 73, 25, 23, 13, 27, 94, 33, 39, 25, 59, 94, 65, 82, 45}，然后再以 3 为步长：

排序前 排序后
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45		 10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

最后以 1 为步长进行排序（此时就是简单的插入排序了）。

可想而知，步长的选择是希尔排序的重要部分。算法最开始以一定的步长进行排序，然后会继续以更小的步长进行排序，最终算法以步长为 1 进行排序。当步长为 1 时，算法变为直接插入排序，这就保证了数据一定会被全部排序。

  • 时间复杂度：平均:O(nlogn) 最坏:O(n^2)
  • 空间复杂度：O(1)
  • 稳定性：不稳定

C:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void shell_sort(int *arr,int len,int gap)
{
    int tmp;
    int i,j;
    for(i = gap; i<len; i = i+gap)
    {
        tmp = arr[i];
        for(j = i -gap;j>=0;j=j-gap)
            if(arr[j] > tmp)
                arr[j+gap] = arr[j];
            else
                break;
        arr[j+gap] = tmp;
    }
}

void Shell(int *arr,int len)
{
    int gap[] = {5,3,1};    //可以分为步长的一半，这里就自定义好了
    int len_gap = sizeof(gap)/sizeof(gap[0]);
    for(int i=0;i<len_gap;++i)
        shell_sort(arr,len,gap[i]);
}

Python:

1
2
3
4
5
6
7
8
9
10
11
def shell_sort(arr:[int])->[int]:
    g = [5,3,1]
    for gap in g:
        for i in range(gap,len(arr)):
            tmp = arr[i]
            j = i-gap
            while j>=0 and arr[j] > tmp:
                arr[j+gap] = arr[j]
                j = j - gap
            arr[j+gap] = tmp
    return arr

快速排序

快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分：分割点左边都是比它小的数，右边都是比它大的数。

  • 时间复杂度：平均:O(nlogn) 最坏:O(n^2)
  • 空间复杂度：O(logn)
  • 稳定性：不稳定

然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

C:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int division(int *arr,int left,int right)
{
    //每次取基准数为最左边的那个数
    int base = arr[left];
    while(left<right)
    {
        //从右端开始，向左寻找，找到小于基准数的值时将元素放最左边
        while(left<right && arr[right] >= base)
            --right;
        arr[left] = arr[right];
        //同理，当找到时转为左边开始向右找，将大于基准数的值放元素右边
        while(left<right && arr[left] <= base)
            ++left;
        arr[right] = arr[left];
    }
    // 最后将base放到left位置。此时，left位置的左侧数值应该都比left小；
    // 而left位置的右侧数值应该都比left大
    arr[left] = base;
    return left;
}

void quick_sort(int *arr,int left,int right)
{
    //左下标要小于右下标，否则会越界
    if( left < right)
    {
        //按照基准数对数组进行分割
        int base = division(arr,left,right);
        //分别对左右两边进行递归
        quick_sort(arr,left,base-1);
        quick_sort(arr,base+1,right);
    }
}

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def quick_sort(arr:[int],left:int,right:int)->[int]:
    def division(arr:[int],left:int,right:int):
        base = arr[left]
        while left < right:
            while left < right and arr[right] >= base:
                right -= 1
            arr[left] = arr[right]
            while left < right and arr[left] <= base:
                left += 1
            arr[right] = arr[left]
        arr[left] = base
        return left

    if(left<right):
        base = division(arr,left,right)
        quick_sort(arr,left,base-1)
        quick_sort(arr,base+1,right)
    return arr

堆排序

堆排序是一种选择排序。

堆是一棵顺序存储的完全二叉树。

  • 其中每个结点的关键字都不大于其孩子结点的关键字，这样的堆称为小根堆。
  • 其中每个结点的关键字都不小于其孩子结点的关键字，这样的堆称为大**根堆**。

举例来说，对于n个元素的序列{R0, R1, … , Rn}当且仅当满足下列关系之一时，称之为堆：

  • Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)
  • Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)

其中i=1,2,…,n/2向下取整；

  • 时间复杂度：O(nlogn)
  • 空间复杂度：O(1)
  • 稳定性：不稳定

归并排序

该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。

  • 时间复杂度：O(nlog2n)
  • 空间复杂度：O(n)
  • 稳定性：稳定

基数排序

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

算法步骤：

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

基数排序的方式可以采用 LSD（Least significant digital）或 MSD（Most significant digital），LSD 的排序方式由键值的最右边开始，而 MSD 则相反，由键值的最左边开始。

不妨通过一个具体的实例来展示一下基数排序是如何进行的。 设有一个初始序列为: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}。

我们知道，任何一个阿拉伯数，它的各个位数上的基数都是以 09 来表示的，所以我们不妨把 09 视为 10 个桶。

我们先根据序列的个位数的数字来进行分类，将其分到指定的桶中。例如：R[0] = 50，个位数上是 0，将这个数存入编号为 0 的桶中。

分类后，我们在从各个桶中，将这些数按照从编号 0 到编号 9 的顺序依次将所有数取出来。这时，得到的序列就是个位数上呈递增趋势的序列。

按照个位数排序： {50, 30, 0, 100, 11, 2, 123, 543, 187, 49}。

接下来，可以对十位数、百位数也按照这种方法进行排序，最后就能得到排序完成的序列。

  • 时间复杂度：O(dn)
  • 空间复杂度：O(n)
  • 稳定性：稳定

相关文章
-------　本文结束　　感谢您的阅读　-------