太原网站建设培训,华强北网站建设,网易做的什么网站,wordpress导航菜单代码前言#xff1a;
直接选择排序是排序中比较简单的排序#xff0c;同时也是时间复杂度不是很优的排序。
思想#xff1a;
本文主要讲解直接选择排序的优化版本。
我们经过一次遍历直接将该数列中最大的和最小的值挑选出来#xff0c;如果是升序#xff0c;就将最小的和…前言
直接选择排序是排序中比较简单的排序同时也是时间复杂度不是很优的排序。
思想
本文主要讲解直接选择排序的优化版本。
我们经过一次遍历直接将该数列中最大的和最小的值挑选出来如果是升序就将最小的和首元素进行交换最大的与尾元素进行交换。然后将首部元素尾部元素--重新遍历再次选择次大的和次小的。以此类推。
注意
按照上面的思路会遇到一些特殊情况造成排序的失败。
比如说我们先将最大的值赋给尾部元素如果最大的值正好在头部元素而最小的值恰好在尾部元素这样就导致把最大的元素赋给尾部元素时会把尾部本来的最小值覆盖掉造成排序的失败。
为了解决这种情况我们只需要将尾部元素提前存储好就欧克拉~
原码
void SelectSort(int* a, int n)
{int begin 0;int end n - 1;while (begin end){int maxi begin, mini begin;for (int i begin 1; i end 1; i){//找出最大值和最小值的下标if (a[i] a[maxi])maxi i;if (a[i] a[mini])mini i;}Swap(a[begin], a[mini]);//max如果被换走就修正以下if (maxi begin)maxi mini;Swap(a[end], a[maxi]);begin;end--;}
}时间复杂度 n n-2 n - 4 n - 6……
这也是一个等差数列所以时间复杂度就是O(N^2)。
显然这并不是一个优的排序算法。
