2排序算法及分析

冒泡排序

从小到大排

1步骤：
从小到大排，每一趟排序 两两比较并交换以保证左小右大 实现最大的数再每趟排序的最末尾
2演示：

3. 什么时候最快
   当输入的数据已经是正序时 。遍历一遍发现没有交换就可以。O(N)

4. 什么时候最慢
   当输入的数据是反序时（写一个 for 循环反序输出数据不就行了，干嘛要用你冒泡排序呢，我是闲的吗）。O(N^2)
   5代码实现

#include void bubble(int arr[],int n)
{int t;for(int i=0;i<n-1;i++){//i+1if(arr[i]>arr[i+1]){t=arr[i];arr[i]=arr[i+1];arr[i+1]=t;}}
} 
void bubblesort(int arr[],int n)
{//每次代排序的个数是从n 一直到最后1个for(int i=n;i>=1;i--){bubble(arr,i);} 
}
int main(){int arr[]={6,5,7,1,23,8,3,2,9}; bubblesort(arr,9);for(int i=0;i<9;i++){printf("%d ",arr[i]);}return 0;
}

选择排序

1步骤：找到当前的最大值，每趟排序都是找到当前待排序列的max，然后和当前最后一位交换，待排序列个数也是从n——1个
2演示：

3,4 最好最坏都是O(N^2) 因为都需要遍历每个待排序列找max

5代码实现

#include int findmaxpos(int arr[],int n)
{int pos=0;int max=arr[0];for (int i=0;i<n;i++){if(arr[i]>max){max=arr[i];pos=i;}} return pos;
} 
void selectsort(int arr[],int n)
{for(int j=n;j>=1;j--){int pos=findmaxpos(arr,j);int t=arr[pos];arr[pos]=arr[j-1];arr[j-1]=t;}}
int main(){int arr[]={6,5,7,1,23,8,3,2,9}; selectsort(arr,9);for(int i=0;i<9;i++){printf("%d ",arr[i]);}return 0;
}

插入排序

1步骤
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。

前面是有序序列，从小到大排序 ，对于某个arr[i] 令key=arr[i] ， 不断比较arr[i]之前的数（arr[i-1]开始 i-- ），与key的大小， 并将arr[i-1]向后移动，直到当前值不比key大 将key插入i所指的位置。待排的长度是n-1到1

2演示

3最快 ：正序不比较 key比其之前所有值都大 key位置不动 一次遍历 O(N)
4最慢：逆序 小的数要一个个往前插入 两层遍历O(N^2)
5代码实现

#include void insert(int arr[],int n)
{//将一个数 插入有序的数组中 int key=arr[n];int i=n;while(arr[i-1]>key&&i>0){//i-1>=0arr[i]=arr[i-1];i--;} //说明找到key该放的位置arr[i]=key; } 
void insertsort(int arr[],int n)
{for(int i=1;i<n;i++){//第0元素默认有序//依次插入1-n-1的元素到前面的有序数组中insert(arr,i); }}
int main(){int arr[]={6,5,7,1,23,8,3,2,9}; insertsort(arr,9);for(int i=0;i<9;i++){printf("%d ",arr[i]);}return 0;
}

归并排序

1步骤：
算法是采用分治法，自上而下的递归，两段有序序列

• 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

  设定两个指针，最初位置分别为两个已经排序序列的起始位置；

  比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

  重复步骤 3 直到某一指针达到序列尾；

  将另一序列剩下的所有元素直接复制到合并序列尾。

简单来说，

• 就是对两个有序序列sort，用双指针
• 但是如果左右两个序列不是有序，则一直递归用mergesort变成有序后merge
• 出口 ，不断平分左右两边序列，直到剩一个数字的时候，

2 merge演示
mergesort演示

3代码实现

#include void merge(int arr[],int L,int M,int R)
{int sizeL=M-L;int sizeR=R-M+1;int size=R-L+1;int left[sizeL];int right[sizeR];for(int i=L;i<M;i++){left[i-L]=arr[i];}for(int i=M;i<=R;i++){right[i-M]=arr[i];}int i=0,j=0,k=L;while(i<sizeL&&j<sizeR){if(left[i]<right[j]){arr[k]=left[i];k++;i++;}else{arr[k]=right[j];k++;j++;}}//说明是j到末尾 将left剩余移入arr中while(i<sizeL){arr[k]=left[i];k++;i++;	 	} while(j<sizeR){arr[k]=right[j];k++;j++;	 	}} 
void mergesort(int arr[],int L,int R)
{if(L==R) return; else{int M=(L+R)/2;mergesort(arr,L,M);mergesort(arr,M+1,R);//合并有序的两个序列merge(arr,L,M+1,R);//这里的M和merge中规定的M应保持已知 所以M+1}}
int main(){int arr[]={6,5,7,1,23,8,3,2,9};  mergesort(arr,0,8);for(int i=0;i<9;i++){printf("%d ",arr[i]);}return 0;
}

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