文档章节

C 排序、查找

asjoker
 asjoker
发布于 2017/02/25 16:28
字数 2023
阅读 4
收藏 0
点赞 0
评论 0

#C语言排序 最近准备搞C++,就先熟悉一下C语言,看到排序算法就整理了一下

##选择排序

选择排序(从小到大)的基本思想是,首先,选出最小的数,放在第一个位置;然后,选出第二小的数,放在第二个位置,以此类推

#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轮比较,就选出次大的数,以此类推。

#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;
}

##插入排序

插入排序的基本思想是,将元素逐个添加到已经排序好的数组中去,同时要求,插入的元素必须在正确的位置,这样原来排序好的数组是仍然有序的。

#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;
}

##快速排序

快速排序算法 的基本思想是:将所要进行排序的数分为左右两个部分,其中一部分的所有数据都比另外一 部分的数据小,然后将所分得的两部分数据进行同样的划分,重复执行以上的划分操作,直 到所有要进行排序的数据变为有序为止。

#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的有序序列为止。下面通过一段代码来看如何实现归并排序。
#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;
}

##顺序查找

顺序査找是一种简单的査找算法,其实现方法是从序列的起始元素开始,逐个将序列中的元素与所要查找的元素进行比较,如果序列中有元素与所要查找的元素相等,那么査找成功,如果査找到序列的最后一个元素都不存在一个元素与所要査找的元素值相等,那么表明査找失败。

#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;
}

##二分查找

二分査找也称折半査找,其优点是查找速度快,缺点是要求所要査找的数据必须是有序序列。该算法的基本思想是将所要査找的序列的中间位置的数据与所要査找的元素进行比较,如果相等,则表示査找成功,否则将以该位置为基准将所要査找的序列分为左右两部分。接下来根据所要査找序列的升降序规律及中间元素与所查找元素的大小关系,来选择所要査找元素可能存在的那部分序列,对其采用同样的方法进行査找,直至能够确定所要查找的元素是否存在

#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;
}

© 著作权归作者所有

共有 人打赏支持
asjoker
粉丝 10
博文 108
码字总数 79411
作品 0
东城
程序员
深入JDK源码之Arrays类中的排序查找算法

二分法查找算法,算法思想:当数据量很大适宜采用该方法。采用二分法查找时,数据需是排好序的。 基本思想:假设数据是按升序排序的,对于给定值x,从序列的中间位置开始比较,如果当前位置值...

陶邦仁
2015/03/15
0
0
C语言/C++编程学习数据结构与算法 通俗易懂讲解 快速排序

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
03/20
0
0
怎么判断那种排序算法和查找算法更适用当前

排序和查找算法那麽多,但是那些方法更好? 那些方法更有优势? 自己应该主要掌握那几张算法 ? 或者自己当前的数据应该怎么排序或者查找? 今天我们来对应一个实际问题来搭配使用排序算法以...

KiTok
2017/11/07
0
0
Lintcode58 4Sum solution 题解

【题目描述】 Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target?Find all unique quadruplets in the array which gives the sum......

Winnielyn
06/26
0
0
linux基础命令(二)

echo 显示变量,如echo $LANG 变量设置,name=lv unset 取消变量 env和export 查看环境变量 set 查看所有变量 export variablename 将自定义变量variablename 变成环境变量 locale 显示结果的...

lvzhongjian
2016/04/29
57
0
MySQL InnoDB索引介绍及优化ZZ

正文: 一、先说说什么是索引?索引(index)翻译为一个目录,用于快速定位我们想要找的数据的位置。例如:我们把一个数据库比作一本书,而索引(index)就是书中的目录,此刻要找到书的某个感兴...

treenewtreenew
2016/12/20
9
0
Navicat 如何进行表单查看

Navicat 表单查看方便表单查看、更新或删除数据,显示当前的记录:栏位名及其值。表单的弹出菜单包括这些功能:设置栏位值为 Null 或空白字符串、使用当前栏位值为筛选、设置表单查看格式及更...

