插入排序

一、概念及其介绍

插入排序(InsertionSort)，一般也被称为直接插入排序。

对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增 1 的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

二、适用说明

插入排序的平均时间复杂度也是 O(n^2)，空间复杂度为常数阶 O(1)，具体时间复杂度和数组的有序性也是有关联的。

插入排序中，当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较 N-1 次，时间复杂度为 O(N)。最坏的情况是待排序数组是逆序的，此时需要比较次数最多，最坏的情况是 O(n^2)。

三、过程图示

假设前面 n-1(其中 n>=2)个数已经是排好顺序的，现将第 n 个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。

按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。

从小到大的插入排序整个过程如图示：

第一轮：从第二位置的 6 开始比较，比前面 7 小，交换位置。

img

第二轮：第三位置的 9 比前一位置的 7 大，无需交换位置。

img

第三轮：第四位置的 3 比前一位置的 9 小交换位置，依次往前比较。

img

第四轮：第五位置的 1 比前一位置的 9 小，交换位置，再依次往前比较。

img

就这样依次比较到最后一个元素。

四、C语言代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>

int main() {
    int num[8]={7,6,9,3,1,5,2,4};
    int temp=1; //定义交换中间变量
    for(int i=0;i<8;i++){
        for(int p=i;p>0;p--){
            if(num[p]<num[p-1]){//判定是否小于前一个数
                temp=num[p];
                num[p]=num[p-1];
                num[p-1]=temp;//若小于，则两数交换
            }
            else break;
        }
    }
    for(int q=0;q<8;q++){
        printf("%d ",num[q]);//输出数组
    }
}

希尔排序

一、概念及其介绍

希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。

希尔排序又称缩小增量排序，因 DL.Shell 于 1959 年提出而得名。

它通过比较相距一定间隔的元素来进行，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。

二、适用说明

希尔排序时间复杂度是 O(n^(1.3-2))，空间复杂度为常数阶 O(1)。希尔排序没有时间复杂度为 O(n(logn)) 的快速排序算法快 ，因此对中等大小规模表现良好，但对规模非常大的数据排序不是最优选择，总之比一般 O(n^2 ) 复杂度的算法快得多。

三、过程图示

希尔排序目的为了加快速度改进了插入排序，交换不相邻的元素对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。

在此我们选择增量 gap=length/2，缩小增量以 gap = gap/2 的方式，用序列 {n/2,(n/2)/2…1} 来表示。

如图示例：

（1）初始增量第一趟 gap = length/2 = 4

img

（2）第二趟，增量缩小为 2

img

（3）第三趟，增量缩小为 1,得到最终排序结果

​ img

四、C语言代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#define lenth 8
int main() {
    int num[lenth]={7,6,9,3,1,5,2,4};
    int gap,j;//定义增量，循环变量
    for(gap=lenth/2;gap>0;gap/=2){
        for(int i=gap;i<lenth;i++){//外层循环，gap每次缩小1/2
            int temp=num[i];//将数组元素赋值给中间值
            for(j=i;j>=gap&&temp<num[j-gap];j-=gap){
                num[j]=num[j-gap];
            }
            num[j]=temp;//判定若小于，两元素交换
        }
    }
    for(int q=0;q<8;q++){
        printf("%d ",num[q]);
    }
}

选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

1. 算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

2. 动图演示

img

3.代码实现

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define n 5

void init(int a[]) {
    srand(time(0));
    int i;
    for (i = 0; i < n; ++i) {
        a[i] = rand() % 101;
    }
}//初始化随机数组

void print(int a[]) {
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}//数组输出函数


void swap(int *a,int *b) //交换两数
{
      int temp = *a;
      *a = *b;
      *b = temp;
}
void choose(int arr[], int len)
{
      int i,j;

        for (i = 0 ; i < len - 1 ; i++)
      {
                int min = i;
                for (j = i + 1; j < len; j++)   //走访未排序的元素
                    if (arr[j] < arr[min])  //找到目前最小值
                        min = j;  //记录最小值
                swap(&arr[min], &arr[i]);  //做交換
            }
}
int main() {
    int a[n];
    init(a);
    printf("Original array:\n");
    print(a);
    choose(a,n);
    printf("Sorted array:\n");
    print(a);
    return 0;
}

冒泡排序

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

  • 作为最简单的排序算法之一，冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。

1. 算法步骤

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

2. 动图演示

img

3. 什么时候最快

当输入的数据已经是正序时（都已经是正序了，我还要你冒泡排序有何用啊）。

4. 什么时候最慢

当输入的数据是反序时（写一个 for 循环反序输出数据不就行了，干嘛要用冒泡排序呢，我是闲的吗）。

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define n 5

void init(int a[]) {
    srand(time(0));
    int i;
    for (i = 0; i < n; ++i) {
        a[i] = rand() % 101;
    }
}//初始化随机数组

void print(int a[]) {
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}//数组输出函数

void gudu(int a[]) {
    int swapped; // 用于标记是否发生交换
    for (int i = n - 1; i > 0; i--) {
        swapped = 0; // 每轮开始前重置为0
        for (int p = 0; p < i; p++) {
            if (a[p] > a[p + 1]) {
                int temp = a[p];
                a[p] = a[p + 1];
                a[p + 1] = temp;
                swapped = 1; // 发生交换
            }
        }
        if (!swapped) {
            // 如果没有发生交换，说明已经排序完成
            break;
        }
    }
}

int main() {
    int a[n];
    init(a);
    printf("Original array:\n");
    print(a);
    gudu(a);
    printf("Sorted array:\n");
    print(a);
    return 0;
}