大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
上面文章讲完了插入排序和交换排序,本次我们来讨论选择排序。
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法(比如序列[5, 5, 3]第一次就将第一个[5]与[3]交换,导致第一个5挪动到第二个5后面)。
1、普通(单个)选择排序
每遍历一次,记录下最值元素所在位置,遍历结束后,将此最值元素调整到合适的位置。这样一次遍历,只需一次交换,便可将最值放置到合适位置
//成功返回0,失败返回-1 int select_sort(int *arr,const int n) { //判断参数是否正确 if(NULL == arr || 0 >= n) return -1; int i = 0; //循环使用 int j = 0; //循环使用 int k = -1; //记录比较的下标 int temp; //交换时作中间值 //每次循环只进行一次交换 最多进行n - 1次循环,因此总体上,比冒泡进行交换的次数少 for(i = 0; i < n - 1; i++) { //第i次排序时,已经进行了i次大循环,因此已经排好了i个元素 //已排好序的元素0,,...,i-2,i-1 //待排元素为i,i+1,...,n-1 k = i; //拿i的位置值与后面的值相比较 for(j = i + 1; j < n; i++) { if(arr[k] < arr[j]) k = j; } //判断k值是否有变化,有变量就交换 if(k != i) { temp = arr[k]; arr[k] = arr[i]; arr[i] = temp; } } return 0; }
2、二分选择排序
int select_sort(int *arr, const int n) { //判断参数是否正确 if(NULL == arr || 0 >= n) return -1; int i = 0; int j = 0; int minpos = -1; int maxpos = -1; int temp; //每次循环完进行二次交换 最多进行n/2次循环,因此总体上,比冒普通选择排序的次数少 for(i = 0; i < n / 2; i++) { minpos = i; maxpos = i; for(j = i + 1; j < n; j++) { if(arr[j] > arr[maxpos]) { maxpos = j; continue; } if(arr[j] < arr[minpos]) { minpos = j; } } temp = arr[i]; arr[i] = arr[minpos]; arr[minpos] = temp; if(maxpos == i) { temp = arr[minpos]; arr[minpos] = arr[n - 1 - i]; arr[n - 1 - i] = temp; } else { temp = arr[maxpos]; arr[maxpos] = arr[n - 1 - i]; arr[n - 1 -i] = temp; } } return 0; }
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。