选择排序算法的思想是什么?
最新回答
鲜奶千层雪
2023-03-19 04:04:29
template<class Type>
int BinarySearch(Type a[],const Type& x,int n)
{
int left=0;
int right=n-1;
while(left<=right){
int middle=(left+right)/2;
if (x==a[middle]) return middle;
if (x>a[middle]) left=middle+1;
else right=middle-1;
}
return -1;
}
模板函数BinarySearch在a[0]<=a[1]<=...<=a[n-1]共n个升序排列的元素中搜索x,找到x时返回其在数组中的位置，否则返回-1。容易看出，每执行一次while循环，待搜索数组的大小减少一半,因此整个算法在最坏情况下的时间复杂度为O(log n)。在数据量很大的时候，它的线性查找在时间复杂度上的优劣一目了然。
选择排序
基本思想是：每次选出第i小的记录，放在第i个位置（i的起点是0，按此说法，第0小的记录实际上就是最小的，有点别扭，不管这么多了）。当i＝N－1时就排完了。
直接选择排序
直选排序简单的再现了选择排序的基本思想，第一次寻找最小元素的代价是O(n)，如果不做某种特殊处理，每次都使用最简单的寻找方法，自然的整个排序的时间复杂度就是O(n2)了。
冒泡法
为了在a[1]中得到最大值，我们将a[1]与它后面的元素a[2]，a[3]，...，a[10]进行比较。首先比较a[1]与a[2]，如果a[1]<a[2]，则将a[1]与a[2]交换，否则不交换。这样在a[1]中得到的是a[1]与a[2]中的大数。然后将a[1]与a[3]比较，如果a[1]<a[3]，则将a[1]与a[3]交换，否则不交换。这样在a[1]中得到的是a[1]，a[2]，a[3]中的最大值，...。如此继续，最后a[1]与a[10]比较，如果a[1]<a[10]，则将a[1]与a[10]交换，否则不交换。这样在a[1]中得到的数就是数组a的最大值（一共进行了9次比较）。
为了在a[2]中得到次大值，应将a[2]与它后面的元素a[3]，a[4]，...，a[10]进行比较。这样经过8次比较，在a[2]是将得到次大值。
如此继续，直到最后a[9]与a[10]比较，将大数放于a[9]，小数放于a[10]，全部排序到此结束。
从上面可以看出，对于10个数，需进行9趟比较，每一趟的比较次数是不一样的。第一趟需比较9次，第二趟比较8次，...，最后一趟比较1次。
以上数组元素的排序，用二重循环实现，外循环变量设为i，内循环变量设为j。外循环重复9次，内循环依次重复9，8，...，1次。每次进行比较的两个元素，第一个元素与外循环i有关的，用a[i]标识，第二个元素是与内循环j有关的，用a[j]标识，i的值依次为1,2,...,9，对于每一个i, j的值依次为i+1,i+2,...。
人不行不怪路不平
2024-03-16 06:08:11
假设记录集大小为n。排序过程需要经过若干趟操作，每一趟操作由若干次子操作组成。
算法思想：
选择类排序（包括简单选择排序、树形选择排序和堆排序等）的基本算法思想是执行第i趟操作时，从第i条记录后选择一条最小的记录和第i条记录交换。
初始状态： 49 38 65 97 76 13 27
第一趟： 从（38 65 97 76 13 27）中选择最小值13与49交换
13 38 65 97 76 49 27
第二趟： 从（65 97 76 49 27）中选择最小值27与38交换
13 27 65 97 76 49 38
... ...
热带的企鹅
2021-10-22 11:25:13
选择排序算法思想：
selectSort(array{n})
输入：B{n}//无序表
输出：A{n}//有序表
循环n次进行以下操作：
1: 无序表B{n}-B{i}中查找最大数位置max;
2: 更新无序表B{n}-B{i}; //交换B[i]～B[position]，待删除B[position];
3: 更新有序表A{i}中; //i++插入A{};
算法退出.
青春喂了作业
2022-11-06 06:27:31
http://hi.baidu.com/gsgaoshuang/blog/item/ca34d1dd4b0a49c98c102917.html
各种排序算法！
ヽ冷艳°皇后
2020-07-21 18:24:42
例 1,3,6,9,5 从小到大排序！
第一步 1
第二步 1,3
第三步 1,3,5
第四步 1,3,5,6
第五步 1,3,5,6,9
//递增选择排序的实现！
void SelectSort(double *head, int amount)
{
double temp;
int m,n;
for (m=0; m<amount-1; m++)
{
for (n=m+1; n<amount; n++)
{
if (head[n]<head[m])
{
temp=head[n];
head[n]=head[m];
head[m]=temp;
}
}
}
}
热门标签
