Zmyu's Blog

0%

插入排序、直接选择（简单）排序、冒泡排序、希尔排序、快速排序

发表于
本文字数： 6.1k 阅读时长 ≈ 51 分钟
文章时效性提示

本文发布于 468 天前，部分信息可能已经改变，请注意甄别。

参考：

  1. bilibili：直接选择排序、冒泡排序、希尔排序、快速排序手推步骤
  2. bilibili：五分钟学会希尔排序【中英字幕】
  3. bilibili：插入排序（直接插入、希尔排序）算法思想

插入排序

插入排序就是在之前排好的有序表中找到合适位置插入。

例如一个乱序的数组：
{51,28,38,86,70,90,7,30,40,86,25}

  1. 第一个是51，此时还没有有序表，51作为有序表中的第一个。
  2. 28小于51，排在51前边{28,51}
  3. 38大于28小于51，排在28和51中间。{28,38,51}
  4. 86大于51，排在最后{28,38,51,86}
    …
    直到排序完成。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
void Sort(int arr[],int sz);
int main()
{
    int arr[] = {51,28,28,86,-70,90,7,28,40,86,25};
    int sz = sizeof(arr)/sizeof(arr[0]);
    Sort(arr,sz);
    return 0;
}
void Sort(int arr[],int sz)
{
    int i;
    for (int i = 1; i < sz; i++) {
           int key = arr[i];
           int j = i - 1;
           // 找到 key 的插入位置
           while (j >= 0 && arr[j] > key) {
               arr[j + 1] = arr[j];
               j--;
           }
           arr[j + 1] = key; // 插入 key
       }
}

直接选择（简单）排序

例如一个数组：
{51,28,38,86,70,90,7,30,40,86,25}
先找到这个数组中最小的数字，也就是7，把它和第一个数字，51交换位置，数组变成了：
{(7),28,38,86,70,90,51,30,40,86,25}
再从这个数组的第二个数字开始寻找最小的数字，也就是25，和第二个数字28交换位置：
{(7,25),38,86,70,90,51,30,40,86,28}
…
直到排序完成。

代码

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
#include <stdio.h>
void Sort(int arr[],int sz);
int main()
{
    int arr[] = {51,28,28,86,-70,90,7,28,40,86,25};
    int sz = sizeof(arr)/sizeof(arr[0]);
    Sort(arr,sz);
    return 0;
}
void Sort(int arr[],int sz)
{
    int i = 0;
    int j = 0;
    for (j=0; j<sz; j++)
    {
        int minValue = arr[j];
        int minIndex = j;
        for (i=j+1; i<sz; i++)//找到最小的数字
        {
            if (arr[i] < minValue)
            {
                minValue = arr[i];//更新最小的数字
                minIndex = i;//最小数字的位置
            }
        }
        if (minIndex != j)//只在必要时交换元素
        {
            int temp = arr[j];
            arr[j] = minValue;
            arr[minIndex] = temp;
        }
    }
}

冒泡排序

假设一个数组：
{51,28,38,86,70,90,7,30,40,86,25}
51先与28进行比较，51>28，数组变成
{28,51,38,86,70,90,7,30,40,86,25}
51再与38比较，51>38，数组变成
{28,38,51,86,70,90,7,30,40,86,25}
…
直至第一轮排序完成，数组变为：
{28,38,51,70,86,7,30,40,86,25,(90)}
可以看到，经过了第一轮排序，把最大的数字移到数组的末尾，之后不会再对这个数字进行排序。

再次进行第二轮冒泡排序：
{28,38,51,70,86,7,30,40,86,25,(90)}
28与38比较，28<38，数组不变。
38再与51比较，38<51，数组不变。
…
86与7比较，86>7，数组改为：
{28,38,51,70,7,86,30,40,86,25,(90)}
86与30比较，数组变成：
{28,38,51,70,7,30,86,40,86,25,(90)}
86与40比较，数组变成：
{28,38,51,70,7,30,40,86,86,25,(90)}
下次比较时，86与86相等，顺序不变，然后86再与25比较：
{28,38,51,70,7,30,40,86,25,86,(90)}
经过第二轮冒泡排序，数组变成：
{28,38,51,70,7,30,40,86,25,(86,90)}
下次再排序时，后两位不会再修改。
…
直到排序完毕。

代码

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
#include <stdio.h>
void Sort(int arr[],int sz);
int main()
{
    int arr[] = {51,28,28,86,-70,90,7,28,40,86,25};
    int sz = sizeof(arr)/sizeof(arr[0]);
    Sort(arr,sz);
    return 0;
}
void Sort(int arr[],int sz)
{
    int i = 0;
    int j = 0;
    int swapped;//发生交换标记
    for (j=0; j<sz-1; j++)//趟数
    {
        swapped = 0; // 标记这一趟是否有交换
        for (i=0; i<sz-j-1; i++)//一趟冒泡排序
        {
            if (arr[i] > arr[i+1])
            {
                int temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
                swapped = 1; // 有交换发生
            }
        }
        // 如果没有交换，提前结束
        if (!swapped)
        {
            break;
        }
    }
}

希尔排序

