Using brute force to solve selection sorting problems

The brute force method is a simple and direct way to solve a problem, often based directly on the description of the problem and the definition of the concepts involved.

Selection sorting idea:

At the beginning of selection sort, scan the entire list to find the smallest element, then exchange it with the first element, and put the smallest element at its final position in the ordered list. Then we scan the list starting from the second element, find the minimum value of the last (n-1) elements, swap it with the second element, and put the second smallest element at its final position in the list. Generally speaking, when scanning the list for the i-th time (the value of i ranges from 0 to n-2), the algorithm looks for the smallest element among the last (n-i) elements, and then exchanges it with Ai, in ( After n-1) passes, the list is sorted.

The following is my code implementation: C

#include 
using namespace std;
int main()
{
    int i,j,temp,minn,N;
    cin>>N;
    int *Arr=new int[N];
    for(i=0;i<n cin>>Arr[i];
 
    for(i=0;iArr[j])
                minn=j;//记录最小值的下标
        }
        temp=Arr[minn];     //交换Arr[minn]和Arr[i]。
        Arr[minn]=Arr[i];
        Arr[i]=temp;
    }
 
    for(i=0;i<n cout return>
<div style="margin-top: 2em; margin-bottom: 1em;"><span style="color: #1e1e1e; letter-spacing: 2px; border-left: #FF3030 3px solid; border-right: #FF3030 3px solid; padding-left: 8px; padding-right: 8px; font-size: 12pt;"><strong>Analysis of Algorithms:</strong></span></div>
<p>The size of the input is determined by the number of elements n. The basic operation is key value comparison Arr[minn]>Arr[j]. The number of times this comparison is performed depends only on the size of the array,</p>
<p>C(n)=∑[i=0,i=N-2] ∑[j=i 1,j=N-1]=∑[i=0,i=N-2] ((N- 1)-(i 1) 1))=∑[i=0,i=N-2](N-i-1)=(n-1)*n/2</p>
<p>That is, for any input, selection sorting is an algorithm with a time complexity of Θ(n2). The number of key exchanges is Θ(n) <i>This makes the selection sort performance better. </i></p></n></n>

The above is the detailed content of Using brute force to solve selection sorting problems. For more information, please follow other related articles on the PHP Chinese website!