当前位置：首页 > 算法 > 正文内容

【排序】----选择排序

亿万年的星光4年前 (2021-01-28)算法1482

1.基本思想

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在待排序的数列最前，直到全部待排序的数据排完。

2.过程

首先初始化最小元素索引值为首元素。依次遍历待排序数列，遇到小于该最小索引位置处的元素则刷新最小索引为该较小元素的位置。

直至遇到尾元素，结束一次遍历，并将最小索引处元素与首元素交换。

·初始化最小索引值为第二个待排序数列元素位置，同样的操作，可得到数列第二个元素即为次小元素；以此类推。

着重在于“选”

动图演示：

#include<iostream>
using namespace std;
int main()
{
     int arr[]={12,45,13,88,79,11,52,66}; //定义数组
     int len =sizeof(arr) / sizeof(arr[0]); //测量数组长度 
 
     for(int i=0;i<len;i++) // i控制当前序列最小值存放的位置， 
     {
         int index=i;  //首先记录下当前最小位置，假设index位置处元素是最小值 
         for(int j=i+1;j<len;j++) //从 
         {
            if (arr[j]<arr[index])  //每次找到数组中最小的一个值， 
                index=j;   //找到了，把下标赋值给index 
        }
        if(index!=i) //如果index和i不相同 
        {
            int temp = arr[i];
            arr[i] =arr[index];
            arr[index]=temp; //交换arr[i]和a[index],将当前最小值放到arr[i]位置。 
        }
        
        /*
        for(int i=0;i<len;i++)
        {
            cout<<arr[i]<<" ";
        }
        cout<<endl;
        */
     }
     return 0; 
}

3.问题及改进

上面的算法思想是一次确定一个有序去的值（最小值），改进的方法可以一次确定两个值（一个最小值和一个最大值），这样可以提高效率。（部分代码）

#include<iostream>
using namespace std;
int main() {
    int arr[]= {12,45,13,88,79,11,52,66}; //定义数组
    int len =sizeof(arr) / sizeof(arr[0]); //测量数组长度
    int left = 0;
    int right = len - 1;
    while (left < right) {
        int max = left;//记录无序区最大元素下标
        int min = left;//记录无序区最小元素下标
        int j = 0;
        for (j = left + 1; j <= right; j++) {
            //找最大元素下标
            if (arr[j] < arr[min]) {
                min = j;
            }
            //找最小元素下标
            if (arr[j]>arr[max]) {
                max = j;
            }
        }
        //最小值如果是第一个则没有必要交换
        if (min != left) {
            int tmp = arr[left];
            arr[left] = arr[min];
            arr[min] = tmp;
        }
        //这里很重要，如果最大元素下标是left,前面已经和最小元素交换了，此时最大元素下标应该是min
        if (max == left) {
            max = min;
        }
        //最大值如果是最后一个则没必要交换
        if (max != right) {
            int tmp = arr[right];
            arr[right] = arr[max];
            arr[max] = tmp;
        }
        left++;
        right--;
    }
    return 0; 
}