Learn how to use selection sort and bubble sort in three minutes

Today I will share with you some algorithms about C language, Selection sort and bubble sort.

For selection sorting, first understand the idea of ​​sorting. Given an array, this idea first assumes that the first element of the array is the largest or smallest. At this time, three variables will be used to represent the subscripts of the elements.

One represents the current one, one represents the largest or smallest subscript found, and one is used to store the subscript of the maximum value in each cycle. After mastering the basic idea of ​​the program, proceed with sequencing. After finding the largest subscript, assign it to the largest subscript except each time.

After finding it, determine whether the assumed current value is the maximum value of this cycle. If not, exchange the maximum and current values, thereby arranging the array in a certain order, and finally write a loop to output the result. .

The code is not difficult, so I will explain it step by step. I just attach the code. If you don’t understand, you can leave me a message and I will explain it to you. Or if there is anything wrong, I can correct it.

#include<stdio.h>
void main()//主函数
{
   int a[10];
   int i,j,w;
   printf("请输入10个数字： \n");
    for(i=0;i<10;i++)
   scanf("%d",&a[i]);
    for(i=0;i<10;i++)
{
     for(j=0;j<10;j++)
     if(a[i]<a[j])//进行比较
//比较后进行交换
{
  w=a[i];
         a[i]=a[j];
           a[j]=w;
}
  }
printf("排序后:\n");
        for(i=0;i<10;i++)
            printf("%4d",a[i]);
              printf("\n");
}

Result display:

Next is Bubble sort, this is the most popular in C language One of the most commonly used algorithms, because it is easier to understand, it is the first thing most people use when they want to sort. This algorithm is relatively easy to understand.

For bubble sorting, the main idea is to compare adjacent numbers in pairs. If the latter one is larger or smaller than the previous one, swap its positions until all numbers are compared.

If an array of size n is given, n-1 comparisons are required, and each comparison is n-1-i times. i represents the subscript that has been compared in the last loop. Write two loop judgments. If exchange is needed, exchange it. If exchange is not required, compare the next two numbers until all numbers are compared.

Finally, use a loop to output all the sorted numbers. The code is as follows:

#include<stdio.h>
#define N 10
void main()
{
   int a[10];
   int i,j,t;
   printf("请输入10个数字： \n");
    for(i=0;i<10;i++)
   scanf("%d",&a[i]);
//使用两层循环
    for(i=0;i<N-1;i++)
{
     for(j=i+1;j<N-(i+1);j++)
     if(a[j]<a[j+1])//比较大小
{
  t=a[j];
         a[j]=a[j+1];
           a[j+1]=t;
}
}
printf("排序后:\n");
        for(i=0;i<10;i++)
            printf("%4d",a[i]);
              printf("\n");
}

Result:

##Conclusion:

For selection The analysis of sorting is very simple. The size of the input is determined by the array elements. The basic operation is the key value comparison A[j]Therefore, for any input, selection sort is an O(n^2) algorithm. Therefore, the time complexity of this experiment is O(100) and the space complexity is O(10). However, the number of times the keys are exchanged is only O(n), or to be more precise, n-1 times (one exchange is performed for each iteration of the i loop).

This feature makes selection sort superior to many other sorting algorithms.

Bubble sorting is a process in which two adjacent numbers are compared, and the larger number sinks to the bottom (or the smaller number floats up). A total of n-1 comparisons and exchanges are performed.

In order to facilitate the implementation of the above bubble algorithm, consider using only a one-dimensional array to store 10 integer data. During the sorting process, the data is always in this array (operated in place and does not occupy additional space). Therefore, the time complexity of this algorithm is O(n-1) and the space complexity is O(1).

Thank you everyone for reading, I hope you will benefit a lot.

This article is reproduced from: https://blog.csdn.net/zjy18886018024/article/details/80718713

Recommended tutorial: "

C Language"

The above is the detailed content of Learn how to use selection sort and bubble sort in three minutes. For more information, please follow other related articles on the PHP Chinese website!