希尔排序首先需要一个步长，这个步长不是固定的，根据实际情况调整。
在这里我们取步长为d=(5,3,1)。
假设一个数组：
{51,28,38,86,70,90,7,30,40,86,25}
步长为5，即51和90为一组，28和7为一组，38和30为一组，86和40为一组，70和86为一组，25单独为一组，本次不对其排序。
进行第一趟排序，不同组进行分别比较：

  1. 51<90，这组顺序不改变
  2. 28>7，把28和7调换位置
  3. 38>30，调换位置
  4. 86>40，调换位置
  5. 70<86，不变
  6. 25单独一组，不变
    进行第一趟排序后，数组变为：
    {51,7,30,40,70,90,28,38,86,86,25}

再以步长为3，在第一次排序后的基础上，进行第二趟希尔排序：
{51,7,30,40,70,90,28,38,86,86,25}
51和40为一组，7和70为一组，30和90为一组，28和86为一组，38和25为一组，倒数第三个数86单独一组。

  1. 51>40，调换位置
  2. 7<70，不变
  3. 30<90，不变
  4. 28<86，不变
  5. 38>25，调换位置
  6. 86单独一组，位置不变
    按照上面进行第二趟希尔排序：
    {40,7,30,51,70,90,28,25,86,86,38}

再以步长为1，进行第三趟希尔排序：

  1. 40先和7比较，调换位置
    {7,40,30,51,70,90,28,25,86,86,38}
  2. 40和30比较，调换位置
    {7,30,40,51,70,90,28,25,86,86,38}
  3. 40和51比较，不变
  4. 51和70比较，不变
  5. 70和90比较，不变，90和28比较，调换位置

代码

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
#include <stdio.h>
void Sort(int arr[],int sz);
int main()
{
    int arr[] = {51,28,28,86,-70,90,7,28,40,86,25};
    int sz = sizeof(arr)/sizeof(arr[0]);
    Sort(arr,sz);
    return 0;
}
void Sort(int arr[],int sz)
{
    int gap,i,j,temp;
    for (gap = sz / 2; gap > 0; gap = gap / 2)//先定义步长
    {
        for (i = gap; i < sz; i++)//元素间移动位置
        {
            for (j = i - gap; j>=0 && arr[j]>arr[j+gap]; j = j - gap)//比较各相距离gap个位置的元素
            {
                temp = arr[j];//更换位置
                arr[j] = arr[j+gap];
                arr[j+gap] = temp;
            }
        }
    }
}

快速排序

先选出一个节点（取有意义的，或者取第一个），把这个节点放在一个数组的中间，把要排序的数字中小于它的放在它的左侧，右侧都是大于它的数字，最后对两边的数字进行排序。
假设一个数组
{51,28,38,86,70,90,7,30,40,86,25}
选取数组中第一个数字作为节点P，最左边为L指针，最右边为R指针。

512838867090730408625
⬆️P
⬆️L⬆️R

P节点在最左边，要先从最右边的R指针开始比较，由于25<51，把25放在左边。⬇️

512838867090730408625
⬆️P
⬆️L⬆️R
25

接下来L指针右移，由于28<51，把28放在左边，L指针右移。⬇️

512838867090730408625
⬆️P
⬆️L⬆️R
2528

L指针指向的38<51，把38放在左边，L指针右移。⬇️

512838867090730408625
⬆️P
⬆️L⬆️R
252838

L指针指向的86>51，86去R指针所在位置，接下来左移R指针。⬇️

512838867090730408625
⬆️P
⬆️L⬆️R
25283886

R指针指向的86>51，86放在右边，R指针左移。⬇️

512838867090730408625
⬆️P
⬆️L⬆️R
2528388686

R指针指向的40<51，40移动到L指针所在的位置，接下来右移L指针。⬇️

512838867090730408625
⬆️P
⬆️L⬆️R
252838408686

L指针指向的70>51，70移动到R指针所在的位置，接来下左移R指针。⬇️

512838867090730408625
⬆️P
⬆️L⬆️R
25283840708686

R指针指向的30<51，30移动到L指针所在的位置，接下来右移L指针。⬇️

512838867090730408625
⬆️P
⬆️L⬆️R
2528384030708686

L指针指向的90>51，90移动到R指针所在位置，接下来左移R指针。⬇️

512838867090730408625
⬆️P
⬆️L⬆️R
252838403090708686

R指针指向的7<51，7移动到L指针位置，接下来右移L指针，L和R指针汇合，把P指针（51）移动到这里。⬇️

512838867090730408625
⬆️R⬆️L
252838403075190708686
⬆️P

接下来把P指针左侧和右侧作为两个单独的数组，再次排序，直到数组有序。

代码

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
#include <stdio.h>
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为基准
    int i = (low - 1); // 小于基准的元素索引
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]); // 交换
        }
    }
    swap(&arr[i + 1], &arr[high]); // 将基准放到正确位置
    return (i + 1);
}
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high); // 找到基准元素的索引
        quickSort(arr, low, pi - 1);  // 对基准左侧进行排序
        quickSort(arr, pi + 1, high); // 对基准右侧进行排序
    }
}
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
int main() {
    int arr[] = {51, 28, 38, 86, 70, 90, 7, 30, 40, 86, 25};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("原数组: ");
    printArray(arr, n);
    quickSort(arr, 0, n - 1);
    printf("排序后数组: ");
    printArray(arr, n);
    return 0;
}