本文共 1824 字，大约阅读时间需要 6 分钟。

一、选择排序

void SelectSort(int* array, int size){    //size-1：每次都会排好一个数据，所以每次都需要进行-1    for (int i = 0; i < size - 1; i++)    {        //用maxPos标记最大的数据        int maxPos = 0;        //size-i：后面数据已经排好序了，直接不用管        for (int j = 0; j < size - i; j++)        {            //找最大的数据            if (array[j] > array[maxPos])                maxPos = j;        }            //如果最大的数据就是最后一个，就没有比较进行比较            if (maxPos != size - i - 1)                Swap(&array[maxPos], &array[size - i - 1]);    }}

二、选择排序优化

优化点：上述代码是一次找一个，这次我们同时找最大的和最小的，和对应的位置交换

void SelectSortOP(int* array, int size){    //定义这个就是减少范围来的，将已经排序好的直接去掉    int begin = 0;    int end = size - 1;    //标记最大或者最小的元素，以便于之后交换    int MaxPos = begin;    int MinPos = begin;    while (begin < end)    {        //index用于遍历数组        int index = begin + 1;        //标记最大最小的元素        while (index <= end)        {            if (array[MaxPos] < array[index])                MaxPos = index;            if (array[MinPos] > array[index])                MinPos = index;            ++index;        }        //交换        if (MinPos != left)            Swap(&array[MinPos], &array[left]);        if (MaxPos != end)            Swap(&array[MaxPos], &array[end]);        begin++;        end--;    }}

三、选择排序优化2

优化点：此时的代码还存在一点瑕疵，如果最小值在最后侧的话，那么交换的时候，MinPos会更新

void SelectSort_2(std::vector
   
     &arr){  int len = arr.size();  int left = 0;  int right = len - 1;  while(left < right)  {    int min_pos = left;    int max_pos = left;    for(int i = left; i <= right; ++i){      if(arr[min_pos] > arr[i]){        min_pos = i;      }      if(arr[max_pos] < arr[i]){        max_pos = i;      }    }    if(min_pos != left)      swap(arr[min_pos], arr[left]);    if(max_pos == left){      max_pos = min_pos;    }    if(max_pos != right)      swap(arr[max_pos], arr[right]);    ++left, --right;  }}
   

转载地址：http://xfacz.baihongyu.com/