八大排序算法之三选择排序—简单选择排序（Simple Selection Sort）

基本思想：

在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

简单选择排序的示例：

操作方法：

第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换；

第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换；

以此类推.....

第i 趟，则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换，

直到整个序列按关键码有序。

算法实现：（杭电ACM 1040）验证结果AC啦

#include<iostream>

using namespace std;

const int N =;

void sort(int a[],int num);

void print(int a[],int num);

void swap(int &a,int &b);

int main()

{

    int s[N];

    int T;

    cin>>T;

    while(T--)

    {

        int n;

        cin>>n;

        for(int j=;j<n;j++)

           cin>>s[j];

        sort(s,n);

        print(s,n);

        cout<<endl;

    }

    return ;

}

void sort(int a[],int num)//选择排序代码

{

    for(int i=;i<num;i++)

    {

           int k=i;

           for(int j=i+;j<num;j++)

           {

               if(a[k]>a[j])//从剩下的元素选择一个最小的元素

                 k=j;

        }

        if(k!=i)

        {

            swap(a[k],a[i]);//与最小的元素进行交换

        }

    }

}

void swap(int &a,int& b)//交换元素

{

    int temp;

    temp=a;

    a=b;

    b=temp;

}

void print(int a[],int n)//输出数组元素

{

    cout<<a[];

    for(int k=;k<n;k++)

    {

        cout<<" "<<a[k];

    }

}

简单选择排序，每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。具体实现如下：

#include<iostream>

using namespace std;

const int N =;

void SelectSort(int a[],int );

void print(int a[],int num);

void swap(int &a,int &b);

int main()

{

    int s[N];

    int T;

    cin>>T;

    while(T--)

    {

        int n;

        cin>>n;

        for(int j=;j<n;j++)

           cin>>s[j];

        SelectSort(s,n);

        print(s,n);

        cout<<endl;

    }

    return ;

}

void SelectSort(int arr[],int size)

{

    int minIndex, maxIndex;

    for (int i = ; i < size / ; i++) {

        minIndex = i;

        maxIndex = size-i-;

        for (int j = i; j < size - i ; j++) {

            if (arr[j] > arr[maxIndex]) {

                maxIndex = j;

                //continue;

            }

            if (arr[j] < arr[minIndex]) {

                minIndex = j;

            }

        }

        if (maxIndex == i && minIndex == size - i - ) {

            //特殊交换位置一，当最大的交换位置和最小的交换位置都在最前面和最后面

            swap(arr[maxIndex],arr[minIndex]);

        }

        else if (maxIndex == i) {

                //特殊交换位置二，当最大的交换位置是最前面

                // Swap(arr[n - i], arr[maxIndex])

                swap(arr[size-i-],arr[maxIndex]);

                swap(arr[i], arr[minIndex]);

            }

            else if (minIndex == size - i - ) {

                    //特殊交换位置三，当最小的交换位置是最后面

                    swap(arr[i], arr[minIndex]);

                    swap(arr[size - i-], arr[maxIndex]);

                }

                else {

                    //除了上面三种特殊交换，就剩普通交换了，普通交换随便哪个先交换都行

                    swap(arr[i], arr[minIndex]);

                    swap(arr[size - i-], arr[maxIndex]) ;

                }

    }

}

void swap(int &a,int& b)//交换元素

{

    int temp;

    temp=a;

    a=b;

    b=temp;

}

void print(int a[],int n)//输出数组元素

{

    cout<<a[];

    for(int k=;k<n;k++)

    {

        cout<<" "<<a[k];

    }

}

巴特西

八大排序算法之三选择排序—简单选择排序（Simple Selection Sort）

最新文章

热门文章