Bubble sort, quick sort

One . Bubble sort

1 The basic idea ： Compare two adjacent numbers , Exchange according to rules .

2. Realize the idea ：

（ Take ascending order as an example ） The first comparison ： First compare the first and second elements , Switch the larger one to the second position , Then compare the second and third , Put the larger one in the third position ... By analogy , At the end of the first comparison , The largest element is in the last position Then make a second comparison ： First compare the first and second elements , Switch the larger one to the second position , Then compare the second and third , Put the larger one in the third position ... By analogy , Because the first comparison has put the largest in the last position So we can compare one element less in the second trip , At the end of the second trip , The second largest element is placed in the penultimate position By analogy , Until the last comparison is completed , The entire array is sorted . （ On the last trip , There is only one element left , Can not participate in the comparison ）

3. Realize dynamic graph

 4 Code implementation

#include <stdio.h>

 int main(int argc, const char *argv[])
{
    int s[10] = {23,45,65,78,90,55,33,17,96,54};
    int i = 0;
    int j = 0;
    int temp = 0;
    int flags=0;// This is set to improve efficiency 
    int len = sizeof(s)/sizeof(int);

    for(i = 0; i < len; i++){
    printf("%d ", s[i]);
    }

    printf("\n");

    for(j = 0; j < len-1; j++){
        flags=0;
        for(i = 0; i < len-1-j; i++){
            if(s[i] > s[i+1]){
                temp = s[i];
                s[i] = s[i+1];
                s[i+1] = temp;
                flags=1;
            }
        }
        if(flags==0){
             break;
         }        
    }

    for(i = 0; i < len; i++){
        printf("%d ", s[i]);
    }

    printf("\n");

    return 0;
 }

Two . Quick sort

 1 Concept

Quick sort is the optimization of bubble sort , It is also a sort method based on Exchange .

Time complexity O(nlogn).

2 The basic idea

Divide and rule through a sequence , First, divide the data into two parts , Part of the data , Are larger than the data of another part ( Small ),（ Every part of the data is not required to be orderly ） then , Perform the above sorting operations for the two parts of data , Divide the data into two parts , By analogy , Until the whole data is in order .

3 Realize dynamic graph

 

4 Code implementation

#include <stdio.h>
#include <unistd.h>

int sort(int *num,int low,int high)
{
    int flag=num[low];

    while(low<high){
        while(num[high]>flag&&low<high){
            high--;
        }

        if(low<high){
            num[low]=num[high];
        }

        while(num[low]<flag&&low<high){
            low++;
        }

        if(low<high){
            num[high]=num[low];
            high--;
        }
    }

    num[low]=flag;

    return low;
}

int quick_sort(int *num,int low,int high)
{
    if(low<high){
        int ret=sort(num,low,high);
        quick_sort(num,0,ret-1);
        quick_sort(num,ret+1,high);
    }
}


int show_num(int *num)
{
    for(int i=0;i<10;i++){
        printf("%d ",num[i]);
    }

    puts("");
}


int main(int argc, char const *argv[])
{
    int num[10]={3,4,12,65,31,52,34,76,6,10};

    show_num(num);

    quick_sort(num,0,9);

    show_num(num);
    return 0;
}