C语言排序

发表于 | 分类于
C语言排序

C语言排序

最近准备搞C++，就先熟悉一下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
#include<stdio.h>

void select_sort(int a[],int n);
//选择排序实现
void select_sort(int a[],int n)
{
    // 循环 0 ..< n-1，不包括最后一个数
    for(int i = 0; i< n-1;i++){
        // 循环 1 ..< n，不包括第一个数
        for (int j = i+1;j<n;j++){
            // 如果 i > j
            if (a[i]>a[j]){
                // 交换位置，小数的放到前面
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
}
int main(){
    int num[8] = {6,2,9,6,4,1,8,3};
    select_sort(num, 8);
    for(int i=0;i<8;i++){
        printf("%d\t",num[i]);
    }
    printf("\n");
    return 0;
}

冒泡排序

冒泡排序的基本思想就是不断比较相邻的两个数，让较大的元素不断地往后移。经过一轮比较，就选出最大的数；经过第2轮比较，就选出次大的数，以此类推。

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
#include <stdio.h>

void bubble_sort(int a[],int n);
void bubble_sort(int a[],int n)
{
    // 循环 0 ..< n-1，不包括最后一个数
    for(int i=0; i<n-1; i++)
    {
        // 循环 0..< n-1-i个，已排序好的最后i个不用比较
        for(int j=0; j<n-1-i; j++)
        {
            // 始终与下一个比较
            if(a[j] > a[j+1])
            {
                // 将较小的数，放前面
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1]=temp;
            }
        }
    }
}
int main(){
    int num[8] = {6,2,9,6,4,1,8,3};
    bubble_sort(num, 8);
    for(int i=0;i<8;i++){
        printf("%d\t",num[i]);
    }
    printf("\n");
    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
#include<stdio.h>

void insert_sort(int a[],int n);
//插入排序实现,这里按从小到大排序
void insert_sort(int a[],int n)
{
    // 循环 1 ..< n-1，不包括第一个数
    for(int i=1; i<n; i++)
    {
        //首先找到元素a[i]需要插入的位置
        int j=0;
        while( (a[j]<a[i]) && (j<i))
        {
            j++;
        }
        //将元素插入到正确的位置
        if(i != j)  //如果i==j，说明a[i]刚好在正确的位置
        {
            int temp = a[i];
            for(int k = i; k > j; k--)
            {
                a[k] = a[k-1];
            }
            a[j] = temp;
        }
    }
}
int main(){
    int num[8] = {6,2,9,6,4,1,8,3};
    insert_sort(num, 8);
    for(int i=0;i<8;i++){
        printf("%d\t",num[i]);
    }
    printf("\n");
    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
#include <stdio.h>
#include <stdlib.h>

int partition(int arr[], int low, int high){
    int key;
    key = arr[low];
    while(low<high){
        while(low <high && arr[high]>= key )
            high--;
        if(low<high)
            arr[low++] = arr[high];
        while( low<high && arr[low]<=key  )
            low++;
        if(low<high)
            arr[high--] = arr[low];
    }
    arr[low] = key;
    return low;
}
void quick_sort(int arr[], int start, int end){
    int pos;
    if (start<end){
        pos = partition(arr, start, end);
        quick_sort(arr,start,pos-1);
        quick_sort(arr,pos+1,end);
    }
    return;
}
int main(void){
    int i;
    int arr[6]={32,12,7, 78, 23,45};
    printf("排序前 \n");
    for(i=0;i<6;i++){
        printf("%d\t",arr[i]);
    }
    quick_sort(arr,0,6-1);
    printf("\n排序后 \n");
    for(i=0; i<6; i++){
        printf("%d\t", arr[i]);
    }
    printf ("\n");
    system("pause");
    return 0;
}

归并排序

归并排序也称合并排序，其算法思想是将待排序序列分为两部分，依次对分得的两个部分再次使用归并排序，之后再对其进行合并。仅从算法思想上了解归并排序会觉得很抽象，接下来就以对序列A[0], A[l]…, A[n-1]进行升序排列来进行讲解，在此采用自顶向下的实现方法，操作步骤如下。

  1. 将所要进行的排序序列分为左右两个部分，如果要进行排序的序列的起始元素下标为first，最后一个元素的下标为last，那么左右两部分之间的临界点下标mid=(first+last)/2，这两部分分别是A[first … mid]和A[mid+1 … last]。
  2. 将上面所分得的两部分序列继续按照步骤(1)继续进行划分，直到划分的区间长度为1。
  3. 将划分结束后的序列进行归并排序，排序方法为对所分的n个子序列进行两两合并，得到n/2或n/2+l个含有两个元素的子序列，再对得到的子序列进行合并，直至得到一个长度为n的有序序列为止。下面通过一段代码来看如何实现归并排序。
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
#include <stdio.h>
#include <stdlib.h>
#define N 7

void merge(int arr[], int low, int mid, int high){
    int i, k;
    int *tmp = (int *)malloc((high-low+1)*sizeof(int));
    //申请空间，使其大小为两个
    int left_low = low;
    int left_high = mid;
    int right_low = mid + 1;
    int right_high = high;
    for(k=0; left_low<=left_high && right_low<=right_high; k++){  // 比较两个指针所指向的元素
        if(arr[left_low]<=arr[right_low]){
            tmp[k] = arr[left_low++];
        }else{
            tmp[k] = arr[right_low++];
        }
    }
    if(left_low <= left_high){  //若第一个序列有剩余，直接复制出来粘到合并序列尾
        //memcpy(tmp+k, arr+left_low, (left_high-left_low+l)*sizeof(int));
        for(i=left_low;i<=left_high;i++)
            tmp[k++] = arr[i];
    }
    if(right_low <= right_high){
        //若第二个序列有剩余，直接复制出来粘到合并序列尾
        //memcpy(tmp+k, arr+right_low, (right_high-right_low+1)*sizeof(int));
        for(i=right_low; i<=right_high; i++)
            tmp[k++] = arr[i];
    }
    for(i=0; i<high-low+1; i++)
        arr[low+i] = tmp[i];
    free(tmp);
    return;
}
void merge_sort(int arr[], unsigned int first, unsigned int last){
    int mid = 0;
    if(first<last){
        mid = (first+last)/2; /* 注意防止溢出 */
        /*mid = first/2 + last/2;*/
        //mid = (first & last) + ((first ^ last) >> 1);
        merge_sort(arr, first, mid);
        merge_sort(arr, mid+1,last);
        merge(arr,first,mid,last);
    }
    return;
}
int main(){
    int i;
    int a[N]={32,12,56,78,76,45,36};
    printf ("排序前 \n");
    for(i=0;i<N;i++)
        printf("%d\t",a[i]);
    merge_sort(a,0,N-1);  // 排序
    printf ("\n 排序后 \n");
    for(i=0;i<N;i++)
        printf("%d\t",a[i]); printf("\n");
    system("pause");
    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
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

int ordersearch(int a[], int n, int des){
    int i;
    for(i=0; i<n; i++)
        if(des==a[i])
            return 1;
    return 0;
}
int main(){
    int i, val;
    int a[8] = {32,12,56,78,76,45,43,98};
    int ret;
    for(i=0; i<8; i++)
        printf("%d\t", a[i]);
    printf("\n请输入所要查找的元素：");
    while(1){
        scanf("%d", &val);
        fflush(stdin);
        ret = ordersearch(a, 8, val);
        if(1 == ret)
            printf ("查找成功！");
        else
            printf ("查找失败！");
        printf("\n请输入所要查找的元素：");
    }
    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
#include <stdio.h>

int binarySearch(int a[], int n, int key){
    int low = 0;
    int high = n - 1;
    while(low<= high){
        int mid = (low + high)/2;
        int midVal = a[mid];
        if(midVal<key)
            low = mid + 1;
        else if(midVal>key)
            high = mid - 1;
        else
            return mid;
    }
    return -1;
}
int main(){
    int i, val, ret;
    int a[8]={-32, 12, 16, 24, 36, 45, 59, 98};
    for(i=0; i<8; i++)
        printf("%d\t", a[i]);
    printf("\n请输人所要查找的元素：");
    scanf("%d",&val);
    ret = binarySearch(a,8,val);
    if(-1 == ret)
        printf("查找失败 \n");
    else
        printf ("查找成功 \n");
    return 0;
}

本文标题:C语言排序

文章作者:史彦超

发布时间:2016年10月11日 - 22:10

最后更新:2021年07月20日 - 16:07

原始链接:https://doingself.github.io/2016/10/11/2016-10-11-C%E8%AF%AD%E8%A8%80%E6%8E%92%E5%BA%8F/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

Donate comment here
分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多