冒泡排序
核心思想:类似水泡一样,一趟比较,通过相邻元素的交换,冒出当前序列的最小值(最大值)到相应位置复杂度分析
最好的情况:序列本身有序,只要进行n-1次比较,无需交换,时间复杂度为O(n)最差情况: 序列逆序,此时需要比较1+2+3+...(n-1)=n(n-1)/2次,并进行等数量级的交换辅助空间:O(1)综上,总的时间复杂度为O(n^2)
稳定性:稳定
void bubbleSort(int arr[],int n){//冒泡排序 int flag=true;for(int i=0;i<n-1&&flag;i++){//flag作为标记,若有序,则不用瞎比较 flag=false;for(int j=n-1;j>=i;j--){//i+j=n-1if(arr[j]<arr[j-1]){swap(arr,j,j-1);flag=true; }}}}
简单选择排序
核心思想:每一趟树立一个数作为靶子,谁比他小,就作为新靶子和剩下的比,最后的靶子就是这一趟最小的值了,然后除去这个数,再剩下的序列中重复此步骤即可复杂度分析
比起冒泡,最大特点就是:交换移动数据相当少不管最好最差情况下,比较的次数都是一样多,而交换次数则有差别第i趟排序要进行n-i次关键字比较,比较次数为:n-1+n-2+...+1=n(n-1)/2次交换次数:
最好的情况(有序):0次最差情况(逆序):n-1次辅助空间:O(1)最终时间复杂度为:O(n^2)
稳定性:稳定
性能比冒泡好点
代码如下
#include <iostream>void swap(int *&arr,int i,int j){int temp=arr[i];arr[i]=arr[j];arr[j]=temp;} void simpleSort(int *arr,int n){//简单选择排序,在n-i+1个记录中选出最小关键字 int i,j,min;for(i=0;i<n;i++){//这里用i<n,当i=n-1时,j的条件不符,不会进入下一个for循环 min=i;for(j=i+1;j<n;j++){if(arr[min]>arr[j]){//这里必须要用arr[min],不能用arr[i] min=j;}}if(min!=i){swap(arr,i,min);}}}void print(int *arr,int n){for(int i=0;i<n;i++){printf("%d ",arr[i]);}}int main(int argc, char** argv) {int arr[]={4,82,56,12,43,61,14};simpleSort(arr,7);print(arr,7);return 0;}
直接插入排序
核心思想:类似我们斗地主抓牌,第一张摸到直接放手里,第2张开始就要考虑手里的若干张牌的排列顺序了,第2张若比第1张小,则要把第2张放在第1张前面,现有的牌排好序后再抓第3张牌,然后依次比较第3张和第2张,第1张的大小关系,来决定第3张该摆在哪,依次类推,直到把抓到的最后一张牌排好序复杂度分析最好的情况(有序):0次移动,比较n-1次,时间复杂度为:O(n)最差(逆序):比较次数为:1+2+3+...+n-1=(n+2)(n-1)/2,移动次数也达到最大:(n+4)(n-1)/2次若排序记录随机,平均比较和移动次数约为:n^2/4辅助空间:O(1)总的复杂度为:O(n^2)稳定性:`稳定性能比冒泡和简单选择排序好点`
代码如下
#include <iostream>void swap(int *&arr,int i,int j){int temp=arr[i];arr[i]=arr[j];arr[j]=temp;}void InsertSort(int *arr,int n){//直接插入排序 int i,j;for(i=1;i<n;i++){//跟摸牌一样,摸到一张就和抓到手的牌比较,然后整理j=i;while(j>0&&arr[j]<arr[j-1]){//摸到的第一张和第0张比大小,排好序 swap(arr,j,j-1);//摸到第2张和第1张比大小,第1张和第0张比 j--;//摸到第3张和第2张比大小,第2张和第1张比大小,第1张和第0张比大小}}}void print(int *arr,int n){for(int i=0;i<n;i++){printf("%d ",arr[i]);}}int main(int argc, char** argv) {int arr[]={12,4,56,8,10,9,41};InsertSort(arr,7);print(arr,7); return 0;}
注:本文所用图片均来自dreamcatcher-cx大神文章
