本文共 608 字,大约阅读时间需要 2 分钟。
选择排序和冒泡排序的思想比较像。冒泡排序的最里层循环结束后,最大的元素会“沉”到序列的最下面。我们是通过一次次的比较大小然后进行交换的方式实现的。那如果我们先找到整个序列最大的元素,然后直接将其放在序列的最后面(或者是先找到最小的元素,然后将其放在序列的最前面),也可以实现排序的目的。
所以我们就得到了选择排序算法的核心思想
1.首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。 2.再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。 3.重复第二步,直到所有元素均排序完毕。用代码来实现上面的三个步骤
void select_sort(int arr[], int len){ int i, j; for (i = 0; i < len - 1; i++) { int min = i; for (j = i + 1; j < len; j++) //扫描未排序的元素 if (arr[j] < arr[min]) //找到目前最小值 min = j; //记录最小值的下标 swap(&arr[min], &arr[i]); //做交换 } return;}
复杂度分析
很显然,时间复杂度为O(n^2),空间复杂度为O(1)
同样,这个排序算法并不适合大批量元素进行排序
转载地址:http://wyali.baihongyu.com/