冒泡排序和选择排序的效率问题

Question

1.先看看我这个算不算选择排序，因为我写的这个会出现自己跟自己交换的时候2.我自己感觉选择排序和冒泡排序在面对倒序的数据时效率是一样的，其他时候选择排序效率稍好点。我的想法对吗？（别给我粘代码）
#include<iostream>
#include<iomanip>
using namespace std;
int main()
{
int str[11];
int i,j,k,t;
for(i=1;i<11;i++){cin>>str[i];}//输入10个数；
for(i=1;i<11;i++)//控制被比较数滑动
{
for(j=i+1;j<11;j++)//控制比较
{str[i]<str[j]?t=str[i],k=i:t=str[j],k=j;/*比较*/t=str[i];str[i]=str[k];str[k]=t;} //交换
}
for(int u=1;u<11;u++){cout<<str[u];}cout<<endl;
return 0;
}

Answer 1

选择排序总是会比冒泡排序效率高，因为选择排序每轮至多只交换1欢，但从算法角度考虑，时间复杂度并没有什么改进，因为都是O(n^2)算法！

追问

我这个算选择么

追答

应该是吧，冒泡排序遇到一个需要交换的就交换一次。
遇到比当前最大值(降序)大的,或比当前最小值小的升序就交换一次。

选择每次选一个最大值(降序)或最小值交换(升序)。
你这个明显是这么做的!

不过冒泡的改进算法效率也不低。就是记录交换次数的方法。

选择排序由于每次只交换一个，比简单的冒泡效率高。
但是你这个效率也不是很好！

好一点的选择排序，
只需要记录最大值(降序)或最小值交换(升序)的位置，
就行了,不要赋值这一步了。

另外C数组下标，都是从0开始计数的；
所以如无特殊需要。一般从0开始！
你这里11个字符只有1~10 是有用数据
第0个字符没有用到!
只有某些比较原始的,插入排序算法，才是从1开始的；0留出来另有用途(是叫哨兵吧!)。

由于你这里是字符数组,
所以算法上最好的,不一定就是最好的!

从算法来说,下面这样的小小改动是比较好的!
for(i=1;i<11;i++)//控制被比较数滑动, .......... 一共进行10轮比较。
{
k=i; //.......k就是最大值的下标，先假设最大值在i；
for(j=i+1;j<11;j++) //控制比较.............比较 10-i次;
if(str[k]<str[j])k=j; //改进的选择排序算法。这个是降序,选最大的,只有遇到更大的,才改变k!
if(k!=i) //i是最大值时不交换；在这里使用，提高不了多少效率，只是从算法上说更好些！
{ t=str[i];str[i]=str[k];str[k]=t; }//最大值从k,交换到i;这一步没什么花样!
}
更好的选择排序，是希尔排序（shellsort）或者叫歇尔排序,
最好的希尔排序,时间复杂度O（N^(4/3))；
这个就看数据结构和算法方面的书吧！
少了 k=i;//这一步，可是内循环里 多了这么多代码 str[i]<str[j]?t=str[i],k=i:t=str[j],k=j;
虽然用了？运算符可是，至少需要两个赋值操作。
这里数据尺寸较小不算什么，一旦数组中的数据尺寸较大就很不划算了！
k=i 就不同了，不管数据如何，只是一个整数赋值操作而已。
最好的内部排序算法好像是快速排序吧!
最好的外部排序算法是归并排序!

Answer 2

经典排序之冒泡排序