经典算法学习（一）排序之选择排序与插入排序

算法即内功

选择排序

选择排序是一种就地排序。选择排序适用数据量小的时候。排序是基于关键量。在迭代的时候与关键量进行比较，在需要交换的时候再交换。
优点：

• 易于实现。（很简单，正常思路排序）
• 就地排序，不需要额外的存储空间。

缺点：

• 扩展性不是很好：O（n^2）

算法：
1.选择最小（大）值放在第一个位置。
2.选择剩下元素的最小（大）值放在第二个位置。
3.就这样一直选择，直到最后。

void selectSort(int a[],int n){int i,j,min,index;for(i=0;i<n-1;i++){min=a[i];index=i;for(j=i+1;j<n;j++){if(min>a[j])index=j;}a[i]=a[j];a[j]=min;}
}

时间复杂度：O（n^2）

插入排序

插入排序是一种比较简单有序的比较排序。在这个算法中，每次迭代都会从数据中删除一个元素，并将其插入有序列中该元素该位于的位置上。从输入数据中随机选择被删除的元素，重复上述过程直到所有输入元素均已插入有序序列中。
优点：

• 简单的实现。
• 对于规模不大的输入数据而言，该算法是高效的。
• 自适应算法：若列表基本有序的情况下，时间复杂度为O（n+d），d是逆序次数。
• 比冒泡排序，选择排序高效。

算法：

void insertSort(int a[],int n){int i,j,temp;for(i=1;i<n;i++){temp=a[i];j=i;while(a[j-1]>temp&&j>=0){a[j]=a[j-1];j--;}a[j]=v;}
}

插入排序要优于前两种排序，因为在基本有序的输入时，插入排序几乎是线性的。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！