文档章节

C 排序、查找

asjoker
 asjoker
发布于 2017/02/25 16:28
字数 2023
阅读 4
收藏 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
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
怎么判断那种排序算法和查找算法更适用当前

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

KiTok
2017/11/07
0
0
linux基础命令(二)

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

lvzhongjian
2016/04/29
57
0

没有更多内容

加载失败,请刷新页面

加载更多

HBase 表修复在线方式和离线方式

一、在线修复 1.1 使用检查命令 $ ./bin/hbase hbck 该命令可完整修复 HBase 元数据信息;存在有错误信息会进行输出; 也可以通过如下命令查看详细信息: $ ./bin/hbase hbck -details 1.2 ...

Ryan-瑞恩
10分钟前
0
0
redis 系列二 -- 常用命令

1.基础命令 info ping quit save dbsize select flushdb flushall 2.键命令 2.1 set 直接赋值 set a a 2.2 get 取值 get a 2.3 exists 是否存在 exists a 2.4 expire 设置剩余时间 秒 expire......

imbiao
42分钟前
1
0
php foreach

<?php// 数组的引用$a=array(1,2,3,4,5);foreach($a as $key=>&$value){$value=$value*2;}print_r($a);echo " $key -------------------$value\r\n";/** * ...

小张525
50分钟前
1
0
12-利用思维导图梳理JavaSE-多线程

12-利用思维导图梳理JavaSE-多线程 主要内容 1.线程概念 2.线程开发 3.线程的状态 4.线程的同步和死锁 5.Java5.0并发库类 QQ/知识星球/个人WeChat/公众号二维码 本文为原创文章,如果对你有一...

飞鱼说编程
今天
0
0
JAVA集合之ArrayList

一、前言 Java 集合类提供了一套设计良好的支持对一组对象进行操作的接口和类,JAVA常用的集合接口有4类,分别是: Collection:代表一组对象,每一个对象都是它的子元素 Set:不包含重复元素...

木木匠
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部