Navicat数据库管理工具
2016/04/28
396
0
mysql联合索引详解

联合索引又叫复合索引。对于复合索引:Mysql从左到右的使用索引中的字段,一个查询可以只使用索引中的一部份,但只能是最左侧部分。例如索引是key index (a,b,c). 可以支持a | a,b| a,b,c 3种...

mn_1127
2015/08/28
150
0
linux下grep分析web服务器日志

1.获得访问前10位的ip地址 cat access.log|awk '{print $1}'|sort|uniq -c|sort -nr|head -10 cat access.log|awk '{counts[$(11)]+=1}; END {for(url in counts) print counts[url], url}' ......

小报童
2013/02/17
0
3
联合索引详解

MySQL 联合索引详解 联合索引又叫复合索引。对于复合索引:Mysql从左到右的使用索引中的字段,一个查询可以只使用索引中的一部份,但只能是最左侧部分。例如索引是key index (a,b,c). 可以支持...

语博兄
2016/07/21
17
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

CoreText进阶(七)-添加自定义View和对其

CoreText进阶(七)-添加自定义View和对其 其它文章: CoreText 入门(一)-文本绘制 CoreText入门(二)-绘制图片 CoreText进阶(三)-事件处理 CoreText进阶(四)-文字行数限制和显示更多...

aron1992
8分钟前
0
0
Python爬虫 爬取百合网的女人们和男人们

学Python也有段时间了,目前学到了Python的类。个人感觉Python的类不应称之为类,而应称之为数据类型,只是数据类型而已!只是数据类型而已!只是数据类型而已!重要的事情说三篇。 据书上说...

p柯西
20分钟前
0
0
在Java中,你真的会日期转换吗

1.什么是SimpleDateFormat 在java doc对SimpleDateFormat的解释如下: SimpleDateFormatis a concrete class for formatting and parsing dates in a locale-sensitive manner. It allows fo......

Java小铺
28分钟前
0
0
Linux系统梳理---系统搭建(二):tomcat的安装和使用

上一章讲到JDK的安装使用,这一章主要记录下服务器tomcat的安装以及部署一个项目. 1.下载tomcat,这里下载的是apache-tomcat-8.5.32.tar.gz 2.创建文件夹,便于管理,和JDK一样,在usr目录下创建t...

勤奋的蚂蚁
39分钟前
0
0
ES15-聚合

1.Terms Aggregation 分组聚合 2.Filter Aggregation 过滤聚合

贾峰uk
40分钟前
0
0
【2018.07.19学习笔记】【linux高级知识 20.27-20.30】

20.27 分发系统介绍 20.28 expect脚本远程登录 20.29 expect脚本远程执行命令 20.30 expect脚本传递参数

lgsxp
43分钟前
0
0
10.32/10.33 rsync通过服务同步~10.35 screen工具

通过服务的方式同步要编辑配置文件:[root@linux-xl ~]# vim /etc/rsyncd.confport=873log file=/var/log/rsync.logpid file=/var/run/rsyncd.pidaddress=192.168.43.21[tes...

洗香香
46分钟前
0
0
与女儿谈商业模式 (3):沃尔玛的成功模式

分类:与女儿谈商业模式 | 标签: 经济学 沃尔玛 陈志武 2007-05-10 09:09阅读(11279)评论(30) 与女儿谈商业模式 (3):沃尔玛的成功模式 陈志武 /文 沃尔玛(Wal-Mart)是另一个有意思的财...

祖冲之
53分钟前
0
0
网页加载速度优化方法总结

1、减少请求 最大的性能漏洞就是一个页面需要发起几十个网络请求来获取诸如样式表、脚本或者图片这样的资源,这个在相对低带宽和高延迟的移动设备连接上来说影响更严重。 2、整合资源 对开发...

Jack088
58分钟前
0
0
dubbo学习

https://blog.csdn.net/houshaolin/article/details/76408399

喵五郎
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部