冒泡排序

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 Effervescence_sort(int len,int a[])
{
    int temp;
    for(int i=0;i<9;i++)
    {
        for(int j=9;j>i;j--)//找到较小数并依次向上冒泡
        {
            if(a[j]<a[j-1])
            {
                temp=a[j];
                a[j]=a[j-1];
                a[j-1]=temp;
            }
        }
    }
}
int main(int argc,char *argv[])
{
    int a[10];
    
    printf("Before sorting:");
    for(int i=0;i<10;i++)
    {
        scanf("%d",&a[i]);
    }
    Effervescence_sort(10,a);
    printf("After sorting:");
    for(int i=0;i<10;i++)
    {
        printf("%d\t",a[i]);
    }
    return 0;
}

图像演示：

选择排序

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 Chose_sort(int len,int a[])

{
    int min,i,j;
    
    for(j=0;j<len-1;j++)//找到最小数，将最小数按次序依次排列
    {
        for(i=j;i<len;i++)
        {
            min=a[j];
            if(min>a[i])
            {
                min=a[i];
                a[i]=a[j];
                a[j]=min;
            }
        }
    }
}
int main(int argc,char *argv[])
{
    int a[10],i;
    printf("Before sorting:");
    for(i=0;i<10;i++)
    {
        scanf("%d",&a[i]);
    }
    Chose_sort(10,a);
    printf("After sorting:");
    for(i=0;i<10;i++)
    printf("%d\t",a[i]);
    return 0;
}

图像演示：

插入排序

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 Insertion_sort(int len,int a[])
{
    int i,j,temp;
    for(i=1;i<len;i++)
    {
        temp=a[i];
        for(j=i;j>0;j--)
        {
            if(a[j-1]>temp)
            a[j]=a[j-1];
            else
            break;
            
        }
        a[j]=temp;
    }//若指定项的数值小于前面项，则循环项等于前一项，直到遇到循环项前一项小于指定项的数值，则循环项等于指定项数值
}
int main(int argc,char *argv[])
{
    int a[10],i;
    printf("Before sorting:");
    for(i=0;i<10;i++)
    {
        scanf("%d",&a[i]);
    }
    Insertion_sort(10,a);
    printf("After sorting:");
    for(i=0;i<10;i++)
    {
       printf("%d\t",a[i]);
    }
    return 0;
}

图像演示：

希尔排序

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
#include<stdio.h>
void shell_sort(int len,int arr[]) {
    int gap, i, j;
    int temp;
    for (gap = len >> 1; gap > 0; gap = gap >> 1)
        for (i = gap; i < len; i++) {
            temp = arr[i];
            for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                arr[j + gap] = arr[j];
            arr[j + gap] = temp;
        }
}//插入排序升级版，在插入排序前先分组排序，再进行插入排序，但不稳定
int main(int argc,int argv[])
{
    int a[10],i;
    printf("Before sorting:");
    for(i=0;i<10;i++)
    {
        scanf("%d",&a[i]);
    }
    shell_sort(a,10);
    printf("After sorting:");
    for(i=0;i<10;i++)
    printf("%d\t",a[i]);
    return 0;
}

图像演示：

归并排序

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
53
54
#include <stdio.h>
#include <stdlib.h>
int min(int x, int y)
{
    return x < y ? x : y;
}
void merge_sort(int arr[], int len)
{
    int *a = arr;
    int *b = (int *)malloc(len * sizeof(int));
    int seg, start;
    for (seg = 1; seg < len; seg += seg)
    {
        for (start = 0; start < len; start += seg + seg)
        {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        int *temp = a;
        a = b;
        b = temp;
    }
    if (a != arr)
    {
        int i;
        for (i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    free(b);
}

int main(int argc, int argv[])
{
    int a[10], i;
    printf("Before sorting:");
    for (i = 0; i < 10; i++)
    {
        scanf("%d", &a[i]);
    }
    merge_sort(a, 10);
    printf("After sorting:");
    for (i = 0; i < 10; i++)
        printf("%d\t", a[i]);
    return 0;
}

图像演示：

快速排序

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <stdio.h>

typedef struct _Range
{
    int start, end;
} Range;
Range new_Range(int s, int e)
{
    Range r;
    r.start = s;
    r.end = e;
    return r;
}
void swap(int *x, int *y)
{
    int t = *x;
    *x = *y;
    *y = t;
}
void quick_sort(int arr[], const int len)
{
    if (len <= 0)
        return; // 避免len等于负值時引发段错误（Segment Fault）
    // r[]模拟列表,p为数量,r[p++]为push,r[--p]为pop且取得元素
    Range r[len];
    int p = 0;
    r[p++] = new_Range(0, len - 1);
    while (p)
    {
        Range range = r[--p];
        if (range.start >= range.end)
            continue;
        int mid = arr[(range.start + range.end) / 2]; // 选取中间4点为基准点
        int left = range.start, right = range.end;
        do
        {
            while (arr[left] < mid)
                ++left; // 检测基准点左侧是否符合要求
            while (arr[right] > mid)
                --right; // 检测基准点右侧是否符合要求

            if (left <= right)
            {
                swap(&arr[left], &arr[right]);
                left++;
                right--; // 移动指针以继续
            }
        } while (left <= right);

        if (range.start < right)
            r[p++] = new_Range(range.start, right);
        if (range.end > left)
            r[p++] = new_Range(left, range.end);
    }
}

int main(int argc, int argv[])
{
    int a[10], i;
    printf("Before sorting:");
    for (i = 0; i < 10; i++)
    {
        scanf("%d", &a[i]);
    }
    quick_sort(a, 10);
    printf("After sorting:");
    for (i = 0; i < 10; i++)
        printf("%d\t", a[i]);
    return 0;
}

图像演示：