Sorting - selection, bubbling

Search - sequential, binary search

1. Select Sorting

Starting from the first number, find the maximum value by comparing with the following numbers each time, put the maximum value in the current position, and the value of the number in the current position in the position of the maximum value, and cycle successively until it reaches the last number.

Example: input a positive integer n (1 < n < = 9), input n positive numbers, sort them from small to large by selection method, and then output.

#include<stdio.h>
#define MAXN 10
int main()
{
    int i,index,k,n,temp;
    int a[MAXN];
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    //yes n Number sorting 
    for(k=0;k<n-1;k++){
        index=k;                //index Used to store the subscript of the minimum value 
        for(i=k+1;i<n;i++){     //Find minimum subscript 
            if(a[i]<a[index]) index=i;
        }
        temp=a[index];            //Minimum and a[k] Element exchange,Change the minimum value to the current position, and put the number of the current position on the original position of the minimum value
        a[index]=a[k];
        a[i]=temp;
    }
    //Output sorted array
    for(i=1;i<n;i++){
        printf("%d",a[i]);
    } 
    printf("\n");
    return 0;
 } 

 

 

2. Bubble sorting

Carry out multiple cycles, and compare two adjacent numbers each time. In ascending order, put the large number behind.   Like bubbles, larger numbers sink and smaller numbers rise.

Example:

#include <stdio.h>
int main(void)
{
    int a[1001];
    int n,i,j,t;
    scanf("%d",&n);//n Number of to sort
    //Enter the number to sort
    for(i=0;i<n;++i)
        scanf("%d",a+i);
 
    //Next, sort
    for(i=0;i<n-1;++i)//n number,A total of n-1 second
    {                 //n-1 The number is finished,The first number must have returned
        //Each time the maximum(Ascending order)Or minimum(Descending order)Put it at the back
        for(j=0;j<n-i-1;++j)
        {
            if(a[j]>a[j+1])//Every bubble,Exchange
            {
                t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
            }
        }
        for(j=0;j<n;++j)
            printf("%-5d ",a[j]);
        printf("\n\n");
    }
 
    return 0;
}

　　

Optimization: in the sorting process, after the final sorting, although the data has been sorted completely, the program cannot judge whether the sorting is completed. In order to solve this problem, set a flag bit flag and set its initial value to non-0, indicating that the sorted table is an unordered table. Set the flag value to 0 before each sorting. During data exchange, Modify the flag to be non-0. Check this flag at the beginning of a new round of sorting. If this flag is 1, it means that no data exchange has been done last time, indicating that it is orderly; if the sequence has become orderly during the sorting process, it will not bubble, otherwise it will be sorted.

  The code is as follows:

for(i=0;i<n-1;++i)//n number,A total of n-1 second
{                 //n-1 The number is finished,The first number must have returned
    //Each time the maximum(Ascending order)Or minimum(Descending order)Put it at the back
    int f=1;//Set a switch variable here
    for(j=0;j<n-i-1;++j)
    {
        if(a[j]>a[j+1])
        {
            t=a[j];
            a[j]=a[j+1];
            a[j+1]=t;
            f=0;
        }
    }
    if(1==f)//f 1 indicates that bubbling has not been carried out,Description sequence order
        break;//If the sequence is ordered,Then you can jump out of sorting
}

 

1. Sequential search

Sequential search refers to searching one by one from beginning to end.

Example code:

#include<stdio.h>
int main()
{
    int n,x,flag,i;
    int a[10];
    scanf("%d%d",&n,&x);
    for( i=0;i<n;i++){
        scanf("%d",&a[i]);
    } 
    //lookup
    flag=0;                                //set up flag Make a sign 
    for(i=0;i<n;i++){
        if(a[i]==x){
            printf("Idex is %d\n",i);    //find x，Then the subscript is output 
            flag=1;                        //Set flag A value of 1 indicates that it is found x 
        }
    } 
    if(flag==0){
        printf("No Found");                //flag Is 0, indicating that it was not found x 
    }
    return 0;
}

 

2. Binary search

The table as a binary lookup object must be an ordered table stored sequentially. The lookup process is to first take the midpoint element A[mid] (mid = (0 + n -1) / 2) of the entire ordered table A[0] ~ A[n - 1] If the keyword of is equal to the given value K, the search is successful. If K is small, the same operation is performed on the remaining left half. If K is large, the same operation is performed on the remaining right half.

There are two kinds: non recursive and recursive

Code 1: non recursive function part

int Binary_search(int low,int high,int n)
{
    int mid;
    while(low<=high){
        mid=(low+high)/2;
        if(n==a[mid]){
            breajk;
        }else if(n<a[mid]){
            high=mid-1;
        }else if(n>a[mid]){
            low=mid+1;
        }
    }
    if(low<=high) return mid;    //Returns the subscript of the lookup number
    else return -1;                    //Can't find

Code 2: recursive function part

int Binary_search_recursive(int *s,int length,int key,int L,int H)
{
    int  M=(L+H)/2;
    if(L>H)
        return -1;　　　　//Can't find
    if(key<s[M])
    {
        return (Binary_search_recursive(s,length,key,L,M-1));
    }
    else if(key>s[M])
    {
        return (Binary_search_recursive(s,length,key,M+1,H));
    }
    else
        return (M);　　　　//M is the number of lookups
}

  Advantages: fewer cycles and higher program efficiency.